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+ 树来说，分支节点用于查找，叶子节点存数据。
- 顶层 B+ 树，比较特殊，称为 root bucket，其所有叶子节点保存的都是子 bucket B+ 树根的 page id 。
- 其他 B+ 树，不妨称之为 data bucket，其叶子节点可能是正常用户数据，也可能是子 bucket B+ 树根的 page id。
相比普通 B+ 树，boltdb 的 B+ 树有几点特殊之处：
- 节点的分支个数不是一个固定范围，而是依据其所存元素大小之和来限制的，这个上限即为页大小。
- 其分支节点（branch node）所存分支的 key，是其所指向分支的最小 key。
- 所有叶子节点并没有通过链表首尾相接起来。
- 没有保证所有的叶子节点都在同一层。
在代码组织上，boltdb 索引相关的源文件如下：
- bucket.go：对 bucket 操作的高层封装。包括kv 的增删改查、子bucket 的增删改查以及 B+ 树拆分和合并。
- node.go：对 node 所存元素和 node 间关系的相关操作。节点内所存元素的增删、加载和落盘，访问孩子兄弟元素、拆分与合并的详细逻辑。
- 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 数组 }
node/page 转换
page 和 node 的对应关系为：文件系统中一组连续的物理 page，加载到内存成为一个逻辑 page ，进而转化为一个 node。下图为一个在文件系统上占用两个 pagesize 空间的一段连续数据 ，首先 mmap 到内存空间，转换为 page 类型，然后通过 node.read 转换为 node 的过程。
其中 node.read 将 page 转换为 node 的代码如下：
// read 函数通过 mmap 读取 page，并转换为 node func (n *node) read(p *page) { // 初始化元信息 n.pgid = p.id n.isLeaf = ((p.flags & leafPageFlag) != 0) n.inodes = make(inodes, int(p.count)) // 加载所包含元素 inodes for i := 0; i < int(p.count); i++ { inode := &n.inodes[i] if n.isLeaf { elem := p.leafPageElement(uint16(i)) inode.flags = elem.flags inode.key = elem.key() inode.value = elem.value() } else { elem := p.branchPageElement(uint16(i)) inode.pgid = elem.pgid inode.key = elem.key() } _assert(len(inode.key) > 0, "read: zero-length inode key") } // 用第一个元素的 key 作为该 node 的 key，以便父节点以此作为索引进行查找和路由 if len(n.inodes) > 0 { n.key = n.inodes[0].key _assert(len(n.key) > 0, "read: zero-length node key") } else { n.key = nil } }
node 元素 inode
inode 表示 node 所含的内部元素，分支节点和叶子节点也复用同一个结构体。对于分支节点，单个元素为 key+引用；对于叶子节点，单个元素为用户 kv 数据。
注意到这里对其他节点的引用类型为 pgid ，而非 node*。这是因为 inode 中指向的元素并不一定加载到了内存。boltdb 在访问 B+ 树时，会按需将访问到的 page 转化为 node，并将其指针存在父节点的 children 字段中， 具体的加载顺序和逻辑在后面小结会详述。
type inode struct { // 共有变量 flags uint32 key []byte // 分支节点使用 pgid pgid // 指向的分支/叶子节点的 page id // 叶子节点使用 value []byte // 叶子节点所存的数据 }
inode 会在 B+ 树中进行路由——二分查找时使用。
新增元素
所有的数据新增都发生在叶子节点，如果新增数据后 B+ 树不平衡，之后会通过 node.spill 来进行拆分调整。主要代码如下：
// put inserts a key/value. func (n *node) put(oldKey, newKey, value []byte, pgid pgid, flags uint32) { // 找到插入点 index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 }) // 如果 key 是新增而非替换，则需为待插入节点腾空儿 exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey)) if !exact { n.inodes = append(n.inodes, inode{}) copy(n.inodes[index+1:], n.inodes[index:]) } // 给要替换/插入的元素赋值 inode := &n.inodes[index] inode.key = newKey // ... }
该函数的主干逻辑比较简单，就是二分查找到待插入位置，如果是覆盖写则直接覆盖；否则就要新增一个元素，并整体右移，腾出插入位置。但是该函数签名很有意思，同时有 oldKey 和 newKey ，开始时感觉很奇怪。其调用代码有两处：
- 在叶子节点插入用户数据时，
oldKey等于newKey，此时这两个参数是有冗余的。 - 在
spill阶段调整 B+ 树时，oldKey可能不等于newKey，此时是有用的，但从代码上来看，用处仍然很隐晦。
在和朋友讨论后，大致得出如下结论：为了避免在叶子节点最左侧插入一个很小的值时，引起祖先节点的 node.key 的链式更新，而将更新延迟到了最后 B+ 树调整阶段（spill 函数）进行统一处理 。此时，需要利用 node.put 函数将最左边的 node.key 更新为 node.inodes[0].key：
// 该代码片段在 node.spill 函数中 if node.parent != nil { // 如果不是根节点 var key = node.key // split 后，最左边 node if key == nil { // split 后，非最左边 node key = node.inodes[0].key } node.parent.put(key, node.inodes[0].key, nil, node.pgid, 0) node.key = node.inodes[0].key }
节点遍历
由于 Golang 不支持 Python 中类似 yield 机制，boltdb 使用栈保存遍历上下文实现了一个树节点顺序遍历的迭代器：cursor。在逻辑上可以理解为对某 B+ 树叶子节点所存元素遍历的迭代器。之前提到，boltdb 的 B+ 树没有使用链表将所有叶子节点串起来，因此需要一些额外逻辑来进行遍历中各种细节的处理。
这么实现增加了遍历的复杂度，但是减少了维持 B+ 树平衡性质的难度，也是一种取舍。
cursor 和某个 bucket 绑定，实现了以下功能，需要注意，当遍历到的元素为嵌套 bucket 时，value = nil。
type Cursor func (c *Cursor) Bucket() *Bucket // 返回绑定的 bucket func (c *Cursor) Delete() error // 删除 cursor 指向的 key func (c *Cursor) First() (key []byte, value []byte) // 定位到并返回该 bucket 第一个 KV func (c *Cursor) Last() (key []byte, value []byte) // 定位到并返回该 bucket 最后一个 KV func (c *Cursor) Next() (key []byte, value []byte) // 定位到并返回该 bucket 下一个 KV func (c *Cursor) Prev() (key []byte, value []byte) // 定位到并返回该 bucket 前一个 KV func (c *Cursor) Seek(seek []byte) (key []byte, value []byte) // 定位到并返回该 bucket 内指定的 KV
由于 boltdb 中 B+ 树左右叶子节点并没有通过链表串起来，因此遍历时需要记下遍历路径以进行回溯。其结构体如下：
type Cursor struct { bucket *Bucket // 使用该句柄来进行 node 的加载 stack []elemRef // 保留路径，方便回溯 }
elemRef 结构体如下，page 和 node 是一一对应的，如果 page 加载到了内存中（通过 page 转换而来），则优先使用 node，否则使用 page；index 表示路径经过该节点时在 inodes 中的位置。
type elemRef struct { page *page node *node index int }
