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 编程的技巧，有点丑，但是很普遍。

祝大家玩得愉快 ！

Contents