从零手写数据库:深入理解存储引擎、索引与查询执行原理 你有没有过这样的经历面对一个复杂的业务系统数据库查询突然变慢你看着满屏的执行计划却无从下手心里忍不住想如果我能从头理解数据库是怎么工作的是不是就能更快地定位问题或者当你学习各种数据库优化技巧时总觉得隔着一层纱那些索引、事务、锁机制听起来都懂但总觉得少了点“手感”。几年前我也被这种感受困扰。直到我决定做一件在很多人看来“费力不讨好”甚至“疯狂”的事抛开所有成熟的数据库系统从零开始用代码“手搓”一个最简单的数据库。这听起来像是一个庞大的学术项目但我的目的非常功利不是为了发明新东西而是为了“拆解”。我想知道当我把“数据库”这个黑盒一层层剥开里面最核心的、不可再简化的骨架到底是什么那些让我头疼的“慢查询”在最底层究竟卡在了哪个环节这个过程远比想象中更有收获。它没有让我成为数据库专家但它给了我一把“手术刀”。当再次面对生产环境的数据性能瓶颈时我不再是盲目地尝试各种配置参数而是能清晰地在大脑中勾勒出数据从磁盘到内存经过解析、优化、执行最终返回结果的完整路径。我知道问题可能出在路径的哪一个“关节”上。今天我想和你分享的不是另一个数据库项目的代码而是这次“徒手造轮子”旅程中最核心的认知收获。我们会避开复杂的分布式和高级特性聚焦于一个单机、单用户、最简化的数据库内核。你会发现理解数据库关键不是记住所有功能而是看清数据流动的基本范式。这个范式是解开所有高级特性的万能钥匙。1. 起点抛开“数据库”的抽象回到“数据”本身我们习惯把数据库看作一个整体一个接收SQL、返回结果的魔法盒子。但在一开始你必须忘掉“数据库”这个词回到最原始的问题我们到底想用它来存什么、怎么取本质上我们需要一个能持久化保存数据断电不丢失并能根据某些条件快速找到其中一部分数据的系统。抛开事务、并发、复杂查询最核心的就这两件事存和取。1.1 最笨的方法文本文件与全表扫描最直接的实现是什么一个文本文件。每一行是一条记录用逗号或制表符分隔字段。要“插入”就在文件末尾追加一行。要“查询”就打开文件从头读到尾逐行解析匹配条件。# 伪代码示例基于文件的“数据库” def insert(filename, record): with open(filename, a) as f: f.write(,.join(record) \n) def select_all(filename): with open(filename, r) as f: return [line.strip().split(,) for line in f] def select_where(filename, condition_field, condition_value): results [] for record in select_all(filename): if record[field_index] condition_value: results.append(record) return results这就是一个“数据库”的雏形。它完美地诠释了持久化文件和查询全扫描。但它的性能是灾难性的数据量稍大比如十万行每次查询都要读取整个文件时间复杂度是O(N)。这就是最经典的“性能瓶颈”场景没有索引的全表扫描。此时你就能切身感受到所有数据库优化教程里那句“避免全表扫描”有多重的分量。它不是一句轻飘飘的建议而是底层机制决定的必然。1.2 第一次进化引入“索引”的思想如何避免全表扫描我们需要一个“目录”。比如如果我们经常按user_id查询可以维护一个单独的“索引文件”。这个文件不存完整数据只存user_id和该条记录在数据文件中的“位置”比如行号或字节偏移量。并且这个索引文件里的user_id是有序的。索引文件 (user_id - position) 1001, 0 1002, 120 1003, 245 ...当查询user_id1002时我们不再扫描整个数据文件而是先在有序的索引文件中使用二分查找快速定位到1002对应的位置120然后直接跳到数据文件的第120字节处读取记录。时间复杂度从O(N)降到了O(log N)。这就是索引最朴素的思想用额外的空间存储索引文件和维护成本插入/删除数据时也要更新索引换取查询时的速度飞跃。几乎所有数据库索引B-Tree, Hash, Bitmap等都是这个思想的复杂变体核心目标都是将随机匹配变为快速定位。到这里你已经实现了数据库最核心的两个组件存储引擎数据文件和索引机制。一个能工作的、针对特定查询很快的“数据库”已经有了骨架。2. 核心理解存储引擎——数据如何在磁盘上安家当我们说“数据库”时很大一部分指的是它的存储引擎。这是负责和数据文件磁盘打交道的部件。它的设计直接决定了数据库的吞吐量、可靠性和数据恢复能力。2.1 直面磁盘的特性随机IO与顺序IO的天壤之别这是理解所有存储优化的基石。磁盘包括SSD的特性是顺序读写远远快于随机读写。顺序读1MB数据可能只需一次寻道加连续传输而随机读1MB数据如果分散在1000个不同位置可能需要1000次寻道。因此存储引擎设计的黄金法则尽可能将随机写转换为顺序写。最经典的实现是日志结构合并树LSM-Tree的思想。它不直接在原数据文件上修改。所有新的插入、更新、删除操作都只是追加写入到一个顺序的日志文件常称为WALWrite-Ahead Log和一个内存中的有序结构MemTable里。当MemTable大到一定程度它被冻结并顺序写入磁盘成为一个不可变的排序字符串表SSTable。查询时需要合并检查内存的MemTable和磁盘上的多个SSTable。通过后台的“压缩”过程合并多个SSTable清理过期数据。这样做的最大好处是写入几乎全是快速的顺序追加。代价是读取可能变慢需要查多个地方并且需要后台压缩线程。LevelDB, RocksDB, Cassandra都基于此思想。另一种经典模式是B树。它试图在磁盘上维护一棵始终平衡的树状结构。每个树节点对应磁盘上一个页Page如4KB或16KB。更新数据时需要在原位置修改对应的页这可能导致随机写。为了优化通常也会配合WAL日志先顺序记录操作日志再异步更新数据页以保证崩溃恢复。2.2 自己实现一个最简单的存储层我们不必实现完整的LSM或B树但可以体验其核心概念。假设我们采用一种极简的“分页”模型定义页数据文件被划分为固定大小的页例如4096字节。按页读写从不单独读写某一行总是读写整个页。页内管理一个页内可以存放多条记录并有一个小小的页头来管理空闲空间和记录指针。# 极简页结构伪代码 PAGE_SIZE 4096 class Page: def __init__(self, page_id): self.page_id page_id self.data bytearray(PAGE_SIZE) self.free_space_offset 4 # 前4个字节存放空闲空间起始位置 self.num_records 0 # 假设记录是定长的可以用一个数组存偏移量 def insert_record(self, record_bytes): # 计算插入位置 insert_offset self.get_free_offset() # 将record_bytes写入data的insert_offset处 # 更新空闲位置指针和记录数 pass def get_record(self, slot_id): # 根据slot_id找到记录偏移量从data中读取字节并解析 pass为什么这么做因为磁盘和操作系统也是按块Block管理的。一次读写一个页是对硬件和系统缓存友好的。这解释了为什么数据库有“页大小”这个参数为什么行不能无限大不能超过页大小以及为什么“行溢出”会带来性能问题。当你自己实现一次“从字节数组里解析出一条记录”的操作后你会对序列化/反序列化的成本有深刻体会。这也是为什么数据库字段类型、长度如此重要以及为什么SELECT *在真正的大数据量下是危险的——它可能迫使数据库读取大量你不需要的字段进行无谓的反序列化。3. 大脑SQL解析与查询执行——从声明到过程的翻译用户输入的是“要什么”SQL数据库需要把它变成“怎么做”执行计划。这个翻译过程就是查询处理。3.1 解析器与语法树理解SQL的结构第一步是解析。将SELECT name FROM users WHERE id 1这样的字符串转换为一棵结构化的抽象语法树AST。SELECT / \ name FROM | users | WHERE | / \ id 1这棵树清晰地表达了查询的意图从users表中选取满足条件id1的记录的name字段。自己写一个简单的SQL解析器或使用现成的解析器生成工具如ANTLR是极具启发性的。你会立刻明白为什么SQL语法有固定的顺序SELECT...FROM...WHERE...因为解析器就是按这个规则来构建树的。3.2 执行计划查询的“作战地图”得到AST后数据库需要制定一个“作战计划”——执行计划。对于我们的简单查询一个朴素的计划是全表扫描遍历users表的每一行。过滤对每一行检查id字段是否等于1。投影对满足条件的行只提取name字段返回。但如果id字段上有索引一个更好的计划是索引查找在id的索引中快速找到id1对应的记录位置。回表根据位置去主数据文件中取出整行记录如果需要其他字段。投影提取name字段返回。查询优化器的工作就是基于表的统计信息有多少行索引的选择性如何等从多个可能的执行计划中估算每个计划的成本主要考虑IO次数选择成本最低的那个。自己实现时我们可以跳过多复杂的优化器但必须实现一个火山模型的执行引擎。每个执行计划节点如扫描、过滤、投影都实现一个next()接口每次调用返回下一行结果。class SeqScanNode: def __init__(self, table): self.table table self.current_row 0 def next(self): if self.current_row len(self.table.rows): return None row self.table.rows[self.current_row] self.current_row 1 return row class FilterNode: def __init__(self, child, condition): self.child child self.condition condition # 例如 lambda row: row[id] 1 def next(self): while True: row self.child.next() if row is None: return None if self.condition(row): return row class ProjectNode: def __init__(self, child, fields): self.child child self.fields fields def next(self): row self.child.next() if row is None: return None return {field: row[field] for field in self.fields} # 组合成执行计划 plan ProjectNode( FilterNode( SeqScanNode(users_table), lambda row: row[id] 1 ), [name] ) # 执行 while (row : plan.next()) is not None: print(row)通过这样串联节点数据就像在流水线上一样从一个操作符流向下一个操作符。这让你直观地理解执行计划是什么以及为什么在WHERE条件中使用函数如WHERE UPPER(name) ALICE会导致索引失效——因为它破坏了“流水线”的流畅性必须在过滤前对每一行数据先做计算。4. 基石事务与恢复——可靠性的代价单用户、单线程操作上面这些差不多够了。但数据库之所以是数据库而不是高级文件系统关键在于它提供了事务保证ACID原子性、一致性、隔离性、持久性。自己实现事务会让你明白“可靠性”不是免费的午餐。4.1 原子性与持久性WAL日志的力量如何保证一个事务要么全部完成要么像没发生过一样原子性并且完成的事务不会丢失持久性核心机制是预写式日志。原理很简单但极其有效在修改任何实际数据页之前先将“打算做什么”以日志记录的形式顺序、持久地写入一个单独的日志文件。例如“事务T1在页5偏移量100处将值‘A’更新为‘B’”。日志写入成功通常需要调用fsync确保落盘后才去内存中修改数据页。定期将内存中被修改过的脏页刷回磁盘数据文件。为什么这样能保证原子性和持久性原子性如果事务中途崩溃数据库重启时会读取日志。发现事务T1只有开始记录没有提交记录就会根据日志中的“前像”信息将事务T1已经修改的数据全部回滚。持久性只要事务的提交记录写入了日志并落盘即使随后数据页还没来得及刷盘就崩溃重启后也可以根据日志中的“后像”信息重新执行重做这个事务的所有修改从而保证不丢失。自己实现一个最简单的WAL你会深刻理解COMMIT这个命令背后沉重的代价——它可能触发一次耗时的磁盘fsync操作。这也是为什么数据库有“同步提交”和“异步提交”的配置选项是在性能和数据安全之间做权衡。4.2 隔离性锁与多版本并发控制当多个用户同时读写时如何保证他们互不干扰最简单的办法是锁。读之前加共享锁写之前加排他锁。这会导致性能问题和死锁。更优雅的方案是多版本并发控制。它为每条记录维护多个版本。当一个事务修改某行时它创建该行的一个新版本并带上自己的事务ID。其他正在运行的事务根据自身的开始时间只能看到在它开始之前已经提交的版本。这样读操作永远不会被写操作阻塞读旧版本写操作之间通过锁或更复杂的机制来协调。实现MVCC相对复杂但它的思想非常深刻用空间存储多个版本换时间避免读写锁冲突是应对高并发读场景的经典设计。5. 从玩具到工具我们获得了什么写一个玩具数据库并不意味着你要用它去替代MySQL或PostgreSQL。恰恰相反这个过程让你更深刻地理解了为什么需要这些成熟的数据库。性能问题的归因能力当看到慢查询时你能立刻在脑中映射是在全表扫描索引失效产生了临时表发生了大量的随机IO锁等待理解了底层优化就有了方向。配置参数的理解innodb_buffer_pool_size是什么是数据库的内存缓存池用来缓存数据页和索引页减少磁盘IO。wal_sync_method是什么是WAL日志刷盘的方式在数据安全与写入延迟间的权衡。现在这些参数不再是魔法数字。设计时的避坑意识知道索引的维护成本就会谨慎创建冗余索引知道事务的代价就会避免不必要的大事务知道MVCC的原理就会明白长事务可能导致旧版本数据无法清理引发表膨胀。学习高级特性的加速器再去学习读写分离、分库分表、分布式事务时你会很容易理解它们要解决的核心矛盾是什么——无非是存储、计算、一致性在分布式场景下的延伸与妥协。最终这个过程的全部价值可以凝结为一句话它把你从一个被动的数据库“用户”变成了一个主动的“对话者”。你不再只是向一个黑盒发送指令并祈祷它运行良好而是开始理解它的语言、它的局限、它的代价。当问题出现时你能够提出更精准的问题设计更有效的验证实验并真正理解解决方案背后的原理。所以如果你也对数据库内部感到好奇或者希望摆脱对数据库调优的盲目感我强烈建议你尝试这个“徒手造轮子”的练习。不必追求功能完整从最简单的键值存储开始加上WAL加上简单的B-Tree索引。每一步的实现都会在你脑中刻下一道清晰的印记。这些印记终将成为你解决复杂数据系统问题时最可靠的思维地图。