btree 的使用

btree 是 Google 写的一个基于内存的 B tree 实现。一如既往的 Google 风格,注释很详细,代码简洁利落(700 多行,只算核心逻辑的话代码量估计更少),未来有时间再来聊聊具体的实现细节。etcd 用 btree 来做 revision 到 keyIndex 的索引,也就是说 etcd 从 key 到具体的 value 其实有两次索引:

1
key -> keyIndex -> bbolt

第一次索引通过 key 查找内存的 btree 来找到 keyIndex 这个数据结构,然后从这个数据结构找到具体的 revision;

第二次索引通过 bbolt 的接口,以 key 为 revision 找到对应的 key-value,从而反序列化出具体的 value,其中 bbolt 是用 B+ tree 来构建数据索引;

我们来简单看看 btree 这个库怎么用,先来一个可运行的小程序尝鲜:

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
36
37
38
39
40
41
42
43
44
45
46
package main

import (
"fmt"

"github.com/google/btree"
)

type foo struct {
value int64
}

// btree 存放的东西必须实现 Less(),即 Item 接口
func (i *foo) Less(b btree.Item) bool {
return i.value < b.(*foo).value
}

func main() {
// 创建一颗 btree
tree := btree.New(32)

// 创建 3 个测试数据
f1 := foo{value: 123}
f2 := foo{value: 456}
f3 := foo{value: 789}

// 插入到 btree 中
tree.ReplaceOrInsert(&f1)
tree.ReplaceOrInsert(&f2)
tree.ReplaceOrInsert(&f3)

// 按照升序打印 >= 0 的数据
// 此时应该一次打印 123,456,789
tree.AscendGreaterOrEqual(&foo{value: 0}, func(item btree.Item) bool {
f := item.(*foo)
fmt.Println(f.value)
return true
})

// 此时应该什么都打印不出来
tree.AscendGreaterOrEqual(&foo{value: 999}, func(item btree.Item) bool {
f := item.(*foo)
fmt.Println(f.value)
return true
})
}

由于数据插入到 btree 需要符合 btree.item interface,当我们读取数据的时候,必须需要将一个 interface 类型转换成一个具体的类型,这时候将用到类型断言

1
f := item.(*foo) // 这时候 f 就是 *foo 类型了

这是一个常见的 Go 编程的技巧,有点丑,但是很普遍。

祝大家玩得愉快