# Google B-Tree 实现 > B-Tree 及其变种数据结构被广泛用于存储系统、数据库系统中，主要作为索引使用，适用于动态随机访问数据的场景。*[google/btree (github.com)](https://github.com/google/btree)* 是一个使用 Go 编写的纯内存 B-Tree 实现，本文对它的源码进行了分析。 ## 概览 #### B-Tree 结构 *[Organization and maintenance of large ordered indices](https://dl.acm.org/doi/10.1145/1734663.1734671)* 这篇论文提出了 B-Tree 数据结构，B-Tree 的查询从根结点开始，对节点内的有序数据进行二分查找，如果命中则结束查询，否则进入子节点查询，直至叶子结点。B-Tree 查询的特点是搜索有可能在非叶子节点结束。作为一个典型的树形结构，其包含的节点类型有： - 根节点（Root Node）：一个 B-Tree 只有一个根节点，位于树的最顶端； - 分支节点（Branch Node）：包含数据项和指向子节点的指针； - 叶子节点（Leaf Node）：只存储数据项。 ![B-Tree](B-Tree.png) B-Tree 的结构如上图所示，一个非空、高度为 h、最小 degree 为 k 的 B-Tree 都有以下属性： 1. 从 root 到叶子节点的长度均为 h； 2. root 和叶子节点可以含有 [1, 2k] 条数据，且root 和分支节点的子节点数量为该节点的数据数 +1； 3. 除 root 和叶子节点外，其它节点都至少有 k 条数据，最多有 2k 条数据。 4. 除 root 和叶子节点外，其它节点至少有 k+1 个子节点，最多有 2k+1 个子节点。 #### API btree 提供了基础的 CRUD API，注释中详细描述了这些接口的功能，也能 Google 到许多文章介绍 btree 的使用。因此仅列出几个关键的 API 以方便对下文的理解： ```go func (t *BTree) Get(key Item) Item {} func (t *BTree) ReplaceOrInsert(item Item) Item {} func (t *BTree) Delete(item Item) Item {} func (t *BTree) Has(key Item) bool {} func (t *BTree) Clear(addNodesToFreelist bool) {} func (t *BTree) Clone() (t2 *BTree) {} ``` 数据插入到 btree 前需要实现 `Item` interface，而这个接口只包含一个 Less 方法，用来将 btree 内的所有数据以增序排列： ```go type Item interface { Less(than Item) bool } ``` 通过 interface 传值是对数据的一层抽象，进而实现不同数据类型的兼容性，而不是将数据序列化为 byte slice 进行存储。缺点在于每次读取值时需要进行类型断言与转换，不过通常情况下使用时都会将 API 封装一层，调用方可以不用关注这些内容。 #### Strict Weak Ordering btree 中一个重要的概念是 Strict Weak Ordering：即如果`!(a 0 && !s[i-1].Less(item) { return i - 1, true } return i, false } ``` ## 数据结构 btree 的数据结构比较清晰，包含 B-Tree 的最小度数`degree`、存储的数据条目数量`length`、与根节点`root`。每个节点都含有自己的子节点与数据条目： ```go // Write operations are not safe for concurrent mutation by multiple goroutines, but Read operations are. type BTree struct { degree int length int root *node cow *copyOnWriteContext } type node struct { items items children children cow *copyOnWriteContext } type children []*node ``` btree 并没有对不同类型的节点进行区分，都统一为 node 表示，以复用节点操作的代码。如果该节点是叶子节点，那么它的`children`字段就是空的。 #### copyOnWriteContext copyOnWriteContext 是 btree 中每个节点都持有的一个结构体，从名字就可以看出，这是一个写时复制有关的内容。由于 btree 是一个纯内存的实现，当我们使用内部提供的`Clone()`方法对原有的 btree 进行拷贝时，新树与旧树会使用写时复制技术来共享同一片内存空间，进而节约内存开销与数据复制所需的时间。只有要对节点进行写操作时，才会真正地新建一个节点。 ![CopyOnWriteContext](CopyOnWriteContext.png) ```go type copyOnWriteContext struct { freelist *FreeList } type FreeList struct { mu sync.Mutex freelist []*node } ``` > Redis 的 RDB 持久化中也使用到了 COW 技术，Redis 主进程 fork 出子进程进行数据备份，父进程继续对外提供服务。而子父进程只是虚拟空间不同，对应的物理空间是相同的，这与`Clone()`方法有异曲同工之处。区别在于 btree 的写时复制直接共享了虚拟内存地址， > 从整体来看，copyOnWriteContext 具有两个作用： - 标记 btree 是否具有当前节点的写操作权限，若没有，则需要创建一个新的节点并替换当前节点，然后才能进行写操作： ```go func (n *node) mutableFor(cow *copyOnWriteContext) *node { if n.cow == cow { return n } out := cow.newNode() // copy node to out code is omitted return out } func (c *copyOnWriteContext) newNode() (n *node) { n = c.freelist.newNode() n.cow = c return } ``` node 的`mutableFor`方法展示了这一过程，如果当前节点的 cow 与 btree 的 cow 一致，那么直接返回当前节点，否则会新建一个节点，并拷贝当前节点的值至新的节点中。 - 封装了可复用的 node 节点列表`freelist`，当一个节点被销毁时会被放入回收列表中，新建节点时可直接从中取出复用，减少了申请节点内存的操作频率。 ```go func (f *FreeList) newNode() (n *node) { f.mu.Lock() index := len(f.freelist) - 1 if index < 0 { f.mu.Unlock() return new(node) } n = f.freelist[index] f.freelist[index] = nil f.freelist = f.freelist[:index] f.mu.Unlock() return } ``` copyOnWriteContext 是 btree 优化内存开销的重要手段，从复用/共享内存这两个角度出发，减少内存申请、销毁的频率，并在大批量数据复制的场景下，使用写时复制共享相同的数据。 ## 对外接口与应用 #### ReplaceOrInsert ReplaceOrInsert 会插入一条新数据到 btree 中，如果该条数据已经存在，则会用新值替换旧值。这个接口的实现中除去边界条件处理，本质上是调用内部的`insert`方法插入数据： ```go func (t *BTree) ReplaceOrInsert(item Item) Item { // ... out := t.root.insert(item, t.maxItems()) if out == nil { t.length++ } return out } func (n *node) insert(item Item, maxItems int) Item { i, found := n.items.find(item) if found { // 当前节点中存在该条数据，更新数据 out := n.items[i] n.items[i] = item return out } if len(n.children) == 0 { // 当前节点没有子节点，在当前节点中插入新数据 n.items.insertAt(i, item) return nil } if n.maybeSplitChild(i, maxItems) { inTree := n.items[i] switch { case item.Less(inTree): // no change, we want first split node case inTree.Less(item): i++ // we want second split node default: out := n.items[i] n.items[i] = item return out } } return n.mutableChild(i).insert(item, maxItems) // 递归调用 } ``` `insert`方法的执行路径如下： 1. 先判断当前节点中是否存在该条数据，如果存在则更新数据； 2. 如果当前节点不存在该条数据，并且当前节点没有子节点，那么直接在当前节点中插入新数据； 3. 如果当前节点不存在该条数据，并且当前节点含有子节点，那么递归调用子节点的`insert`方法，在 Strict Weak Ordering 一小节中提到过，`find`方法返回的 i 是**第一个**满足`(item < s[i])`条件的值，既然已经确定当前节点不存在该条数据，那么它应该被存储在第 i 个子节点中。 #### Delete B-Tree 节点删除数据时都需要进行以下判断： - 节点的 items 数量大于 minItems，直接从中删除指定的 item； - 节点的 items 数量小于等于 minItems，此时需要为节点填充 item： 1. 左节点含有足够的 items，从左节点偷取一个 item； 2. 右节点含有足够的 items，从右节点偷取一个 item； 3. 与右节点合并。 btree 对删除操作进行了一定的简化，在递归调用子节点的`remove`方法之前，先确保子节点具有足够的 items 以移除节点，然后再调用一次`remove`方法以真正移除数据。 ```go // 以下代码已经简化 func (n *node) remove(item Item, minItems int, typ toRemove) Item { i, found := n.items.find(item) if len(n.children) == 0 { if found { return n.items.removeAt(i) } return nil } // If we get to here, we have children. if len(n.children[i].items) <= minItems { // 子节点需要填充 item return n.growChildAndRemove(i, item, minItems, typ) } child := n.mutableChild(i) if found { out := n.items[i] n.items[i] = child.remove(nil, minItems, removeMax) return out } return child.remove(item, minItems, typ) } // growChildAndRemove 确保子节点含有足够的 items func (n *node) growChildAndRemove(i int, item Item, minItems int, typ toRemove) Item { if i > 0 && len(n.children[i-1].items) > minItems { // Steal from left child } else if i < len(n.items) && len(n.children[i+1].items) > minItems { // steal from right child } else { // merge with right child } return n.remove(item, minItems, typ) // 第二次调用 remove 方法真正移除 item } ``` #### Iterate btree 支持增序/降序范围查询，以增序查询为例，这是一个标准的迭代 BFS 实现，并将迭代到的值以调用方传入的`ItemIterator`函数进行处理。 ```go func (n *node) iterate(dir direction, start, stop Item, includeStart bool, hit bool, iter ItemIterator) (bool, bool) { var ok, found bool var index int switch dir { case ascend: if start != nil { index, _ = n.items.find(start) } for i := index; i < len(n.items); i++ { if len(n.children) > 0 { if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter); !ok { return hit, false } } // 删除了边界条件处理代码 if !iter(n.items[i]) { return hit, false } } if len(n.children) > 0 { if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter); !ok { return hit, false } } return hit, true } ``` #### 应用 etcd 为了实现多版本并发控制，会将键值对的每个版本`reversion`都保存到 BoltDB 中。为了将客户端提供的原始键值对信息与 reversion 关联起来，etcd 使用 btree 维护 Key 与 reversion 之间的映射关系，然后再利用获取到的 reversion 去 BoltDB 中查找 value。 下面是 etcd 的封装的 btree 代码，由于 btree 支持并发读，但是只能串行写，所以在`treeIndex`中加了一个读写锁。这部分的详细内容可以参考 *[etcd 状态机存储](https://wingsxdu.com/post/database/etcd/#%E7%8A%B6%E6%80%81%E6%9C%BA%E5%AD%98%E5%82%A8)* 一文，本文不再详细缀述。 ```go type treeIndex struct { sync.RWMutex tree *btree.BTree lg *zap.Logger } ``` ## 总结 Google 实现的 btree 中有许多值得深思的点， 使用写时复制与回收列表来减少内存开销，并且尽可能地复用底层代码，整体的设计十分简洁。 通过上面的内容可以得知，B-Tree 的查找性能不稳定，最好情况是只查根节点，最坏情况是查到叶子节点。并且作为有序的数据组合，其范围查询的性能也不算好。因此在 B-Tree 的基础上提出了改进的数据结构 B+Tree： - B-Tree 的所有节点都会存储数据，而 B+Tree 只有叶子节点存储数据，查询复杂度稳定为 log(n)，； - B+Tree 的叶子节点增加了指向左右节点的指针，即变为链表结构，在进行范围查询时由 BFS 退化为链表的遍历。 ![B+Tree](B+Tree.png) B+Tree 的另一个优点是，由于非叶子节点不存储数据，只存储 key 和指向子节点的指针，相同大小的非叶子节点可以索引到更多的子节点。举例来说，如果我们实现一个基于磁盘的索引系统，每个节点大小固定为 16KB，每条数据的大小为 1KB，以一个 unit64 的整数作为主键，一个指向子节点的指针为 unit64，也就是说一个节点可以存储 16 条数据，。那么高度为 3 的 B+Tree 第一层为 1 个 根节点，第二层约有 1,000 个节点（一个主键和一个指针的组合占用 16Bytes），第三层约有 1,000,000 个节点，可以存储约 1600 万条数据。而 B-Tree 的第二层只有 16 个节点，第三层只有 256 个节点，只能存储 4096 条数据，需要 6 层才能存储 1600 万条数据。 从上面的例子可以看出，在千万级数据的情况下，不考虑在内存中缓存节点，B-Tree 最差需要 6 次 I/O 才能查询到数据，而 B+Tree 稳定为 3 次 I/O。因此在笔者看来，在基于磁盘的存储系统中，B-Tree 无论是在单个值查询还是范围查询都没有优势；而在纯内存存储的时，B-Tree 也只适用于范围查询不频繁的情况下。 ## References - [Difference between B tree and B+ tree - GeeksforGeeks](https://www.geeksforgeeks.org/difference-between-b-tree-and-b-tree/) - [Organization and maintenance of large ordered indices](https://dl.acm.org/doi/10.1145/1734663.1734671) - [Strict Weak Ordering and the C++ STL](https://medium.com/@shiansu/strict-weak-ordering-and-the-c-stl-f7dcfa4d4e07)