BoltDB 源码分析（二）：B+Tree、Bucket 与 Cursor

上一篇我们把外层地基搭起来了：

1. DB 如何管理文件、mmap 和事务
2. meta 如何定义整个数据库的当前版本
3. 只读事务为什么只是拿一个 root 视图
4. 写事务为什么必须单线程串行

这一篇我们进入真正存数据的地方：B+Tree 本体。

如果说第一篇回答的是“BoltDB 作为数据库是怎么活着的”，那这一篇要回答的是：

1. 一个 bucket 在文件里到底长什么样
2. branch page 和 leaf page 如何表达一棵树
3. cursor 为什么能支持有序扫描和 seek
4. 为什么写事务要先把 page materialize 成 node
5. split / rebalance 到底是怎么发生的

上一篇： BoltDB 源码分析（一）：事务、mmap 与文件格式

下一篇： BoltDB 源码分析（三）：提交、freelist 与崩溃恢复

1. 先纠正一个常见误解：Bucket 不是 page，Bucket 是“子树入口”

在 BoltDB 的 API 里，大家最常接触的是 Bucket：

1. tx.Bucket(name)
2. bucket.Get(key)
3. bucket.Put(key, value)
4. bucket.CreateBucket(child)

这很容易让人误以为 Bucket 是某个固定 page 类型。

其实不是。

源码里真正持久化的 bucket 结构只有两个字段：

1. root pgid
2. sequence uint64

这意味着 bucket 在磁盘上的本质只是：

一个指向子树根页的描述头。

于是整个 BoltDB 顶层实际上是这样组织的：

1. root bucket 负责管理“顶层 bucket 名称 -> 子 bucket”
2. 每个子 bucket 再有自己的 root page
3. 每个 bucket 自己维护一棵独立 B+Tree

所以 bucket 更像“namespace + subtree root”的组合，而不是“表对象”的完整实体。

2. page 上的数据布局：BoltDB 的树结构全部压在这几种 element 里

2.1 branch page 只保存导航信息

branchPageElement 只有三个字段：

1. pos
2. ksize
3. pgid

其中真正重要的是 key + pgid 这对组合：

1. key 表示该子树的下界锚点
2. pgid 指向下一级 page

branch page 不存 value，它的职责只有一个：决定查找时该往哪个子 page 走。

2.2 leaf page 保存真实键值

leafPageElement 比 branch 多两个维度：

1. flags
2. vsize

leaf element 的真正含义是：

1. 一个有序 key
2. 对应 value
3. 以及这个 value 是普通值还是 bucket 值

这里 flags & bucketLeafFlag != 0 特别重要，因为它说明：

嵌套 bucket 并不是单独的“目录项类型”，而是 leaf value 中存放了一个 bucket header，必要时还可能内联一个小型根页。

这就是 BoltDB 设计里非常精巧的一点。它没有额外发明一套“子 bucket 元数据区”，而是直接把 bucket 当成 leaf value 的一种特殊语义。

2.3 key/value 真正存放在 element 数组之后的变长区域

无论 branch 还是 leaf，page 内部都不是“结构体数组里直接塞变长字段”，而是：

1. 前面先放固定大小的 element header 数组
2. 后面一片连续空间顺序存 key/value 原始字节
3. pos 负责告诉你当前 element 的数据从哪里开始

这种布局有几个好处：

1. page 内部紧凑
2. 有利于顺序扫描
3. split/spill 时容易整体重写

缺点也很明显：

1. 任意插入并不是局部改几个字节就完事
2. 一旦页要修改，常常会倾向于整页重写

而这恰好与 BoltDB 的 copy-on-write 事务模型非常匹配。

3. inline bucket：BoltDB 为小 bucket 做的一次重要优化

bucket.go 里有一段很值得细读的逻辑：openBucket() 会在 child.root == 0 时，把 value 后面的数据当成一张内联 page。

这意味着：

1. 如果一个 bucket 很小
2. 并且它没有嵌套子 bucket
3. 并且序列化后尺寸不超过阈值

那么它可以直接被内联在父 bucket 的 leaf value 里，而不用单独占真实 page。

源码里的判定标准主要来自 inlineable()：

1. 必须只有一个 leaf root node
2. 不能包含子 bucket
3. 总大小不能超过 pageSize / 4

这个优化非常有价值，因为很多应用确实会有大量小 bucket。若每个都分配独立 page：

1. 空间浪费会非常明显
2. 读路径会多一次 page 跳转
3. page 管理压力也会上升

所以 inline bucket 的本质就是：

用更复杂一点的 value 语义，换取小对象存储密度。

4. Cursor 为什么是理解 BoltDB 读路径的核心

BoltDB 的读 API 看起来很多，但真正底层大多都会落到 Cursor 上。

例如：

1. Bucket.Get() 内部会 Cursor().seek(key)
2. Bucket.ForEach() 内部会从 First() 一路 Next()
3. Bucket.Bucket(name) 也是先 seek 再判断 bucketLeafFlag

所以只要读懂 Cursor，基本就读懂了 BoltDB 的查找与遍历。

4.1 Cursor 用一个栈保存从根到叶子的路径

Cursor 里最关键的数据结构不是指针，而是：

stack []elemRef

每个 elemRef 记录：

1. 当前在看的是 page 还是 node
2. 当前层 index 落在哪个元素上

于是一次 seek() 的过程，本质上就是：

1. 从 bucket 根开始
2. 在 branch page 上二分查找应该下钻到哪个 child
3. 把这一层位置压栈
4. 一路走到 leaf
5. 在 leaf 上再做一次二分

栈保存的不是“访问历史”，而是当前位置的完整路径。这让 Next() / Prev() 能够非常自然地工作：

1. 先尝试在当前叶子页移动 index
2. 不行就往上回退到某个还能前进的父层
3. 然后再沿最左/最右路径下钻回叶子

这跟文件系统目录遍历或者 B+Tree iterator 的标准写法很像，但 BoltDB 写得相当紧凑。

4.2 Seek() 找到的不是“相等”，而是“第一个大于等于”

nsearch() 和 searchPage() 用的都是 sort.Search。它们的语义不是“必须命中”，而是：

找到第一个 key >= target 的位置。

因此 Seek(k) 的行为是：

1. 如果 key 存在，返回它
2. 如果不存在，返回下一个更大的 key
3. 如果已经超出最后一个 key，则返回 nil

这让范围扫描非常自然，因为有序存储 + lower bound 查找本来就是 B+Tree 最擅长的事。

4.3 为什么遍历时修改数据会出问题

源码注释明确提醒：

在 cursor 遍历过程中修改 bucket，可能让 cursor 失效。

原因并不神秘：

1. cursor 的 stack 记录的是当前树结构中的路径
2. 一旦当前 leaf/node 因写操作发生 split、merge、rebalance
3. 原来的路径引用就可能不再对应同一逻辑位置

所以 BoltDB 没有尝试给 cursor 提供“结构变化下的稳定迭代器”语义，而是把约束交给使用者：修改后请重新定位。

这很务实，也很符合它“实现小而清楚”的风格。

5. 为什么写事务不能直接改 page，而要 materialize 成 node

这一步是源码里最值得慢慢体会的地方。

读事务完全可以直接读 mmap 中的 page，因为它不修改。

但写事务如果也直接在 page 上原地做插入删除，会立刻遇到几个问题：

1. page 是紧凑布局，插删代价高
2. split / merge / rebalance 会牵涉父子层联动
3. remap 可能让直接指针悬空
4. copy-on-write 提交本来就需要写出新页，而不是原地覆盖旧页

所以 BoltDB 的选择是：

1. 读的时候仍然以 page 为事实来源
2. 一旦某个位置需要修改，就把它反序列化成内存 node
3. 后续所有结构调整都在 node 上完成
4. commit/spill 时再把 node 写回新分配的 page

这个 node 本质上就是 page 的可变形态。

它持有：

1. parent
2. children
3. inodes
4. pgid
5. isLeaf
6. unbalanced / spilled

于是 page 世界和 node 世界的分工就非常清楚：

1. page 是磁盘布局与只读事实
2. node 是写事务期间的可编辑中间表示

6. Put()、Delete() 到底改了什么

6.1 Put() 并不立刻写 page

Bucket.Put() 做的事情其实很少：

1. 用 cursor 定位 key
2. 检查是否与 bucket value 冲突
3. cloneBytes(key)
4. 调 c.node().put(...)

也就是说，Put() 真正改的是当前 leaf 对应的内存 node 的 inodes，而不是磁盘页。

这意味着提交前的很多更新只是在累计“树结构变更意图”。

6.2 Delete() 也只是标记 node 失衡

node.del() 删除 inode 后，会把 n.unbalanced = true。

这就说明 BoltDB 的删除策略是两阶段的：

1. 逻辑删除时，只先从当前 node 的 inode 列表去掉 key
2. 真正的树形恢复工作，放到 commit 前统一 rebalance()

这比“每删一个 key 就立刻自底向上修树”更适合 BoltDB 的事务模型，因为它可以把一批变更聚合后再处理。

代价是 commit 阶段的工作会更重，但整体逻辑更整洁。

7. split：一个 node 太大时，BoltDB 如何把它拆开

7.1 split 不是按“中间元素一刀切”，而是按填充率阈值计算

splitTwo() 并不是简单取一半。它先根据 Bucket.FillPercent 算出阈值：

threshold := int(float64(pageSize) * fillPercent)

然后通过 splitIndex() 找到一个既满足：

1. 左右两边都保留最少 key 数
2. 左页大小尽量不超过阈值

的分割点。

这说明 BoltDB 的 split 目标不是“元素数平均”，而是“页利用率合理”。

默认 FillPercent = 0.5，也就是尽量半满。

为什么默认要保守一点？因为如果页刚写满，后续再插入几乎必 split；预留一些空间，能减少写放大。

7.2 split 会在父节点中插入新的边界键

当 node 被拆成多个 node 后，每个新 node 在 spill 时都会向父节点写入：

1. 自己的首 key
2. 自己的新 pgid

于是父 branch page 的导航边界就被更新了。

这里非常能体现 B+Tree 的本质：

父节点存的不是“孩子的摘要统计”，而是“孩子子树的边界 key + 指针”。

7.3 root split 会生成新 root

如果根节点 split，源码会创建一个没有 parent 的新 parent，然后继续 spill。

最终旧根不再是根，新 parent 获得自己的 pgid，bucket 的 root 指向它。

这就是树高增长的过程。

BoltDB 并没有为 root 特殊定义另一套结构，而是沿用统一的 node/page 规则，只在“无 parent 时补 parent”这一步做特殊处理。

8. rebalance：删除之后，BoltDB 如何避免出现太瘦的节点

8.1 rebalance 的触发条件比“低于半满”更宽松

rebalance() 并不是经典教材里那种“低于 50% 就借位/合并”。源码里的判断更保守：

1. 如果节点尺寸仍高于 pageSize / 4
2. 并且 key 数量仍高于最小要求

那它就先不动。

这说明 BoltDB 更关注“别太稀烂”，而不是严格追求教科书式平衡。

这很符合工程权衡：

1. 少一点重排，提交更快
2. 允许一定碎片和不均匀
3. 只在明显不合理时做合并

8.2 root 的 rebalance 有特殊坍缩逻辑

如果 root 是 branch，且只剩一个 child，BoltDB 会把 child 提升上来，直接覆盖 root 的内容。

这本质上是在做树高收缩。

否则如果删除导致根下只剩单一路径，树会长期多一层无意义 branch。

8.3 非根节点 rebalance 主要就是“跟兄弟合并”

当前节点过小后，会选择左兄弟或右兄弟作为目标，把 inode 并过去，然后在父节点删掉对应边界项。

所以 rebalance 的本质不是复杂的“局部借位舞蹈”，而是：

1. 能留就留
2. 太小就并
3. 并完递归修 parent

这种策略和 BoltDB 的单 writer 模型高度匹配。它不需要为高并发写入优化局部操作粒度，更看重实现简单和提交阶段整体正确性。

9. spill() 是第二篇最关键的函数

如果说 cursor 是读路径核心，那 spill() 就是写路径里连接“内存树”和“磁盘页”的桥。

它做了几件大事：

1. 先递归 spill 子 bucket
2. 再 spill 当前 bucket 的 root node
3. node 如有旧 pgid，先把旧页加入 freelist pending
4. 为新 node 分配新 page
5. 把 node 序列化写入 page
6. 更新父节点中的边界 key 和 pgid
7. 若根发生 split，继续向上 spill 新 root

这里你应该已经能看出 BoltDB 的 copy-on-write 风格了：

1. 旧页不是被覆盖，而是被“宣布为将来可回收”
2. 新结构总是写到新 page
3. 最后只需把 bucket root / meta root 切到新树上

这就是第三篇提交路径的前半段基础。

10. 站在源码视角，重新理解 Bucket 的 API 语义

到这里再回看常用 API，会更清楚它们到底代表什么：

1. Bucket.Get()：一次基于 cursor 的有序查找
2. Bucket.Put()：修改当前 leaf 对应 node 的 inode 集合
3. Bucket.Delete()：逻辑删除并标记后续 rebalance
4. Bucket.CreateBucket()：插入一个带 bucketLeafFlag 的特殊 leaf value
5. Bucket.Bucket()：把这个特殊 value 重新解释成子树入口

换句话说，BoltDB 的 bucket API 表面上在操作“命名空间”，底层上一直在操作：

1. leaf value 的特殊编码
2. B+Tree 节点的修改与重写

这套抽象非常省：只用一套树结构，同时表达普通 KV 和嵌套 bucket。

11. 这一篇最该记住的几个结论

1. Bucket 不是独立 page 类型，而是“子树根描述符”
2. branch page 只负责导航，leaf page 才保存真实 key/value
3. 子 bucket 在父 leaf 中其实是一种特殊 value，并通过 bucketLeafFlag 区分
4. Cursor 用路径栈把 seek、scan、prev/next 全统一起来了
5. 写事务不直接编辑 page，而是把 page materialize 为可修改的 node
6. split / rebalance / spill 共同构成了从“内存变更”到“新页布局”的完整管道

到这一步，我们已经能看懂 BoltDB 如何组织一棵树，也能理解为什么它的读路径短、写路径清楚。

最后一篇要收尾三个更硬核的问题：

1. 一次 Commit() 到底按什么顺序写盘
2. freelist 为什么要区分 available 和 pending
3. BoltDB 没有 WAL，却为什么还能靠双 meta page 恢复到一致状态

继续阅读：BoltDB 源码分析（三）：提交、freelist 与崩溃恢复