# 从零实现最小SQL数据库：解析器、执行器与简单存储 > 本文从头构建一个简易SQL数据库原型，涵盖SQL解析、查询执行和基本数据存储，适用于原型验证查询处理与数据管理。 ## 元数据 - 路径: /posts/2025/10/22/implementing-minimal-sql-database-from-scratch/ - 发布时间: 2025-10-22T14:01:57+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 站点: https://blog.hotdry.top ## 正文 构建一个最小SQL数据库的原型有助于开发者深入理解数据库的核心机制，包括查询解析、执行优化和数据持久化。这种从零开始的实现方式，能揭示SQL引擎的内部工作原理，避免将数据库视为黑盒子。在实际工程中，这样的原型可用于快速验证查询逻辑或教育目的，而非生产环境。 SQL数据库的基本架构通常分为前端（Parser）和后端（Executor与Storage）。Parser负责将用户输入的SQL字符串转换为抽象语法树（AST），Executor则根据AST生成执行计划并操作数据，Storage提供数据读写接口。借鉴经典教程如SQLite从零实现，我们可以简化这些组件，支持基本的CREATE TABLE、INSERT、SELECT语句。 首先，聚焦Parser的实现。Parser是SQL引擎的入口，需要处理词法分析（Lexing）和语法分析（Parsing）。词法分析将SQL字符串拆分为Token序列，例如关键字（如SELECT）、标识符（如表名）、操作符（如=）和字面量（如'value'）。一个简单的Lexer可以使用状态机遍历字符串，识别这些Token。 例如，在Python中实现Lexer： ```python class Token: def __init__(self, type, value): self.type = type self.value = value def lexer(sql): tokens = [] i = 0 while i < len(sql): if sql[i].isspace(): i += 1 continue if sql[i].isalpha(): word = '' while i < len(sql) and sql[i].isalnum(): word += sql[i] i += 1 tokens.append(Token('KEYWORD' if word.upper() in ['SELECT', 'INSERT', 'CREATE', 'TABLE'] else 'ID', word)) continue # 处理操作符、字符串等... if sql[i] == "'": i += 1 val = '' while i < len(sql) and sql[i] != "'": val += sql[i] i += 1 i += 1 # 跳过结束引号 tokens.append(Token('STRING', val)) continue # 类似处理数字、逗号等 return tokens ``` 这个Lexer支持基本Token识别。接下来是语法分析，使用递归下降解析器构建AST。对于CREATE TABLE语句，AST可能表示为树状结构：CreateTableNode(table_name, columns=[ColumnNode(name, type)])。 对于SELECT语句，AST包括SelectNode(columns, table, where_conditions)。一个简单的Parser函数可以消费Token列表，匹配语法规则： ```python def parse_select(tokens): if tokens[0].type == 'KEYWORD' and tokens[0].value.upper() == 'SELECT': # 解析列、FROM、WHERE pass # 返回AST节点 ``` 这种实现仅支持子集SQL，避免复杂如JOIN或子查询。实际参数：Token类型限制为10种以内，AST节点类不超过5种，确保解析时间O(n)。 证据显示，这种Parser设计在教程中已被验证有效。例如，在cstack的SQLite教程中，Lexer使用有限状态机处理SQL，Parser生成字节码前体，支持高效执行。测试时，可用单元测试验证如"SELECT * FROM users"解析为正确AST。 其次，Executor负责执行AST。它将AST转换为逻辑执行计划，然后物理执行。简单Executor可直接遍历AST：对于SELECT，扫描Storage中的表，应用WHERE过滤，投影所需列。 实现一个内存-based Executor： ```python class Executor: def execute(self, ast, storage): if isinstance(ast, SelectNode): table = storage.get_table(ast.table) result = [] for row in table.rows: if self.eval_where(ast.where, row): projected = {col: row.get(col, None) for col in ast.columns} result.append(projected) return result def eval_where(self, condition, row): # 简单条件评估，如 col = value return True # 占位 ``` 这里，eval_where处理基本谓词。优化点：对于常量过滤，先推下到Storage扫描。但在最小实现中，无需查询优化器，仅顺序扫描。参数建议：行缓冲区大小为1000行，WHERE条件支持=、>、<三种操作符，回滚策略为简单事务（内存快照）。 从key-value存储启发，Executor可集成简单索引加速扫描，但prototype中用全表扫描。风险：无索引时，O(n)扫描对大表慢；限制造成：忽略ACID，仅内存一致性。 最后，Storage层管理数据持久化。最小设计使用内存字典存储表：{table_name: {columns: dict, rows: list of dicts}}。为持久化，序列化到JSON文件或二进制。 示例Storage： ```python class Storage: def __init__(self, file_path): self.tables = {} self.file_path = file_path self.load() def create_table(self, name, columns): self.tables[name] = {'columns': columns, 'rows': []} self.persist() def insert(self, table, row): self.tables[table]['rows'].append(row) self.persist() def get_table(self, name): return self.tables.get(name) def persist(self): with open(self.file_path, 'w') as f: json.dump(self.tables, f) def load(self): try: with open(self.file_path, 'r') as f: self.tables = json.load(f) except FileNotFoundError: self.tables = {} ``` 这个Storage支持基本CRUD，文件路径如'db.json'。参数：每100次写操作flush一次，减少IO；支持TEXT和INT类型，长度限20字符。借鉴nan.fyi的append-only文件，可扩展为段文件，但prototype用JSON简单。 整合组件：REPL循环读取SQL，Parser生成AST，Executor执行返回结果，Storage持久数据。完整prototype约500行代码，用Python快速迭代。 可落地清单： 1. 环境：Python 3.8+，无外部依赖。 2. 测试用例：CREATE TABLE users (id INT, name TEXT); INSERT INTO users VALUES (1, 'Alice'); SELECT * FROM users; 3. 监控点：解析时间<1ms，执行延迟<10ms for 1000行。 4. 回滚策略：内存事务，用try-except包装执行。 5. 扩展：添加B-tree索引，支持UPDATE/DELETE。 这种最小SQL数据库原型揭示了引擎本质：Parser桥接用户与内部，Executor桥接逻辑与物理，Storage桥接内存与盘。虽简陋，却为深入如LSM树或优化器铺路。在工程中，用作教学工具或查询模拟器。 资料来源： - https://nan.fyi/database (键值存储启发) - https://cstack.github.io/db_tutorial/ (SQLite从零教程) - https://build-your-own.org/database/ (Go实现参考) ## 同分类近期文章 ### [Apache Arrow 10 周年：剖析 mmap 与 SIMD 融合的向量化 I/O 工程流水线](/posts/2026/02/13/apache-arrow-mmap-simd-vectorized-io-pipeline/) - 日期: 2026-02-13T15:01:04+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析 Apache Arrow 列式格式如何与操作系统内存映射及 SIMD 指令集协同，构建零拷贝、硬件加速的高性能数据流水线，并给出关键工程参数与监控要点。 ### [Stripe维护系统工程：自动化流程、零停机部署与健康监控体系](/posts/2026/01/21/stripe-maintenance-systems-engineering-automation-zero-downtime/) - 日期: 2026-01-21T08:46:58+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析Stripe维护系统工程实践，聚焦自动化维护流程、零停机部署策略与ML驱动的系统健康度监控体系的设计与实现。 ### [基于参数化设计和拓扑优化的3D打印人体工程学工作站定制](/posts/2026/01/20/parametric-ergonomic-3d-printing-design-workflow/) - 日期: 2026-01-20T23:46:42+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 通过OpenSCAD参数化设计、BOSL2库燕尾榫连接和拓扑优化，实现个性化人体工程学3D打印工作站的轻量化与结构强度平衡。 ### [TSMC产能分配算法解析：构建半导体制造资源调度模型与优先级队列实现](/posts/2026/01/15/tsmc-capacity-allocation-algorithm-resource-scheduling-model-priority-queue-implementation/) - 日期: 2026-01-15T23:16:27+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 深入分析TSMC产能分配策略，构建基于强化学习的半导体制造资源调度模型，实现多目标优化的优先级队列算法，提供可落地的工程参数与监控要点。 ### [SparkFun供应链重构：BOM自动化与供应商评估框架](/posts/2026/01/15/sparkfun-supply-chain-reconstruction-bom-automation-framework/) - 日期: 2026-01-15T08:17:16+08:00 - 分类: [systems-engineering](/categories/systems-engineering/) - 摘要: 分析SparkFun终止与Adafruit合作后的硬件供应链重构工程挑战，包括BOM自动化管理、替代供应商评估框架、元器件兼容性验证流水线设计