由一个golang的B-Tree包展开-1(属性介绍)

发表于 | 分类于 |

偶然看到一个google的一个golang实现的内存中b-tree包(传送门)，就细看了其实现. 对其他平衡树感谢趣的可以看这里：Left-Leaning Red-Black Tree, B+tree

reddit上有个github.com/google/btree和 github.com/cznic/b比较的讨论，可以看到这个包的作者与用户的一些讨论。

b-tree的定义

关于btree的结构定义，《计算机程序设计艺术》和《算法导论》中的描述有点儿出入，知乎上有个细微区别的讨论(传送门)， 记得我上学时数据结构教材是清华严蔚敏那版， 里面对btree的定义是参考了Knuth在《计算机程序设计艺术》的， 里面有个“阶“的概念，就是指一个节点可以有的最大子树的个数，一棵m阶b-tree的定义就如下了：

  1. 树中每一个结点至多有m棵子树
  2. 若根结点不是叶子结点，则至少有两棵子树
  3. 除根结点之外的所有非终端结点至少有「m/2」棵子树（向上取整）
  4. 所有的非终端结点中包含下列信息数据(n,A_{0} ,K_{1},A_{1},K_{2} ,A_{2},…,K_{n},A_{n})，其中：K_{i}（i=1,…,n）为关键字，且K_{i}<K_{i+1}（i=1,…,n-1）；A_{i}（i=0,…,n）为指向子树根结点的指针，且指针A_{i-1}所指子树中所有结点的关键字均小于K_{i}（i=1,…,n), A_{n} 所指子树中所有结点的关键字均大于K_{n} ，n（m/2-1 <= n <= m-1）为关键字的个数（或n+1为子树个数）
  5. 所有叶子节点在同一个层次。

之前看这个定义的时候，我总会有一些困扰， 后来看了《算法导论》中的定义，发现他的定义我是更能接受的， 最大的特点是不再用阶去定义树，而用节点的最小度（minimum degree），度就是一个节点子树的个数，书中主要给予节点的最小度做了如下限定，假设一棵btree的最小度为t (t>=2),则会有如下属性限制：

  • 除了根节点外， 其他节点的 t-1<=len(key)<= 2t-1
  • 接着上面，如果为非叶子节点，节点的子树个数 t< len(children) <2t,因为非叶子，节点的键个数+1 = 节点的子节点个数

从《计算机程序设计艺术》的属性来看，最小的树为3阶btree, 即2-3树（树的非叶子节点子节点个数为2，3），
从《算法导论》的btree属性定义来看，最小的树为2度树（4阶），即2-3-4树（树的非叶子节点个数可以为2，3，4）

这里顺便引用一下完整的定义：

1) All leaves are at same level.
2) A B-Tree is defined by the term minimum degree ‘t’. The value of t depends upon disk block size.
3) Every node except root must contain at least t-1 keys. Root may contain minimum 1 key.
4) All nodes (including root) may contain at most 2t – 1 keys.
5) Number of children of a node is equal to the number of keys in it plus 1.
6) All keys of a node are sorted in increasing order. The child between two keys k1 and k2 contains all keys in the range from k1 and k2.
7) B-Tree grows and shrinks from the root which is unlike Binary Search Tree. Binary Search Trees grow downward and also shrink from downward.
8) Like other balanced Binary Search Trees, time complexity to search, insert and delete is O(Logn).

Google的这个btree包从定义来看，是按照《算法导论》来定义的，即2-3-4树。

从定义可以看出， b-tree是一种平衡的多路查找树， 与avl树，红黑树等平衡二叉树比起来， b-tree通过多叉，降低了树的高度， 从而减少了查询的次数，一个主要的应用是在数据库系统的索引维护， 由于数据库的索引信息是放在磁盘中，以树形结构存放，假设树高为h, 在查询一个索引时，最多需要进行h次查找，对于磁盘文件来说， 就是h次磁盘读取，所以，b-tree相对于二叉树查询，降低了高度，减少了磁盘读取次数。

一次磁盘读取耗时 = 寻道时间 + 旋转延时 + 数据读取传输耗时， 寻道即为磁头移动到对应磁道所需时间， 普通机械磁盘寻道时间3-15ms， 旋转时间为磁头移动到对应磁道后，旋转到对应扇区所需要的时间， 通过磁盘的转速我们可以计算出平均旋转耗时. 从这里看出，磁盘io是个很低效的事情

单元测试


在设计一个库的时候， 第一步是确定库要实现的功能，进行功能接口抽象，对于一个btree库， 其应该有基本功能如下：

  1. 初始化btree

    1
    2
    // 传入degree， 初始化一棵空树，确定btreed的节点最小度
    func New(degree int) *BTree {   }

  2. 插入节点

    1
    2
    3
    4
    // 向btree插入item
    //如果item已经在tree中，则返回item
    // 如果是新增节点，则返回nil
    func (t *BTree) ReplaceOrInsert(item Item) Item {}

  3. 删除节点

    1
    2
    3
    // 如果item 存在，则从树中删除，并返回item
    // 如果要删除的item 不存在，则返回nil
    func (t *BTree) Delete(item Item) Item {}

确定了这些基本功能抽象之后，我们要做什么呢，去实现接口吗？《重构》告诉我们， 我们也可以先思考接口的单元测试怎么设计。同时，对于包的用户来说，单元测试也是一个让用户了解包功能和如何使用的地图。 来说说btree包单元测试的设计思路：

  1. 先初始化一个btree

  2. 对0-10000的所有整数做随机全排列得到set,依次插入到btree中，每次插入判断返回值是否为nil（因为set中值不重复，每次插入都是增加新节点，所以每次预期返回值都是nil）

  3. 将步骤2中对set再依次插入到btree中(经过步骤2后， 本轮插入的节点预期应该都已存在，所以，每次插入对返回都不为nil)

  4. 将步骤2，步骤3循环执行10次， 以保证代码对测试覆盖度，每次循环完毕判断当前btree是否变为空树。

摘一段btree包对单元测试代码：
代码里可以看到，btree提供了Min(), Max()方法来获取树中最大最小值

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
47
48
49

func TestBTree(t *testing.T) {
    tr := New(*btreeDegree)
    const treeSize = 10000
    for i := 0; i < 10; i++ {
        if min := tr.Min(); min != nil {
            t.Fatalf("empty min, got %+v", min)
        }
        if max := tr.Max(); max != nil {
            t.Fatalf("empty max, got %+v", max)
        }
        for _, item := range perm(treeSize) {
            if x := tr.ReplaceOrInsert(item); x != nil {
                t.Fatal("insert found item", item)
            }
        }
        for _, item := range perm(treeSize) {
            if x := tr.ReplaceOrInsert(item); x == nil {
                t.Fatal("insert didn't find item", item)
            }
        }
        if min, want := tr.Min(), Item(Int(0)); min != want {
            t.Fatalf("min: want %+v, got %+v", want, min)
        }
        if max, want := tr.Max(), Item(Int(treeSize-1)); max != want {
            t.Fatalf("max: want %+v, got %+v", want, max)
        }
        got := all(tr)
        want := rang(treeSize)
        if !reflect.DeepEqual(got, want) {
            t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
        }

        gotrev := allrev(tr)
        wantrev := rangrev(treeSize)
        if !reflect.DeepEqual(gotrev, wantrev) {
            t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
        }

        for _, item := range perm(treeSize) {
            if x := tr.Delete(item); x == nil {
                t.Fatalf("didn't find %v", item)
            }
        }
        if got = all(tr); len(got) > 0 {
            t.Fatalf("some left!: %v", got)
        }
    }
}

随机全排列集合的生成方法

单元测试中，实现了一个随机全排列集合的获取函数perm, 其实是依赖了golang基础包rand的一个方法，rand.Perm(n), rand.Perm(n)会返回一个[0,n)所有整数等随机全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
func init() {
    seed := time.Now().Unix()
    fmt.Println(seed)
    rand.Seed(seed)
}

// perm returns a random permutation of n Int items in the range [0, n).
func perm(n int) (out []Item) {
    for _, v := range rand.Perm(n) {
        out = append(out, Int(v))
    }
    return
}

再跳到rand.Perm()看是如何实现的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Perm returns, as a slice of n ints, a pseudo-random permutation of the integers [0,n).
func (r *Rand) Perm(n int) []int {
    m := make([]int, n)
    // In the following loop, the iteration when i=0 always swaps m[0] with m[0].
    // A change to remove this useless iteration is to assign 1 to i in the init
    // statement. But Perm also effects r. Making this change will affect
    // the final state of r. So this change can't be made for compatibility
    // reasons for Go 1.
    for i := 0; i < n; i++ {
        j := r.Intn(i + 1) 
        //每次循环，选择一个0到i之间的伪随机数j, 
        // 然后执行i，j内容swap. 其实就是一个完整的shuffle函数。
        m[i] = m[j]
        m[j] = i
    }
    return m
}

～ 待续（节点的插入， 节点的删除）