本期我们继续延续 etcd 存储引擎系列的话题. 在该系列中，我们以 boltdb 作为 b+树 工程化落地的学习案例，该项目开源地址为：https://github.com/etcd-io/bbolt，go 语言纯度接近 100%. （本系列涉及走读的 boltdb 源码版本为 v1.3.8）
下面是本专题的分享节奏，本文是其中的第三篇——b+树实现篇：
本文我们聚焦于 boltdb 针对 b+ 树的技术实现细节，b+ 树是 b 树的迭代升级版本，因此，我们有必要先理清楚关于b树和b+树的理论模型和核心性质.
首先，我们需要对计算机存储模型有个基本的概念认知. 常用的计算机存储介质分为内存 memory (全称 main memory) 和磁盘 disk (又称外存 external memory)：
从性能层面，我们补充一些定量描述：访问一次内存的耗时大约为 100 ns 的量级，而访问一次磁盘的耗时可能处在 10 ms 的量级，两者之间的速度差距达到 10万倍.
举个更生动的例子来反映两者的效率差距——倘若访问一次内存的耗时是 1 秒，那么访问一次磁盘的耗时约为 1.2 天左右.
针对于数据库系统的设计来说，通常宁可接受访问内存 100次也要避免访问磁盘 1 次. 因此，提升性能的关键点很大程度上在于如何减少访问磁盘的 io 次数，而不在于如何提效磁盘访问行为本身. 这个过程中也需要结合局部性原理的应用，尽可能把需要用到的热数据缓存在内存中加以复用.
在这样的前提之下，类似 b 树这样的多叉搜索树数据结构，是很适用于作为读密集型数据库或文件系统的索引模型的. 虽然在写流程中，涉及到对索引结构的调整存在一定的代价，但是在读流程中，每与索引的一次交互对应一次磁盘 io，检索进度也会因此向下递进一层，最坏的情况下在来到叶子节点时也必然会得到检索结果. 由于 b 树形状扁平，高度很低，因此对应的磁盘 io 次数也会很少.
下面我们捋一下有关于 b 树的定义.
b 树，英文名为 b-tree，因此很多人也把其称为 b-(jiǎn)树，但大家需要明白，其实说的是同一个东西. b 树是一种自平衡的多叉搜索树，通过维护有序的数据结构，保证能够基于对数级别的时间复杂度完成搜索、插入和删除操作.
下面是详细定义：
b 树是一种平衡多叉搜索树，伴随着每个 b 树实例都有一个阶数的概念，针对于一棵 n 阶 b 树，需要满足：
一棵 4 阶 b 树的示意图如下所示：
在基础定义之上，再针对其中涉及到的几个核心概念展开说明：
通过下方的示意图能看到，【10,12,14】节点正好达到了阶数 4 的上限，其拥有的子节点数 量恰好为 4 个，如果再多的话就需要调整处理了.
下面给大家提供一个可用于可视化动态展示 b 树构造进程的网站，传送门如下：
b 树可视化—— https://www.cs.usfca.edu/~galles/visualization/BTree.html
为了帮助大家进一步加深对 b 树的理解，下面给出几个详细的操作案例加以说明：
首先针对 b 树的元素插入流程，核心步骤如下：
上述 step4 的步骤称之为 “spill”，它可能进一步引起父节点元素数量超限，因此会针对父节点递归执行 step4. 最坏的情况下，可能一直分裂到根节点，最终生成新的根节点实例，导致 b 树整体高度加 1.
下面是针对一棵 3 阶 b 树的元素插入案例：
下面针对 b 树的元素删除流程进行梳理，这一块儿相对复杂一些，核心步骤如下：
step4-step6 的流程称之为“rebalance”. 如果执行到 step6 ，则需要检查父节点状况是否满足条件，如果不满足，则以父节点为起点沿 step4 开始递归执行. 最不利的情况可能层层向上递归合并，最终 b 树的整体高度可能会下降.
下面是针对一棵 5 阶 b 树的元素删除案例：
相信通过上面补充的两个案例，大家对 b 树的特性和机制都有了进一步的认识，下面我们以 b 树为基础，展开关于 b+ 树的介绍.
b+树继承了 b 树的绝大多数特性，并在基础上作了几点调整：
下面给出一个 3 阶 b+ 树示意图，展示如下：
下面是个可用于可视化动态展示 b+ 树构造进程的网站，传送门如下：
b+ 树可视化—— https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html
我们通常认为，b+ 树相比于 b 树更加适合于用于作为读密集型数据库的索引结构，其原因就在于：
至此,我们介绍完有关 b+ 树的理论部分，下面我们就一起进入到 boltdb 的源码中，探讨有关于 b+ 树的具体实现细节.
有关于 b+ 树的定义是偏理论的，在真正付诸实践时，boltdb 作了如下几处调整：
为了降低模型复杂度，boltdb 没有将 b+ 树叶子节点通过单向指针串联成链，而是引入了一个游标结构，通过记录检索移动路径结合路径回溯的方式，来支持范围检索的诉求.
由于 boltdb 中，kv 数据是不定长的，因此不适合通过阶数来限定节点容量. 这里采取的方式是启用了数据填充率（填充率 fillPercent = dataSize / pageSize） . 当某个节点数据填充率 <= 0.25 时，需要进行 rebalance，使节点变得更加丰满；当某个节点数据填充率大于用户设定的阈值时，需要进行 spill，需要保证拆分后的节点不能过于臃肿.
boltdb 针对 b+ 树的实现根据存储介质可以分为磁盘与内存两个版本. 磁盘上的是持久化的 b+树，需要严格保证其平衡性，而内存中的是读写事务运行时使用的 b+ 树副本（copy-on-write），基于懒加载机制反序列得到，在运行过程中不会因为单笔改动而频繁执行 reblance 和 spill 操作，而是在事务提交时，一次性完成 b+ 树的自平衡调整操作，最后再将完整的内容持久化为稳定版本的“磁盘的树”.
上图展示了磁盘上的 b+ 树的实现细节，一切的根源要从 db 实例的 meta page 中说起. 我们知道每个 db 实例会持有两个轮换使用的 meta page，代码如下：
// db 实例
type DB struct {
// ...
// 两个轮换使用的 meta page
meta0 *meta
meta1 *meta
// ...
}每个 meta page 对应数据的一个持久化版本，其中持有一个 root bucket：
type meta struct {
// ...
// 始祖 bucket
root bucket
// ...
}一个 bucket 对应一张表，其中通过 root 字段标识了表中 b+ 树根节点对应的 page id：
// bucket header，表示一张表
type bucket struct {
// b+ 树根节点 page id
root pgid
// ...
}通过 page id 可以得到每个 page 对应的 header，进一步可通过 ptr 取得 page body：
// page header，当 flags 为 branch 或 leaf 时，对应一个磁盘上的 b+ 树节点
type page struct {
id pgid // page id
flags uint16 // page 类型，b+ 树枝干节点对应为 branch；叶子节点对应为 leaf
count uint16 // page 内的数据量，对应 b+ 树节点表示节点内 key 的数量
ptr uintptr // page body 的起始位置
// ...
}b+ 树中的持久化节点分为 branch page（枝干节点）和 leaf page（叶子节点）两种类型，采用 shadow paging 技术标识每组元素的所在位置.
针对 branch page 的结构示意图如上，其中通过 branchPageElement 标识每个内部元素的信息，其中通过 pos 和 ksize 指向的 key 值就是枝干节点中的索引，pgid 就是指向子节点的指针：
// 在 branch page 中标识一组 key 的 header
type branchPageElement struct {
pos uint32 // key 的起始位置
ksize uint32 // key 的大小，单位 byte
pgid pgid // key 映射子节点的 page id
}从 branch page 的 header 出发，通过 index 可以获取到指定的 branchPageElement：
// 获取 branch page 中指定 index 的 branchPageElement
func (p *page) branchPageElement(index uint16) *branchPageElement {
// 通过偏移地址的方式获取
return (*branchPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
unsafe.Sizeof(branchPageElement{}), int(index)))
}获取到 branchPageElement 后，可以通过 key 方法读取键值，以及通过成员属性直接获取对应子节点的 pgid：
// 获取到 header 后，读取 branch page 对应的 key 值
func (n *branchPageElement) key() []byte {
// 结合 pos 和 ksize，通过偏移地址获得
return unsafeByteSlice(unsafe.Pointer(n), 0, int(n.pos), int(n.pos)+int(n.ksize))
}针对 element page 的结构示意图如上，其中通过 leafPageElement 标识每个内部元素的信息，其中通过 pos 和 ksize 指向 key 值，通过 pos+ksize 结合 vsize 指向 value， 对应的就是叶子节点中的一组 kv 数据：
type leafPageElement struct {
flags uint32 // 标识 kv 对是不是 bucket 类型
pos uint32 // key 起始地址
ksize uint32 // key 的大小，单位 byte
vsize uint32 // value 的大小，单位 byte. value 起始地址为 pos+ksize
}从 branch page 的 header 出发，通过 index 可以获取到指定的 leafPageElement：
// 获取 leaf page 中指定 index 的 leafPageElement
func (p *page) leafPageElement(index uint16) *leafPageElement {
return (*leafPageElement)(unsafeIndex(unsafe.Pointer(p), unsafe.Sizeof(*p),
leafPageElementSize, int(index)))
}获取到 leafPageElement 后，通过地址偏移的方式，就能获取到叶子节点中的指定 kv 对了：
// 获取到 header 后，读取 leaf page 对应的 key 值
func (n *leafPageElement) key() []byte {
// 通过偏移地址读取
i := int(n.pos)
j := i + int(n.ksize)
return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
}// 获取到 header 后，读取 leaf page 对应的 value 值
func (n *leafPageElement) value() []byte {
// 通过偏移地址读取. value 起始地址为 pos+ksize，因为 value 和 key 是紧挨着的
i := int(n.pos) + int(n.ksize)
j := i + int(n.vsize)
return unsafeByteSlice(unsafe.Pointer(n), 0, i, j)
}综上所述，磁盘中的 b+ 树通过一系列 page 作为节点，枝干节点通过一系列 branchPageElement 建立多叉索引的拓扑结构，通过每个 branchPageElement 中的 pgid 找到指向子节点的引用；叶子节点中则通过一系列 leafPageElement 找到多组 kv 数据的地址
上图展示了内存中的 b+ 树的实现细节，内存中的 b+ 树属于运行时拷贝建立的一个中间态副本，需要从事务实例中开始追溯：
每个事务会基于 copy on write 机制，在内存中拷贝生成一份 root Bucket 副本：
// 事务
type Tx struct {
// ...
// 根 bucket. 是基于 copy on write 在内存中拷贝生成的一份副本
root Bucket
// ...
}每个 Bucket 副本实例中，会持有内存中 b+ 树根节点副本的引用：
// 事务运行时，基于 copy on write 在内存中拷贝生成的一份副本
type Bucket struct {
// ...
rootNode *node // 内存中的 b+ 树根节点
nodes map[pgid]*node // 读写事务过程中，反序列化过的 node 缓存于此
// ...
}每个 node 都是基于 branch page 或者 leaf page 反序列化到内存中的一个 b+ 树节点副本，反序列化流程是完全基于懒加载机制推动的，只要在涉及到对该节点内容进行修改时，才会执行该操作：
// 内存中反序列化的一个 b+ 树节点副本
type node struct {
bucket *Bucket // 从属的 bucket
isLeaf bool // 标识其是叶子节点还是枝干节点
unbalanced bool // 标记节点是否有删除过数据，需要在持久化前进行 rebalance 操作
spilled bool // 标记节点是否已经在事务提交过程中执行过 spill 操作
key []byte // 节点中最小的 key
pgid pgid // 节点对应的 page id. 标识其来源，实际上在持久化时会被序列化到一个新的 page 副本中(copy-on-write)
parent *node // 父节点
children nodes // 反序列化过的子节点列表
inodes inodes // 节点内部数据列表. 叶子节点为 key-value 对，枝干节点为 key-child 对
}如果 node 为枝干节点的副本，则会通过一系列 inode 记录指向子节点的引用（指向的是 page，需要修改的时候才会反序列化成 node）；
如果 node 为叶子节点的副本，则会通过一系列 inode 记录其中存储的 kv 数据
// b+ 树节点内部的一笔数据. 叶子节点为 key-value 对，枝干节点为 key-child 对
type inode struct {
flags uint32 // 标识 value 是否为 bucket
key []byte // 标识键 key
pgid pgid // 如果 inode 从属于枝干节点，则通过 pgid 指向 child page
value []byte // 如果 inode 从属于叶子节点，则直接通过 value 取值
}boltdb 中的 bucket 类似于表的概念，每个 bucket 都会对应一棵独立的 b+ 树.
Bucket 类对应表示一个内存中的 bucket 副本，其核心字段含义展示如上图，其中还包含一个 FillPercent 字段，表示 Bucket 下每个 node 副本在 spill 过程数据填充率需要达到的阈值，默认值为 0.5.
// bucket boltdb 中隔离的一个数据组，可简单理解为表.
// Bucket 是在有事务启动时，基于 copy-on-write 机制生成的一份 bucket 副本
type Bucket struct {
*bucket // bucket header. 需要持久化的数据
tx *Tx // Bucket 从属的事务.
// ...
rootNode *node // Bucket 下的 b+ 树根节点
nodes map[pgid]*node // 事务操作 Bucket 过程中，反序列化过的 node
// bucket 下的 node 填充率阈值. spill 操作时，需要保证拆分出的新节点填充率高于该值
FillPercent float64
}
// 默认 bucket 填充率
const DefaultFillPercent = 0.5游标 cursor 是 boltdb 用于辅助完成范围操作的检索工具，它会通过一个栈结构 stack 记录某次流程在 b+ 树上的移动路径.
// 与 b+ 树交互时使用的游标工具，通过栈结构记录了检索过程中的移动路径
type Cursor struct {
bucket *Bucket
stack []elemRef // 记录移动路径的栈
}移动路径中的每个 step 对应为一个 elemRef 实例， 其中通过 page 或 node 指向某个 b+ 树节点，通过 index 指向节点中的某个 key.
// cursor 移动过程中的一个 step
type elemRef struct {
page *page // step 位于哪个 page(node 未序列化时使用)
node *node // step 位于哪个 node
index int // step 踩在节点中的哪个 key-value(child)
}// 生成一个新的 bucket 下的游标实例
func (b *Bucket) Cursor() *Cursor {
// ...
// 构造并返回游标实例
return &Cursor{
bucket: b,
stack: make([]elemRef, 0),
}
}从本章开始，我们一起梳理一下，boltdb 中涉及到 b+ 树数据结构的 crud 流程.
b+ 树的 crud 很大程度上都是借助游标 cursor 加以实现的，我们首先要理清 cursor 的作用机制，这需要从一个非常核心的方法——cursor.seek 开始谈起：
seek 主干流程分为三个步骤：
func (c *Cursor) seek(seek []byte) (key []byte, value []byte, flags uint32) {
// 清空栈结构，从头开始检索
c.stack = c.stack[:0]
// 移动游标沿路检索，直到找到目标 key 应该存在的位置
c.search(seek, c.bucket.root)
// 返回 cursor 当前指向位置对应的 key value 值
return c.keyValue()
}search 方法的作用是，沿着 pgId 对应节点作为起点出发，将 cursor 移动到 <= key 且最接近 key 的位置：
func (c *Cursor) search(key []byte, pgId pgid) {
// 根据 pgid 在 bucket 中获取节点. 如果反序列化过 node 就用 node，否则就用 page
p, n := c.bucket.pageNode(pgId)
// 包装成移动路径中的一个 step
e := elemRef{page: p, node: n}
// 追加到记录移动路径对应的栈结构中
c.stack = append(c.stack, e)
// 如果已经来到叶子节点，则在节点内部检索结果
if e.isLeaf() {
c.nsearch(key)
return
}
// 否则继续在枝干节点上检索
if n != nil {
c.searchNode(key, n)
return
}
c.searchPage(key, p)
}倘若来到叶子节点，通过 nsearch 方法在其中检索数据：
通过这个 nsearch 流程也能进一步看出内存中 b+ 树副本的懒加载机制，在读流程检索 b+ 树的过程中，哪怕某个节点没有反序列化过也没有关系，可以通过获取对应 page 完成数据的检索操作.
// 在当前栈顶 step 所在的叶子节点中检索，使得 index 指向首个 >= key 的位置
func (c *Cursor) nsearch(key []byte) {
// 获取栈顶 step(当前所在位置)
e := &c.stack[len(c.stack)-1]
p, n := e.page, e.node
// 如果有反序列化好的 node，则使用 node
if n != nil {
// 二分查找，找到首个 >= key 的 inode 对应的 index
index := sort.Search(len(n.inodes), func(i int) bool {
return bytes.Compare(n.inodes[i].key, key) != -1
})
e.index = index
return
}
// node 未反序列化，则通过 page 来检索
// 获取 leaf page 下的全量 leafPageElement
inodes := p.leafPageElements()
// 二分查找，找到首个 >= key 的 leafPageElement 对应的 index
index := sort.Search(int(p.count), func(i int) bool {
return bytes.Compare(inodes[i].key(), key) != -1
})
e.index = index
}倘若当前还处在枝干节点，则根据当前节点是否以反序列化成 node，选择调用 searchNode 或者 searchPage 方法来完成后续检索流程:
// 当前枝干节点已反序列化成 node
func (c *Cursor) searchNode(key []byte, n *node) {
// 是否与某个 inode 的 key 相等
var exact bool
// 二分检索，找到首个 >= key 的 inode
index := sort.Search(len(n.inodes), func(i int) bool {
// 对比 inode 的 key 和目标 key
ret := bytes.Compare(n.inodes[i].key, key)
if ret == 0 { // 如果相同，标识 exact 为 true
exact = true
}
// 找到首个 >= 目标 key 的 inode
return ret != -1
})
// 如果 inode 首个 key 不相同而是更大，则 index 往前倒退一位
if !exact && index > 0 {
index--
}
// 记录当前 step 指向的 index 位置
c.stack[len(c.stack)-1].index = index
// 递归调用 search 方法，以子节点为起点开始下一轮检索
c.search(key, n.inodes[index].pgid)
}// 当前枝干节点未反序列化成 node
func (c *Cursor) searchPage(key []byte, p *page) {
// 获取 branch page 内的所有 branchPageElement，通过地址偏移的方式
inodes := p.branchPageElements()
// 是否与某个 inode 的 key 相等
var exact bool
// 二分检索，找到首个 >= key 的 inode
index := sort.Search(int(p.count), func(i int) bool {
// 对比 inode 的 key 和目标 key
ret := bytes.Compare(inodes[i].key(), key)
// 和 inode 的 key 相同，exact 置为 true
if ret == 0 {
exact = true
}
// 返回首个 >= key 的 inode
return ret != -1
})
// 如果 inode 首个 key 不相同而是更大，则 index 往前倒退一位
if !exact && index > 0 {
index--
}
// 记录当前 step 指向的 index 位置
c.stack[len(c.stack)-1].index = index
// 递归调用 search 方法，以子节点为起点开始下一轮检索
c.search(key, inodes[index].pgid)
}当 cursor 移动到目标位置后，可以通过 keyValue 方法取出对应的 kv 结果：
func (c *Cursor) keyValue() ([]byte, []byte, uint32) {
// 获取栈顶的 step
ref := &c.stack[len(c.stack)-1]
// 如果 step 所在的节点没有数据，或者指向的 index 越界，则返回 nil
if ref.count() == 0 || ref.index >= ref.count() {
return nil, nil, 0
}
// 倘若节点反序列已经反序列化成 node，则根据 index 获取到 inode，并返回 key value
if ref.node != nil {
inode := &ref.node.inodes[ref.index]
return inode.key, inode.value, inode.flags
}
// 未反序列化成 node，则根据 index 获取到对应的 leafPageElement
elem := ref.page.leafPageElement(uint16(ref.index))
// 通过地址偏移的方式，获取到 key value
return elem.key(), elem.value(), elem.flags
}cursor.node 方法，用于返回游标移动路径中，最后一个叶子节点 node 副本：
func (c *Cursor) node() *node {
// ...
// 1 返回栈顶对应的 node. 如果 node 已经反序列化了并且是叶子节点，直接返回即可
if ref := &c.stack[len(c.stack)-1]; ref.node != nil && ref.isLeaf() {
return ref.node
}
// 使用 b+ 树根节点进行兜底(倘若一个节点都)
var n = c.stack[0].node
if n == nil {
n = c.bucket.node(c.stack[0].page.id, nil)
}
// 扣除栈顶元素后，后开始正序遍历(从根节点出发)
for _, ref := range c.stack[:len(c.stack)-1] {
// 按照移动路径中每个 step 的 index 指引前进的方向(找到要通往的子节点在父节点 inodes 中的 index)
n = n.childAt(ref.index)
}
// ...
// 返回检索到的 node
return n
}返回 node 中对应 index 的子节点：
func (n *node) childAt(index int) *node {
// ...
return n.bucket.node(n.inodes[index].pgid, n)
}// 从 bucket 中的返回 page 对应的 node 副本. 如果没反序列化过，会进行反序列化
func (b *Bucket) node(pgId pgid, parent *node) *node {
// 如果对应 node 已经在 Bucket 反序列化过，则直接复用
if n := b.nodes[pgId]; n != nil {
return n
}
// 构造 node 副本实例
n := &node{bucket: b, parent: parent}
if parent == nil {
b.rootNode = n
} else {
parent.children = append(parent.children, n)
}
// 兼容 inline bucket 类型
var p = b.page
if p == nil { // 非 inline bucket，则根据 pg id 取出对应的 page
p = b.tx.page(pgId) // 底层基于 pgid + pageSize，在 mmap 中通过地址偏移的方式获取到
}
// 读取 page 内容，反序列化到 node 实例中
n.read(p)
// 缓存 node
b.nodes[pgId] = n
// ...
return n
}通过 Bucket.Put 方法，能够实现往指定表中插入或者更新一组 kv 数据的操作：
// 往 Bucket 下的 b+ 树中写入一笔 kv 对数据.
func (b *Bucket) Put(key []byte, value []byte) error {
// ...
// 1 构造一个新的游标实例
c := b.Cursor()
// 2 借助游标，移动到 key 应该被写入的位置，并且通过栈结构记录过程中的移动路径
k, _, flags := c.seek(key)
// ...
// 3 在对应位置中写入 key-value 对
key = cloneBytes(key)
c.node().put(key, key, value, 0, 0)
return nil
}// 往 node 中插入一组 key-value 对
func (n *node) put(oldKey, newKey, value []byte, pgId pgid, flags uint32) {
// ...
// 找到 node 中首个 >= oldKey 的 inode 对应的 index
index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, oldKey) != -1 })
// exact 标识：index 对应 innode 的 key 是否等于 oldKey
exact := (len(n.inodes) > 0 && index < len(n.inodes) && bytes.Equal(n.inodes[index].key, oldKey))
if !exact { // 倘若不等，则需要在其之前插入一个新的 inode，写入 newKey
n.inodes = append(n.inodes, inode{})
copy(n.inodes[index+1:], n.inodes[index:])
}
// 找到 index 指向的 innode
inode := &n.inodes[index]
// 写入对应的 newKey、value、flags、pgID 等信息
inode.flags = flags
inode.key = newKey
inode.value = value
inode.pgid = pgId
// ...
}通过 Bucket.Gut 方法，能够从表中获取 key 对应的 value：
// 从 Bucket 中获取 key 对应的 value
func (b *Bucket) Get(key []byte) []byte {
// 构造游标，并根据 key 移动到指定位置
k, v, flags := b.Cursor().seek(key)
// 倘若游标所在位置不是叶子节点，说明没有满足要求的 kv 对，返回空
if (flags & bucketLeafFlag) != 0 {
return nil
}
// 游标所在位置 key 不等，说明没有满足要求的 kv 对，返回空
if !bytes.Equal(key, k) {
return nil
}
// 返回 value
return v
}通过 Bucket.Delete 方法，能够实现在表中删除 key 的操作：
// 从 bucket 中删除某个 key
func (b *Bucket) Delete(key []byte) error {
// ...
// 构造 bucket 下的游标实例
c := b.Cursor()
// 移动游标，根据 key 移动到指定位置
k, _, flags := c.seek(key)
// 如果当前所在位置 key 不等，说明 kv 对不存在，返回 nil
if !bytes.Equal(key, k) {
return nil
}
// ...
// 从游标当前所在节点中删除对应的 key
c.node().del(key)
return nil
}// 从 node 副本中删除某个 key
func (n *node) del(key []byte) {
// 在 node 中二分查找，找到首个 >= key 的 inode
index := sort.Search(len(n.inodes), func(i int) bool { return bytes.Compare(n.inodes[i].key, key) != -1 })
// 如果 innode 的 key 不等，说明 key 不存在，直接返回
if index >= len(n.inodes) || !bytes.Equal(n.inodes[index].key, key) {
return
}
// 从 inodes 中删除 key 对应的 innode
n.inodes = append(n.inodes[:index], n.inodes[index+1:]...)
// 设置 node 为 unbalanced 状态，在持久化前需要执行 rebalance 操作
n.unbalanced = true
}针对 b+ 树而言，最复杂的流程莫过于——因为写入或者删除操作导致其平衡性遭到破坏，进一步需要补偿执行的 rebalance 和 spill 操作.
在前文中我也提到了，由于内存中的 b+ 树本质上是一个读写事务在执行过程中建立的一份临时副本，因此为了保证操作性能，在事务运行过程中可以允许这份副本暂时被打破平衡性，但会保证在其因事务提交而被落盘为磁盘上持久化的 b+ 树之时完成平衡性的调整.
在事务提交时，首先会针对内存中的 b+ 树副本执行 rebalance 流程：
func (tx *Tx) Commit() error {
// ...
// rebalance ...
tx.root.rebalance()
// ...
opgid := tx.meta.pgid
// spill ...
if err := tx.root.spill(); err != nil {
tx.rollback()
return err
}
// 脏数据页落盘...
// meta page 落盘...
return nil
}rebalance 流程以 Bucket 副本为单元分组执行：
func (b *Bucket) rebalance() {
// 针对 bucket 下的所有 node 副本进行 rebalance
// 只有被反序列化成 node 副本的节点才可能有过修改
for _, n := range b.nodes {
n.rebalance()
}
// 针对所有反序列化过的子 bucket 副本进行 rebalance
// 只有被反序列化成 bucket 副本的桶才可能有过修改
for _, child := range b.buckets {
child.rebalance()
}
}下面拆解核心方法——node.rebalance：
func (n *node) rebalance() {
// 节点没有删除过数据，则无需 rebalance
if !n.unbalanced {
return
}
// 当前已经在执行 rebalance 流程，为避免重复执行，将 unbalanced 置为 false
n.unbalanced = false
// ...
// 如果节点填充数据量 > pageSzie/4 并且 key 满足最小数量要求 (叶子节点多于 1 个 key，枝干节点多于 2 个 key)，则不需要进行 rebalance
var threshold = n.bucket.tx.db.pageSize / 4
if n.size() > threshold && len(n.inodes) > n.minKeys() {
return
}
// 如果当前 node 是 root，则有特殊处理
if n.parent == nil {
// 如果 root 为枝干节点，并且只有一个 inode，需要和 inode 合并
if !n.isLeaf && len(n.inodes) == 1 {
// 获取唯一的 child node
child := n.bucket.node(n.inodes[0].pgid, n)
// copy child node 的信息
n.isLeaf = child.isLeaf
n.inodes = child.inodes[:]
n.children = child.children
// 将 child node 的所有孩子的 parent 置为自己
for _, inode := range n.inodes {
if child, ok := n.bucket.nodes[inode.pgid]; ok {
child.parent = n
}
}
// 移除 child node
child.parent = nil
delete(n.bucket.nodes, child.pgid)
child.free()
}
return
}
// 如果当前节点没有 inode，则直接移除当前节点
if n.numChildren() == 0 {
n.parent.del(n.key)
n.parent.removeChild(n)
delete(n.bucket.nodes, n.pgid)
n.free()
// 递归 rebalance 父节点
n.parent.rebalance()
return
}
// 断言：父节点必然至少有两个孩子节点. 因为父节点是枝干节点，孩子节点数至少为 2，这是 boltdb 实现 b+ 树的规范
_assert(n.parent.numChildren() > 1, "parent must have at least 2 children")
// 走常规流程，进行 rebalance 操作
// 如果当前 node 在 parent 中的 index = 0，则和后继兄弟节点合并
// 如果当前 node 在 parent 中的 index > 0，则和前驱兄弟节点合并
var target *node
var useNextSibling = (n.parent.childIndex(n) == 0)
if useNextSibling {
target = n.nextSibling()
} else {
target = n.prevSibling()
}
// 和后继节点合并
if useNextSibling {
// 遍历后继节点的所有 child node，将其 parent 指向自己，并添加到自己的 children 列表中
for _, inode := range target.inodes {
if child, ok := n.bucket.nodes[inode.pgid]; ok {
child.parent.removeChild(child)
child.parent = n
child.parent.children = append(child.parent.children, child)
}
}
// 当前节点 inodes 列表追加后继节点的所有 inode
n.inodes = append(n.inodes, target.inodes...)
// 从 parent 中删除后继节点，包含删除 b+ 树中的 kv 数据以及从 parent node 中的 children list 中移除
n.parent.del(target.key)
n.parent.removeChild(target)
// 从 bucket 的 nodes 缓存中移除后继节点
delete(n.bucket.nodes, target.pgid)
target.free()
} else { // 和前驱节点合并
// 遍历自己的所有 child node，将其 parent 指向前驱节点，并添加到前驱节点的 children 列表中
for _, inode := range n.inodes {
if child, ok := n.bucket.nodes[inode.pgid]; ok {
child.parent.removeChild(child)
child.parent = target
child.parent.children = append(child.parent.children, child)
}
}
// 前驱节点的 inodes 中追加当前节点的所有 inode
target.inodes = append(target.inodes, n.inodes...)
// 从 parent 中删除当前节点，包含删除 b+ 树中的 kv 数据以及从 parent node 中的 children list 中移除
n.parent.del(n.key)
n.parent.removeChild(n)
// 从 bucket 的 nodes 缓存中移除当前节点
delete(n.bucket.nodes, n.pgid)
n.free()
}
// 递归 rebalance parent
n.parent.rebalance()
}下面附上上述流程涉及到的几个支线方法：
func (n *node) minKeys() int {
if n.isLeaf {
return 1
}
return 2
}prevSibling——获取 node 副本的前驱兄弟节点：
func (n *node) prevSibling() *node {
if n.parent == nil {
return nil
}
index := n.parent.childIndex(n)
if index == 0 {
return nil
}
return n.parent.childAt(index - 1)
}nextSibling——获取 node 副本的后继兄弟节点：
func (n *node) nextSibling() *node {
if n.parent == nil {
return nil
}
index := n.parent.childIndex(n)
if index >= n.parent.numChildren()-1 {
return nil
}
return n.parent.childAt(index + 1)
}事务提交流程中，完成 rebalance 操作后，就会进一步执行 spill 操作. 且 spill 流程不仅完成大节点的拆分，还会基于 copy-on-write 机制为所有反序列化过的 node 分配新的 page 副本：
func (tx *Tx) Commit() error {
// ...
// rebalance ...
tx.root.rebalance()
// ...
opgid := tx.meta.pgid
// spill ...
if err := tx.root.spill(); err != nil {
tx.rollback()
return err
}
// 脏数据页落盘...
// meta page 落盘...
return nil
}spill 流程以 Bucket 副本为单元分组执行：
// spill 拆分 bucket
func (b *Bucket) spill() error {
// 针对所有反序列化过的子 bucket，尝试进行 spill
for name, child := range b.buckets {
var value []byte
// 针对 inline bucket，无需 spill. 直接序列化
if child.inlineable() {
child.free()
value = child.write()
} else {
// 针对常规的子 bucket，需要递归执行 spill 操作
if err := child.spill(); err != nil {
return err
}
// 深拷贝一份 child bucket header 的副本
value = make([]byte, unsafe.Sizeof(bucket{}))
var bucket = (*bucket)(unsafe.Pointer(&value[0]))
*bucket = *child.bucket
}
// 如果 child 没有数据，直接跳过
if child.rootNode == nil {
continue
}
// 构造一个当前 bucket 的 cursor 实例
var c = b.Cursor()
// 移动 cursor，走到 child bucket 所在 kv 对的位置
k, _, flags := c.seek([]byte(name))
// 更新 kv 对内容，value 更新为 spill 后的 child bucket 的序列化数据
c.node().put([]byte(name), []byte(name), value, 0, bucketLeafFlag)
}
// 如果当前 bucket 没有数据，则无需 spill 直接返回
if b.rootNode == nil {
return nil
}
// 从 root node 开始 spill 拆分
if err := b.rootNode.spill(); err != nil {
return err
}
// spill 后可能会出现新的 root 节点，因此尝试更新引用
b.rootNode = b.rootNode.root()
// ...
// 更新 root 节点对应 page id
b.root = b.rootNode.pgid
return nil
}node.spill 基于 node 副本进行 spill 拆分，并针对拆分后的每个 node 副本依次分配新 page 的核心方法：
func (n *node) spill() error {
var tx = n.bucket.tx
// 节点已经 spill 过，直接返回
if n.spilled {
return nil
}
// 对反序列化过的 child node 进行排序
sort.Sort(n.children)
// 针对每个反序列化过的 child node 先进行 spill 操作
for i := 0; i < len(n.children); i++ {
if err := n.children[i].spill(); err != nil {
return err
}
}
// children 置为空. 因为能走到 spill 流程必然是提交事务的时刻，后续 children 已经不需要用到了
n.children = nil
// 将当前 node 拆分成多个符合要求的 node
var nodes = n.split(uintptr(tx.db.pageSize))
// 遍历所有拆分出来的新节点
for _, node := range nodes {
// 如果 node 对应 page id > 0，代表复用了之前的 page，则需要对 page 进行 free.
// 因为当前 node 要被写入到一个新的脏数据 page 副本中了
if node.pgid > 0 {
tx.db.freelist.free(tx.meta.txid, tx.page(node.pgid))
node.pgid = 0
}
// 根据 node 数据量大小结合 pageSize 设定，计算出 node 需要的 page 数量
// 申请分配指定数量的可用 page. 此时优先从 freelist 获取，如果 freelist 资源不足，则重新进行一轮 mmap 作扩容
// 此处如果要分配的 page 数量 > 1，则会通过 overflow 进行拼接. 逻辑意义上仍是一个"page"
p, err := tx.allocate((node.size() + tx.db.pageSize - 1) / tx.db.pageSize)
// node pg id 指向申请到的可用 page 的首个 page 的 id
node.pgid = p.id
// node 内容序列化到 page 中
node.write(p)
// 标识 node 已经 spill 过了
node.spilled = true
// parent 存在，则跟新对应的 inodes 和 b+ 树中的 kv 数据
if node.parent != nil {
var key = node.key
if key == nil {
key = node.inodes[0].key
}
// 写入到 parent b+ 树中
node.parent.put(key, node.inodes[0].key, nil, node.pgid, 0)
// 更新 parent node 的 inodes 内容
node.key = node.inodes[0].key
// ...
}
// ...
}
// 如果 spill 过程中给 node 拆出了一个新的 parent，则需要递归对其 spill
if n.parent != nil && n.parent.pgid == 0 {
n.children = nil
return n.parent.spill()
}
return nil
}下面看看，如何实现将一个节点拆分成多个合规的 node 副本：
func (n *node) split(pageSize uintptr) []*node {
var nodes []*node
node := n
for {
// 首先将当前 node 拆分成两部分：
// - 第一部分：一定满足大小要求
// - 第二部分：如果为 nil，则拆分结束；如果大小仍不合规，则针对第二部分递归拆分
a, b := node.splitTwo(pageSize)
nodes = append(nodes, a)
// 第二部分为 nil，则拆分结束
if b == nil {
break
}
// node 指向第二部分，递归对第二部分执行上述流程
node = b
}
return nodes
}在 node.splitTwo 方法中：
// 根据传入的 pageSize 阈值，将 node 拆分为两部分，保证第一部分一定满足要求
func (n *node) splitTwo(pageSize uintptr) (*node, *node) {
// 如果当前 node 的 inode 数量 <= 4 或者数据大小小于 pageSize，则直接返回不作拆分
if len(n.inodes) <= (minKeysPerPage*2) || n.sizeLessThan(pageSize) {
return n, nil
}
// 根据 bucket 设置的填充率计算出 spill 阈值 threshold
var fillPercent = n.bucket.FillPercent
if fillPercent < minFillPercent {
fillPercent = minFillPercent
} else if fillPercent > maxFillPercent {
fillPercent = maxFillPercent
}
threshold := int(float64(pageSize) * fillPercent)
// 根据 threshold，得出 split 切分之处的 index. 从 index 开始往右的部分为切分出来的第二部分
splitIndex, _ := n.splitIndex(threshold)
// 如果 node 原本为 root，需要构造出一个新的 root. 因为 node 要被拆分了
if n.parent == nil {
n.parent = &node{bucket: n.bucket, children: []*node{n}}
}
// 拆分后的第二部分内容暂时存放在 next 实例当中
next := &node{bucket: n.bucket, isLeaf: n.isLeaf, parent: n.parent}
// next 追加到 parent 的 children 中
n.parent.children = append(n.parent.children, next)
// 将 node 的 inodes 沿着 splitIndex 一分为二，第二部分分给 next
next.inodes = n.inodes[splitIndex:]
n.inodes = n.inodes[:splitIndex]
// ...
// 返回拆分后得到的两部分
return n, next
}// 根据 thresold，找到 node 的拆分边界
func (n *node) splitIndex(threshold int) (index, sz uintptr) {
sz = pageHeaderSize
// 遍历 node 的 inodes
for i := 0; i < len(n.inodes)-minKeysPerPage; i++ {
index = uintptr(i)
inode := n.inodes[i]
// 计算得到 pageElement + key + value 三部分总大小
elsize := n.pageElementSize() + uintptr(len(inode.key)) + uintptr(len(inode.value))
// 如果加上当前 inode 后，前半部分大小超过阈值，则找到拆分边界， index 就是后半部分的起点
if index >= minKeysPerPage && sz+elsize > uintptr(threshold) {
break
}
// 每遍历完一个 inode，将 elsize 累加到 sz
sz += elsize
}
return
}至此，b+树篇正文结束.
本文是 etcd 存储引擎系列的第三篇，带着大家一起深入了解了 b+树理论模型以及 boltdb 针对该模块的实现细节. 在此回顾整个系列的研究进程并对后续内容进行展望：
本文由微信公众号小徐先生的编程世界原创，哈喽比特收录。
文章来源：https://mp.weixin.qq.com/s/lqFkUIiabcRb2LAEXdXsSA
京东创始人刘强东和其妻子章泽天最近成为了互联网舆论关注的焦点。有关他们“移民美国”和在美国购买豪宅的传言在互联网上广泛传播。然而，京东官方通过微博发言人发布的消息澄清了这些传言，称这些言论纯属虚假信息和蓄意捏造。
日前，据博主“@超能数码君老周”爆料，国内三大运营商中国移动、中国电信和中国联通预计将集体采购百万台规模的华为Mate60系列手机。
据报道，荷兰半导体设备公司ASML正看到美国对华遏制政策的负面影响。阿斯麦（ASML）CEO彼得·温宁克在一档电视节目中分享了他对中国大陆问题以及该公司面临的出口管制和保护主义的看法。彼得曾在多个场合表达了他对出口管制以及中荷经济关系的担忧。
今年早些时候，抖音悄然上线了一款名为“青桃”的 App，Slogan 为“看见你的热爱”，根据应用介绍可知，“青桃”是一个属于年轻人的兴趣知识视频平台，由抖音官方出品的中长视频关联版本，整体风格有些类似B站。
日前，威马汽车首席数据官梅松林转发了一份“世界各国地区拥车率排行榜”，同时，他发文表示：中国汽车普及率低于非洲国家尼日利亚，每百户家庭仅17户有车。意大利世界排名第一，每十户中九户有车。
近日，一项新的研究发现，维生素 C 和 E 等抗氧化剂会激活一种机制，刺激癌症肿瘤中新血管的生长，帮助它们生长和扩散。
据媒体援引消息人士报道，苹果公司正在测试使用3D打印技术来生产其智能手表的钢质底盘。消息传出后，3D系统一度大涨超10%，不过截至周三收盘，该股涨幅回落至2%以内。
9月2日，坐拥千万粉丝的网红主播“秀才”账号被封禁，在社交媒体平台上引发热议。平台相关负责人表示，“秀才”账号违反平台相关规定，已封禁。据知情人士透露，秀才近期被举报存在违法行为，这可能是他被封禁的部分原因。据悉，“秀才”年龄39岁，是安徽省亳州市蒙城县人，抖音网红，粉丝数量超1200万。他曾被称为“中老年...
9月3日消息，亚马逊的一些股东，包括持有该公司股票的一家养老基金，日前对亚马逊、其创始人贝索斯和其董事会提起诉讼，指控他们在为 Project Kuiper 卫星星座项目购买发射服务时“违反了信义义务”。
据消息，为推广自家应用，苹果现推出了一个名为“Apps by Apple”的网站，展示了苹果为旗下产品（如 iPhone、iPad、Apple Watch、Mac 和 Apple TV）开发的各种应用程序。
特斯拉本周在美国大幅下调Model S和X售价，引发了该公司一些最坚定支持者的不满。知名特斯拉多头、未来基金（Future Fund）管理合伙人加里·布莱克发帖称，降价是一种“短期麻醉剂”，会让潜在客户等待进一步降价。
据外媒9月2日报道，荷兰半导体设备制造商阿斯麦称，尽管荷兰政府颁布的半导体设备出口管制新规9月正式生效，但该公司已获得在2023年底以前向中国运送受限制芯片制造机器的许可。
近日，根据美国证券交易委员会的文件显示，苹果卫星服务提供商 Globalstar 近期向马斯克旗下的 SpaceX 支付 6400 万美元（约 4.65 亿元人民币）。用于在 2023-2025 年期间，发射卫星，进一步扩展苹果 iPhone 系列的 SOS 卫星服务。
据报道，马斯克旗下社交平台𝕏（推特）日前调整了隐私政策，允许 𝕏 使用用户发布的信息来训练其人工智能（AI）模型。新的隐私政策将于 9 月 29 日生效。新政策规定，𝕏可能会使用所收集到的平台信息和公开可用的信息，来帮助训练 𝕏 的机器学习或人工智能模型。
9月2日，荣耀CEO赵明在采访中谈及华为手机回归时表示，替老同事们高兴，觉得手机行业，由于华为的回归，让竞争充满了更多的可能性和更多的魅力，对行业来说也是件好事。
《自然》30日发表的一篇论文报道了一个名为Swift的人工智能（AI）系统，该系统驾驶无人机的能力可在真实世界中一对一冠军赛里战胜人类对手。
近日，非营利组织纽约真菌学会（NYMS）发出警告，表示亚马逊为代表的电商平台上，充斥着各种AI生成的蘑菇觅食科普书籍，其中存在诸多错误。
社交媒体平台𝕏（原推特）新隐私政策提到：“在您同意的情况下，我们可能出于安全、安保和身份识别目的收集和使用您的生物识别信息。”
2023年德国柏林消费电子展上，各大企业都带来了最新的理念和产品，而高端化、本土化的中国产品正在不断吸引欧洲等国际市场的目光。
罗永浩日前在直播中吐槽苹果即将推出的 iPhone 新品，具体内容为：“以我对我‘子公司’的了解，我认为 iPhone 15 跟 iPhone 14 不会有什么区别的，除了序（列）号变了，这个‘不要脸’的东西，这个‘臭厨子’。
