手写持久化B树KV存储引擎：从原理到工程实现-北京尧图网络

直接手写一个支持持久化的B树KV存储引擎这件事听起来像是在重复造轮子但真正动手之后你会发现数据结构教材里的那几页纸和工程实现之间的距离远比你想象的大。这个项目适合两类人一类是想彻底搞懂B树、B树原理的开发者另一类是正在做自己的数据库、嵌入式存储方案需要从底层掌控读写路径的人。我做完这个项目之后最大的感受是——把懂原理变成能落地中间隔着一整套关于磁盘、缓存和崩溃恢复的工程细节。这个项目的输入很纯粹一个标题btree B树实现key-value存储没有更多约束。那我就不客气了把从数据结构设计到磁盘落盘、再到并发和恢复的完整路径都讲一遍所有代码风格和工程方案都基于我在类似项目里的常见实践来展开给你一条可以直接照着走的路。1. KV存储选型为什么是B树而不是别的东西1.1 哈希表、跳表、LSM与B树的取舍很多人的第一反应是KV存储用哈希表不就行了吗查找O(1)实现简单内存里跑得飞快。但一旦数据量超过内存容量必须落盘哈希表的问题就暴露了——它的访问模式是随机I/O。哈希表扩容、rehash、冲突链这些操作在内存里是几纳秒的事到了磁盘上就是每次随机寻道性能直接崩盘。那么LSM-Tree呢现在很多分布式存储都在用写性能极好靠顺序写和后台合并。但LSM的读放大和写放大是硬伤读路径要查多层SSTable还需要布隆过滤器辅助复杂度比B树高一个量级。而且如果你的业务是那种写入不多、读取很多、对读延迟敏感的场景LSM并不合适。跳表或者红黑树呢在内存里它们都是很优秀的有序结构但问题是节点之间通过指针连接在磁盘上指针就是页号每次沿着指针走一步就是一次随机I/O。B树把大量键值组织在一个节点里节点大小对齐磁盘页一次I/O能拿到一整块数据局部性原理用到了极致。所以选择B树的核心逻辑是它天然为磁盘设计。树的深度浅一个几百万KV的B树三层就够每层访问一次磁盘从根到叶子稳定在三次I/O以内。这种可预测的低延迟对很多业务场景来说是刚需。1.2 这个项目要做成什么样动手之前先把边界划清楚。这个项目我定义成单机嵌入式KV存储接口参考通用的key-value语义put、get、delete再加上扫描接口范围查询。数据落盘到单个文件支持进程重启后数据不丢。不追求分布式不追求完整的SQL层就是一个纯粹的存储内核。明确边界很重要。我见过太多人写着写着就想加事务、加并发控制、加备份工具结果主线功能反而不完整。这个项目先把存储核心跑通后面的扩展再说。2. 从B树到B树核心数据结构设计2.1 B树保持平衡的底层逻辑B树的定义不用我背了关键在于它为什么能保持平衡所有叶子都在同一层节点分裂时自底向上生长根节点是唯一允许长高的地方。这种生长方式保证了任何路径的长度一致。这里有个工程上的细节值得讲参数选择。阶数m决定一个节点最多有多少个子节点但工程上更常用的是每个节点最多存多少个键这个值它直接由节点大小和键值大小推导出来。我设的页大小是4096字节也就是常说的4KB这是磁盘扇区对齐的经典选择很多文件系统块大小也是4KB。键是8字节的整数值定长64字节按这个算一个叶子节点大约能存45个键值对。当然实际可以动态调整但初期先固定下来后面再做变长优化。分裂时机是插入路径上最要小心的。节点键数达到上限时必须分裂中间键上提到父节点左右两半留在原节点和新节点里。这里有个我犯过的错误分裂之后忘了把父节点的子指针数组顺序调整对导致后面的查找走到了错误的子树。诊断了半天才发现是子指针比键多一个的那一个放错了位置。// 节点分裂的伪代码思路 // 假设节点已满keys数量 MAX_KEYS mid MAX_KEYS / 2 left_node.keys keys[0..mid-1] right_node.keys keys[mid1..MAX_KEYS-1] promote_key keys[mid] // 非叶子节点还要把子指针一分为二 // 父节点插入 promote_key 和 right_node 的指针2.2 B树叶子链表如何让范围查询少走弯路B树和B树最大区别是B树非叶子节点只存索引键不存值所有值都在叶子节点叶子节点之间用链表串起来。这个设计的价值在做范围查询时体现得最明显——找到下界之后沿着叶子链表一路往后扫就行不需要反复回溯父节点。我在实现的时候把叶子链表设计成双向链表这多花了一点维护成本但换来了一个很实际的便利反向范围扫描也能做到O(1)跳跃。如果你只需要正向扫描单向链表就行但做取最近N条这种需求时双向链表省事很多。还有一个容易被忽略的点非叶子节点只存键。这意味着同样4KB的页内部节点能放下更多键树变得更宽更扁平层数进一步压缩。实际效果是3000万条数据树高稳定在3层。查任意一条数据根节点、中间层、叶子层三次磁盘I/O搞定。3. 磁盘上的KV怎么组织持久化细节3.1 页存储与页管理内存里的节点最终要映射到磁盘上的页。我在文件开头预留了一个固定大小的头部记录根节点页号、节点总数、空闲页链表头等信息。每个页固定4096字节页内布局如下页号4字节、类型标记1字节内部节点/叶子节点、键数量4字节、剩余空间存放键数组、子指针数组或值数组。页号是节点的磁盘地址根节点页号变了树长高时要写回文件头。删除操作会产生空闲页我维护了一个简单的空闲页链表把被删的页号串起来新页优先从链表里取。这里必须提醒一个坑页内数据对齐。键数组和值数组都是定长的但结构体里如果把uint8和uint64混在一起排列编译器会自动加padding导致你算好的偏移量全错。我干脆不用结构体直接映射而是手动计算偏移量写辅助函数get_key(index)、set_value(index)读写都走显式序列化虽然代码啰嗦一点但排错容易。3.2 崩溃恢复与预写日志直接改页就完事肯定不行。进程在写入过程中崩溃文件可能处于半更新状态比如节点分裂写了一半父节点的指针还没来得及更新数据就丢了。解决这个问题的标准做法是预写日志WAL。我的策略是这样的每次变更先以追加的方式写入一个独立的日志文件日志里包含页号、页内偏移、旧值和新值。日志写成功后再把变更应用到数据文件。恢复时扫描日志把未完成的操作重放一遍保证数据文件最终一致。日志刷盘的时机也有讲究。同步刷盘每次写入都fsync最安全但最慢异步刷盘性能好但可能出现小窗口的数据丢失。我采取了折中方案批量提交积攒若干条操作后一次性刷盘配合一个后台线程定时刷。单机上这个方案实测稳定性和性能都过得去。4. 核心实操查找、插入、删除的实现4.1 查找路径从根到叶子的三次I/O查找逻辑很简单但细节决定成败。从根节点开始在当前节点的键数组里找第一个大于等于目标键的位置i如果找到且key等于目标键在叶子节点里直接返回值如果是内部节点就沿着第i个子指针继续向下。很多人写B树查找时容易把内部节点的查找搞混内部节点存的是路标键指引你去哪个子树找到完全相等的键并不代表值在这里值永远不会出现在内部节点上。def search(key): node read_page(root_page_id) while not node.is_leaf: i bisect_left(node.keys, key) node read_page(node.children[i]) i bisect_left(node.keys, key) if i len(node.keys) and node.keys[i] key: return node.values[i] return None这段逻辑的要点在bisect_left返回的位置i如果key正好命中直接返回如果没命中i指向第一个大于key的位置这个位置就是下一步要去的子树。孩子数组总是比键数组多一个这是B树不变的规则。4.2 插入与分裂最容易写崩的环节插入分两步先插入键值对再沿路径向上检查是否触发分裂。递归写法最清晰——子树返回一个需要上提的键和新增的右兄弟节点父节点收到后决定是否插入并继续上提。分裂时有一种情况必须单独处理根节点满了。根节点满时不向上提而是新建一个空根节点把原根节点分裂成两个子节点树的高度加一。这意味着分裂是老根变矮、新根长出来的过程。代码里要记得把新根节点的页号写回文件头。def insert(node_page_id, key, value): node read_page(node_page_id) if node.is_leaf: insert_into_leaf(node, key, value) else: i bisect_left(node.keys, key) child_result insert(node.children[i], key, value) if child_result.is_split: insert_child_pointer(node, child_result.promote_key, child_result.new_child_id) if node.key_count MAX_KEYS: return split_node(node) else: write_page(node) return NotSplit插入时另一个常见的坑是重复键。有的实现允许重复键但那会让叶子节点键数组里的顺序关系变得复杂。我这个项目选择键唯一重复put直接覆盖旧值。这样查找和删除的语义最简单也最容易和上层业务对齐。4.3 删除与合并少做Pessimistic的优化删除是B树里最麻烦的操作。一个键没了之后节点键数可能低于下限一般下限是上限的一半。这时候有两个选择先从兄弟节点借一个键借不了就合并。借键时要注意不能只动当前节点因为两个叶子节点之间的借调要经过父节点中转父节点里的索引键也要同步更新。def delete(node_page_id, key): node read_page(node_page_id) if node.is_leaf: if key not in node.keys: return NotFound remove_from_leaf(node, key) else: i bisect_left(node.keys, key) child_result delete(node.children[i], key) if child_result.underflow: rebalance(node, i) if node.key_count MIN_KEYS and node is not root: return Underflow write_page(node) return OK这里我想说一个经验和教训不要做提前合并。有一种优化思路是删除时只要发现节点快空了就立刻合并这看起来更主动但会让删除操作频繁触发父节点变动写放大反而变严重。实际测试里改成懒合并——先标记等键数低于下限且确实需要时再合并——性能好了不少。当然这依赖具体场景如果你的业务删除非常密集可以再权衡。5. 缓存与并发性能的最后一块拼图5.1 LRU缓存把热点页留在内存磁盘I/O再快也要微秒级内存访问是纳秒级差了两个数量级。所以存储引擎必须加缓存。我的实现是一个简单的LRU缓存以页号为key缓存页对象命中率直接决定了引擎的吞吐。LRU有一个工程实现技巧用双向链表哈希表组合链表记录访问顺序哈希表提供O(1)随机访问。每次访问页时把页挪到链表头部缓存满时淘汰链表尾部。为了减少锁竞争我给了缓存一个分段锁设计按页号hash分到16个桶每个桶独立的锁实测并发性能比单锁好了好几倍。缓存还有一个和持久化配合的问题淘汰页之前必须先写回磁盘否则内存里改过但磁盘上还是旧数据等进程崩溃就丢了。我在页对象里加了一个dirty标志淘汰时如果dirty才写盘干净页直接丢弃。这个细节不处理缓存就会变成数据丢失的帮凶。5.2 并发控制读写锁的粗粒度方案并发控制是存储引擎的老大难。我用了读写锁多个读者可以同时进树写者独占。锁的粒度是整棵树一个读写锁实现最简单也不容易死锁但瓶颈明显——写入多了之后读者全被堵住。如果后续要优化并发可以降到节点级别的锁或者乐观锁并发控制。但说实话这个项目的核心价值在存储结构本身并发优化是增量项。先把正确性做对性能瓶颈后面用profiler定位。5.3 常见问题与排查技巧实录做这个项目我踩过的坑值得列出来都是文档里不会写的。第一个坑是页内容与缓存不一致。现象是put之后马上get偶尔会拿到旧值。排查下来发现在更新页之后没有把页标记为dirty缓存淘汰时把更新过的页当干净页丢掉了。解决办法很简单所有修改页的路径都走统一的mark_dirty接口杜绝遗漏。第二个坑是分裂后的递归传递。分裂返回的上提键和右兄弟页号在递归返回时传丢了。B树插入的递归返回值设计不好很容易出这类问题。我最后定了一个结构体is_split、promote_key、new_child_id三个字段专门用来在递归中传递分裂信息再也没错过。第三个坑是文件头更新时机。根节点分裂时新的根节点页号写进文件头但这个写入被延迟到了整个插入操作结束后。如果中途崩溃文件头指向的还是旧根页而这个页的内容已经被改得不成样子了。修复方式是把文件头更新纳入WAL保护崩溃恢复时重放日志把文件头修正好。下面是一个简易排查速查表方便你对照现象可能原因排查思路get返回旧值缓存页未标记dirty检查所有修改路径是否统一走mark_dirty插入后树结构错乱分裂信息在递归中丢失用结构化返回值传递is_split/promote_key/new_child_id崩溃后数据异常文件头未纳入WAL把根节点页号这类元数据变更也写入日志范围扫描漏数据叶子链表指针维护错误检查分裂时链表的前驱/后继是否重新串联删除后树仍不平衡父节点索引键未同步借键路径上父键也要更新不只是兄弟节点数据6. 性能实测与调优方向6.1 基准数据与瓶颈在一台普通的开发机上数据集100万条键8字节值64字节顺序写入速度大约每秒12万次随机写入每秒8万次随机读取每秒15万次。顺序读因为缓存命中率高的关系每秒能到几十万次。瓶颈很明显不在B树本身而在刷盘频率和缓存命中率。提高缓存大小从64MB到512MB随机读性能翻了一倍因为热点页不再频繁淘汰。写入性能和刷盘频次强相关批量提交/按组提交对写入吞吐的影响是数量级的。6.2 下一步值得做的优化如果想把项目做成可用的产品有几个方向可以继续变长key和value支持动态调整页内布局、持久化空闲页管理目前用链表线性扫描页多了之后效率低可以换成B树管理的空闲页位图并发控制从粗粒度读写锁升级成节点级锁再加一个简单的索引统计信息方便上层做执行计划。但我建议在项目初期不要急着做这些先把定长KV版本的正确性打磨好写全单元测试做crash consistency测试。一个错误的索引比没有索引更糟糕稳定性和可调试性永远是存储引擎的第一优先级。7. 结束前想说的话做这个项目最大的收获是理解了数据结构和存储引擎之间的鸿沟。教材上的B树在内存里操作指针工程里的B树在磁盘上操作页号中间差着一层序列化、缓存和日志。每一次分裂都对应着磁盘写入每一次崩溃恢复都要保证日志与数据的一致性——这些才是存储内核真正复杂的部分。如果你也想动手写一个我建议从最朴素的定长KV开始先不要变长、不要并发、不要缓存就一个MappedFile加递归分裂跑通正确性再逐步加料。一步步来比一开始就想做成MySQL容易得多。写完之后你会对数据库底层多一份敬畏也多一份底气。

手写持久化B树KV存储引擎：从原理到工程实现

相关推荐

网络模拟实战：从tc到Chaos Mesh的三层故障注入体系

破除数据孤岛，从数据标准到治理的制造数字化基座搭建指南

新手养虾三天就团灭？观赏虾入坑前必须搞懂的水质真相

更多资讯

提示词工程师会消失吗？从模型进化看AI职业转型之路

LeetCode 730详解：区间DP与容斥原理解决不同回文子序列计数

AI透明度危机：大模型安全评测、脑机接口与幻觉治理的底层逻辑

LeetCode 730 不同回文子序列：动态规划去重与Java实现

数据库设计与应用开发实战：ER图、索引优化与事务控制要点

DE/SHADE/L-SHADE算法在CEC2005基准函数上的Matlab对比实验及实现细节

今日更新

智能硬件视频会议集成：从芯片选型到场景落地的全栈实践

FFmpeg音视频处理与5路RTMP推流实战：从原理到118克盒子部署

RK3528+1GB内存如何变身直播节点？硬编解码与六协议实战复盘

本周精选

金融AI落地指南：从调研报告到技术选型与工程实践

大模型上下文成本与注意力优化技术深度解析——为何O(n²)平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测

基于GMM的语音识别系统原理与MATLAB实现详解

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？