boltdb 源码导读（二）：boltdb 索引设计

boltdb 是市面上为数不多的纯 go 语言开发的、单机 KV 库。boltdb 基于 Howard Chu's LMDB 项目 ，实现的比较清爽，去掉单元测试和适配代码，核心代码大概四千多行。简单的 API、简约的实现，也是作者的意图所在。由于作者精力所限，原 boltdb 已经封版，不再更新。若想改进，提交新的 pr，建议去 etcd 维护的 fork 版本 bbolt。
为了方便，本系列导读文章仍以不再变动的原 repo 为基础。该项目麻雀虽小，五脏俱全，仅仅四千多行代码，就实现了一个基于 B+ 树索引、支持一写多读事务的单机 KV 引擎。代码本身简约朴实、注释得当，如果你是 go 语言爱好者、如果对 KV 库感兴趣，那 boltdb 是不可错过的一个 repo。
本系列计划分成三篇文章，依次围绕数据组织、索引设计、事务实现等三个主要方面对 boltdb 源码进行剖析。由于三个方面不是完全正交解耦的，因此叙述时会不可避免的产生交织，读不懂时，暂时略过即可，待有全貌，再回来梳理。本文是篇， boltdb 数据组织。

概览

数据库中常用的索引设计有两种，一个是 B+ 树，一个是 LSM-tree。B+ 树比较经典，比如说传统单机数据库 mysql 就是 B+ 树索引，它对快速读取和范围查询（range query）比较友好。 LSM-tree 是近年来比较流行的索引结构，Bigtable、LevelDB、RocksDB 都有它的影子；前面文章也有提到，LSM-tree 使用 WAL 和多级数据组织以牺牲部分读性能，换来强悍的随机写性能。因此，这也是一个经典的取舍问题。

BoltDB 在逻辑上以桶来组织数据，一个桶可以看做一个命名空间，是一组 KV 对的集合，和对象存储的桶概念类似。每个桶对应一棵 B+ 树，命名空间是可以嵌套的，因此 BoltDB 的 Bucket 间也是允许嵌套的。在实现上来说，子 bucket 的 root node 的 page id 保存在父 bucket 叶子节点上实现嵌套。

每个 db 文件，是一组树形组织的 B+ 树。我们知道对于 B+ 树来说，分支节点用于查找，叶子节点存数据。

1. 顶层 B+ 树，比较特殊，称为 root bucket，其所有叶子节点保存的都是子 bucket B+ 树根的 page id 。
2. 其他 B+ 树，不妨称之为 data bucket，其叶子节点可能是正常用户数据，也可能是子 bucket B+ 树根的 page id。

相比普通 B+ 树，boltdb 的 B+ 树有几点特殊之处：

1. 节点的分支个数不是一个固定范围，而是依据其所存元素大小之和来限制的，这个上限即为页大小。
2. 其分支节点（branch node）所存分支的 key，是其所指向分支的小 key。
3. 所有叶子节点并没有通过链表首尾相接起来。
4. 没有保证所有的叶子节点都在同一层。

在代码组织上，boltdb 索引相关的源文件如下：

1. bucket.go：对 bucket 操作的高层封装。包括kv 的增删改查、子bucket 的增删改查以及 B+ 树拆分和合并。
2. node.go：对 node 所存元素和 node 间关系的相关操作。节点内所存元素的增删、加载和落盘，访问孩子兄弟元素、拆分与合并的详细逻辑。
3. cursor.go：实现了类似迭代器的功能，可以在 B+ 树上的叶子节点上进行随意游走。

本文将由主要分三部分，由局部到整体来一步步揭示 BoltDB 是如何进行索引设计的。首先会拆解树的基本单元，其次剖析 bucket 的遍历实现，后分析树的生长和平衡过程。

作者：青藤木鸟 https://www.qtmuniao.com/2020/12/14/bolt-index-design, 转载请注明出处

基本单元——节点（Node）

B+ 树的基本构成单元是节点（node），对应在上一篇中提到过文件系统中存储的页（page），节点包括两种类型，分支节点（branch node）和叶子节点（leaf node）。但在实现时，他们复用了同一个结构体，并通过一个标志位 isLeaf 来区分：

// node 表示内存中一个反序列化后的 page
type node struct {
    bucket     *Bucket   // 其所在 bucket 的指针
    isLeaf     bool      // 是否为叶子节点

    // 调整、维持 B+ 树时使用
    unbalanced bool      // 是否需要进行合并
    spilled    bool      // 是否需要进行拆分和落盘

    key        []byte    // 所含个元素的 key
    pgid       pgid      // 对应的 page 的 id

    parent     *node     // 父节点指针
    children   nodes     // 孩子节点指针（只包含加载到内存中的部分孩子）

    inodes     inodes    // 所存元素的元信息；对于分支节点是 key+pgid 数组，对于叶子节点是 kv 数组
}