這是B-Tree合集的第二部分。在這一部分會實現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)和Search。
基本數(shù)據(jù)結(jié)構(gòu)
根據(jù)Part1介紹的B-Tree的屬性，我們可以建立node和tree兩個基本的數(shù)據(jù)結(jié)構(gòu)
type BTreeNode struct {
keys []int // An array of keys
t int // Minimum degree
c []*BTreeNode // An array of child pointers
n int // Current number of keys
leaf bool // Is true when node is leaf. Otherwise false
}
type BTree struct {
root *BTreeNode // Pointer to root node
t int // Minimum degree
}
// Constructor for BTreeNode
func NewBTreeNode(t int, leaf bool) *BTreeNode {
return &BTreeNode{
keys: make([]int, t<<1-1),
t: t,
c: make([]*BTreeNode, t<<1),
leaf: leaf,
}
}
// Constructor (Initializes tree as empty)
func NewBTree(t int) *BTree {
return &BTree{
t: t,
}
}Search
比如要在下面這個B樹中找120
那么從Part1可知，我們都會從root出發(fā)，所以有下面3步即可找到120
可見，可以用下面的偽代碼來描述Search方法
對于紅框里面的，意思是找第一個大于等于k的鍵index，但是偽代碼用了順序查找的方法，即O(N)。從Part1可知，node中的元素是從小到大排列的，所以我們可以用二分的方式優(yōu)化。
// find the index of the first key which is greater or equal to k
func findGE(s []int, left, right, k int) int {
if left <= right {
mid := left + (right-left)>>1
if k == s[mid] {
return mid
} else if k > s[mid] {
return findGE(s, mid+1, right, k)
} else {
return findGE(s, left, mid-1, k)
}
}
return left
}
下面是Search的代碼
func (n *BTreeNode) search(k int) *BTreeNode {
i := findGE(n.keys, 0, n.n-1, k)
if n.keys[i] == k {
return n
}
if n.leaf {
return nil
}
return n.c[i].search(k)
}
func (t *BTree) Search(k int) *BTreeNode {
if t.root != nil {
return t.root.search(k)
}
return nil
}在下次的Part3中，將實現(xiàn)B-Tree的Insert。
