Google B-Tree 实现

2021-11-20 约 4162 字预计阅读 9 分钟

B-Tree 及其变种数据结构被广泛用于存储系统、数据库系统中，主要作为索引使用，适用于动态随机访问数据的场景。google/btree (github.com) 是一个使用 Go 编写的纯内存 B-Tree 实现，本文对它的源码进行了分析。

概览

B-Tree 结构

Organization and maintenance of large ordered indices 这篇论文提出了 B-Tree 数据结构，B-Tree 的查询从根结点开始，对节点内的有序数据进行二分查找，如果命中则结束查询，否则进入子节点查询，直至叶子结点。B-Tree 查询的特点是搜索有可能在非叶子节点结束。作为一个典型的树形结构，其包含的节点类型有：

根节点（Root Node）：一个 B-Tree 只有一个根节点，位于树的最顶端；
分支节点（Branch Node）：包含数据项和指向子节点的指针；
叶子节点（Leaf Node）：只存储数据项。

B-Tree 的结构如上图所示，一个非空、高度为 h、最小 degree 为 k 的 B-Tree 都有以下属性：

从 root 到叶子节点的长度均为 h；
root 和叶子节点可以含有 [1, 2k] 条数据，且root 和分支节点的子节点数量为该节点的数据数 +1；
除 root 和叶子节点外，其它节点都至少有 k 条数据，最多有 2k 条数据。
除 root 和叶子节点外，其它节点至少有 k+1 个子节点，最多有 2k+1 个子节点。

API

btree 提供了基础的 CRUD API，注释中详细描述了这些接口的功能，也能 Google 到许多文章介绍 btree 的使用。因此仅列出几个关键的 API 以方便对下文的理解：

1
2
3
4
5
6


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 内的所有数据以增序排列：

1
2
3


type Item interface {
  Less(than Item) bool
}

通过 interface 传值是对数据的一层抽象，进而实现不同数据类型的兼容性，而不是将数据序列化为 byte slice 进行存储。缺点在于每次读取值时需要进行类型断言与转换，不过通常情况下使用时都会将 API 封装一层，调用方可以不用关注这些内容。

Strict Weak Ordering

btree 中一个重要的概念是 Strict Weak Ordering：即如果!(a<b) && !(b<a)，那么就视为 a 和 b 是相等的。在这里，相等并不意味着 a 和 b 是同一个对象实体或其值完全一致，而是只要满足表达式!(a<b) && !(b<a)就可以视为a == b。

例如在下面的代码示例中，foo结构体具有三个内部字段，并且实现了 Less 方法，这个方法可以视为小于号<操作运算符。a 和 b 都是它的两个实体对象，并且结构体没有手动实现==号操作运算符。虽然它们具有不同的变量值与内存地址，但他们满足条件!(a<b) && !(b<a)，那么就可以视为 a 和 b 是相等的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


type foo struct {
  key   int64
  value int64
  name  string
}

func (i *foo) Less(b *foo) bool {
  return i.key < b.key
}

func main() {
  a := &foo{key: 123, value: 456, name: "test1"}
  b := &foo{key: 123, value: 789, name: "test2"}
  if !a.Less(b) && !b.Less(a) {
    println("a == b")
  }
}

具体到 btree 的查询方法实现中，会利用二分查找找出第一个满足(item < s[i])条件的值，这也就说明(item < s[i-1])是不成立的（值为 false），这时再进行一次(s[i-1] < item)判断，如果也不成立，那么就可以认为 item 与 s[i-1] 是相等的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


// 'found' is true if the item already exists in the list at the given index.
func (s items) find(item Item) (index int, found bool) {
  i := sort.Search(len(s), func(i int) bool {
    return item.Less(s[i])
  })
  if i > 0 && !s[i-1].Less(item) {
    return i - 1, true
  }
  return i, false
}

数据结构

btree 的数据结构比较清晰，包含 B-Tree 的最小度数degree、存储的数据条目数量length、与根节点root。每个节点都含有自己的子节点与数据条目：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


// 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 进行拷贝时，新树与旧树会使用写时复制技术来共享同一片内存空间，进而节约内存开销与数据复制所需的时间。只有要对节点进行写操作时，才会真正地新建一个节点。

1
2
3
4
5
6
7
8


type copyOnWriteContext struct {
  freelist *FreeList
}

type FreeList struct {
   mu       sync.Mutex
   freelist []*node
}

Redis 的 RDB 持久化中也使用到了 COW 技术，Redis 主进程 fork 出子进程进行数据备份，父进程继续对外提供服务。而子父进程只是虚拟空间不同，对应的物理空间是相同的，这与Clone()方法有异曲同工之处。区别在于 btree 的写时复制直接共享了虚拟内存地址，

从整体来看，copyOnWriteContext 具有两个作用：

标记 btree 是否具有当前节点的写操作权限，若没有，则需要创建一个新的节点并替换当前节点，然后才能进行写操作：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


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，当一个节点被销毁时会被放入回收列表中，新建节点时可直接从中取出复用，减少了申请节点内存的操作频率。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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方法插入数据：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


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方法的执行路径如下：

先判断当前节点中是否存在该条数据，如果存在则更新数据；
如果当前节点不存在该条数据，并且当前节点没有子节点，那么直接在当前节点中插入新数据；
如果当前节点不存在该条数据，并且当前节点含有子节点，那么递归调用子节点的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方法以真正移除数据。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


// 以下代码已经简化
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函数进行处理。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


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 状态机存储 一文，本文不再详细缀述。

1
2
3
4
5


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 的另一个优点是，由于非叶子节点不存储数据，只存储 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

Radix Tree 与 Gin 实现

目录