Google B-Tree 实现

文章目录

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

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 以方便对下文的理解:

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

CopyOnWriteContext

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

  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方法以真正移除数据。

 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 的叶子节点增加了指向左右节点的指针,即变为链表结构,在进行范围查询时由 DFS 退化为链表的遍历。

B+Tree

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