B-Tree

struct

B 树的定义中多了一个字段 m，m 表示的是 B 树的阶数，这是 m 阶 B 树的定义：

1. 除根结点外所有节点关键字个数范围
2. 若非叶子节点含 n 个关键字，则子树有 n + 1 个，由关键字范围可知子树的个数范围为
3. 根结点至少包含一个关键字，至少有两个儿子（除非这棵树只有一个节点，根结点），根结点的关键字个数范围为 孩子数范围为
4. 所有叶子节点都在同一层，即高度都一样
5. 每个节点的关键字从小到大排列，节点当中 k - 1 个元素正好是 k 个孩子包含的元素的值域的划分 ```go type Tree struct { Root *Node
   Comparator utils.Comparator size int
   m int
   }

type Node struct { Parent Node Entries []Entry Children []*Node
}

type Entry struct { Key interface{} Value interface{} }

我们可以看到 Entry 就是要存储的数据，每个 Node 内可以存储多个 Entry，也可以有多个 Child
<a name="search"></a>
## search
因为 B 树终于不是二叉树了，我们进行搜索就不能简单的比较之后向左向右了，虽然这各函数名字叫做递归的搜索，但是并没有看出来这个函数内存在递归的内容啊，相反它是使用的循环来完成的，这里循环调用 search<br />函数，每次调用完成后如果 found 不为 true ，并且不是叶子节点，那就向下一层，并且进入的是第 index 各子节点，所以我们需要进入 `search()`  来看一看 index 是怎么找到的。
```go
func (tree *Tree) searchRecursively(startNode *Node, key interface{}) (node *Node, index int, found bool) {
    if tree.Empty() {
        return nil, -1, false
    }
    node = startNode
    for {
        index, found = tree.search(node, key)
        if found {
            return node, index, true
        }
        if tree.isLeaf(node) {
            return nil, -1, false
        }
        node = node.Children[index]
    }
}

search() 的主体也是一个 for 循环，这就是一个二分查找，每次取中间值进行对比，然后根据结果改变下一次需要查找的位置，如果没有找到返回的是 low 的值，也就是这里的 low 就是 index 的值，所以 node.Entry[ low ].Key < key ，而且 node.Entry[ high ].Key > key ，low 所对应的 Key 在这里实际的意思是小于新插入的 Key 的最大关键字，所以这个节点的范围勘定包含需要查找的 key。

func (tree *Tree) search(node *Node, key interface{}) (index int, found bool) {
    low, high := 0, len(node.Entries)-1
    var mid int
    for low <= high {
        mid = (high + low) / 2
        compare := tree.Comparator(key, node.Entries[mid].Key)
        switch {
        case compare > 0:
            low = mid + 1
        case compare < 0:
            high = mid - 1
        case compare == 0:
            return mid, true
        }
    }
    return low, false

Put

很清楚的看到，这里 Put() 只是新建了一个 Entry，并没有真正的完成插入，实际上操作的是这个 insert() 。
这里插入函数分成了两种，一种是直接插入到叶子里，另一种是插入到中间节点的，我们观察后发现，插入到中间节点的其实递归调用了 insert 这个函数，也就是说插入中间节点的情况，最终肯定也被转化为了插入到叶子节点的，我们来看看这个转化是怎么完成的。
这里先查找是否在这个节点中存在 Key 值相同的节点，如果存在，那就直接插入失败，否则再次调用 Insert() ，不过这次插入的位置是它的子节点中。这个过程其实上就是函数 searchRecursively() 的递归过程，其实这个才应该叫做递归啊？

func (tree *Tree) insert(node *Node, entry *Entry) (inserted bool) {
    if tree.isLeaf(node) {
        return tree.insertIntoLeaf(node, entry)
    }
    return tree.insertIntoInternal(node, entry)
}
func (tree *Tree) insertIntoInternal(node *Node, entry *Entry) (inserted bool) {
    insertPosition, found := tree.search(node, entry.Key)
    if found {
        node.Entries[insertPosition] = entry
        return false
    }
    return tree.insert(node.Children[insertPosition], entry)
}

当我们一直递归直到进入了叶子节点中，插入才开始真正的进行，首先依旧是先查看是否有冲突的关键字，如果没有，那就将新的 Entry 插入到 insertPosition + 1 的位置。现在我们已经完成了对新节点的插入，但是实际上，最重要的是检查这棵树是否满足 B 树的定义，也就是它的关键字数目是否在 这个区间内，当然我们还需要注意如果这个节点是根结点它的范围是 ，不过对于插入来说是不需要考虑下界的，所以它和普通节点也没有区别。

如果我们的节点关键字个数超过了规定的范围，就需要将这个节点进行分裂（其实还可以将一个关键字给兄弟节点，但是这里没有实现），分裂的操作首先是先将这个节点分为两份，然后将中间一个关键字给父节点，然后这个节点的两端就可以存储新增的两个节点了，但是这样父节点就增加了一个关键字，所以还需要检查父节点是否满足关键字范围。

func (tree *Tree) splitNonRoot(node *Node) {
    middle := tree.middle() // 取出中间位置，因为需要分裂，所以节点中肯定有 m 个关键字
    parent := node.Parent
    left := &Node{Entries: append([]*Entry(nil), node.Entries[:middle]...), Parent: parent}
    right := &Node{Entries: append([]*Entry(nil), node.Entries[middle+1:]...), Parent: parent}
    // 如果不是叶子节点，还需要把子树也分配给左右节点
    if !tree.isLeaf(node) {
        left.Children = append([]*Node(nil), node.Children[:middle+1]...)
        right.Children = append([]*Node(nil), node.Children[middle+1:]...)
        setParent(left.Children, left)
        setParent(right.Children, right)
    }
    insertPosition, _ := tree.search(parent, node.Entries[middle].Key)
    // 将中间节点插入到父节点中
    parent.Entries = append(parent.Entries, nil) // 先将底层数组扩容
    copy(parent.Entries[insertPosition+1:], parent.Entries[insertPosition:]) // 然后复制剩下的元素，最后一个 nil 会溢出
    parent.Entries[insertPosition] = node.Entries[middle]
    // 将分裂的左节点插入到父节点中
    parent.Children[insertPosition] = left
    // 将分裂的右节点插入到父节点中
    parent.Children = append(parent.Children, nil)
    copy(parent.Children[insertPosition+2:], parent.Children[insertPosition+1:])
    parent.Children[insertPosition+1] = right
    tree.split(parent)
}

因为根结点没有父节点，所以新生成的关键字就作为新的根结点被存储在结构体中

Remove

类似于 Put() 在这 Remove() 也没有真正的有删除代码，所有的实现还在 delete() 中，这里只是通过 key 调用 search 找到了需要删除的节点的位置而已。
首先如果需要删除的节点是叶子节点，那就可以直接删除，如果是中间节点，那就将他左子树中的最右面节点的最后一个元素作为现在这个位置的值，这就将删除中间节点转化为了删除叶子节点。所以我们调用 reblance() 的时候传入的都是叶子节点，

func (tree *Tree) rebalance(node *Node, deletedKey interface{}) {
    // 检查是否需要重新平衡，其实就是节点关键字是否小于最小值。
    if node == nil || len(node.Entries) >= tree.minEntries() {
        return
    }
    // 从左兄弟节点借一个
    leftSibling, leftSiblingIndex := tree.leftSibling(node, deletedKey)
    if leftSibling != nil && len(leftSibling.Entries) > tree.minEntries() {
        // rotate right
        node.Entries = append([]*Entry{node.Parent.Entries[leftSiblingIndex]}, node.Entries...) // prepend parent's separator entry to node's entries
        node.Parent.Entries[leftSiblingIndex] = leftSibling.Entries[len(leftSibling.Entries)-1]
        tree.deleteEntry(leftSibling, len(leftSibling.Entries)-1)
        if !tree.isLeaf(leftSibling) {
            leftSiblingRightMostChild := leftSibling.Children[len(leftSibling.Children)-1]
            leftSiblingRightMostChild.Parent = node
            node.Children = append([]*Node{leftSiblingRightMostChild}, node.Children...)
            tree.deleteChild(leftSibling, len(leftSibling.Children)-1)
        }
        return
    }
    // 从右兄弟节点借一个
    rightSibling, rightSiblingIndex := tree.rightSibling(node, deletedKey)
    if rightSibling != nil && len(rightSibling.Entries) > tree.minEntries() {
        // rotate left
        node.Entries = append(node.Entries, node.Parent.Entries[rightSiblingIndex-1]) // append parent's separator entry to node's entries
        node.Parent.Entries[rightSiblingIndex-1] = rightSibling.Entries[0]
        tree.deleteEntry(rightSibling, 0)
        if !tree.isLeaf(rightSibling) {
            rightSiblingLeftMostChild := rightSibling.Children[0]
            rightSiblingLeftMostChild.Parent = node
            node.Children = append(node.Children, rightSiblingLeftMostChild)
            tree.deleteChild(rightSibling, 0)
        }
        return
    }
    // 合并兄弟节点
    if rightSibling != nil {
        // merge with right sibling
        node.Entries = append(node.Entries, node.Parent.Entries[rightSiblingIndex-1])
        node.Entries = append(node.Entries, rightSibling.Entries...)
        deletedKey = node.Parent.Entries[rightSiblingIndex-1].Key
        tree.deleteEntry(node.Parent, rightSiblingIndex-1)
        tree.appendChildren(node.Parent.Children[rightSiblingIndex], node)
        tree.deleteChild(node.Parent, rightSiblingIndex)
    } else if leftSibling != nil {
        // merge with left sibling
        entries := append([]*Entry(nil), leftSibling.Entries...)
        entries = append(entries, node.Parent.Entries[leftSiblingIndex])
        node.Entries = append(entries, node.Entries...)
        deletedKey = node.Parent.Entries[leftSiblingIndex].Key
        tree.deleteEntry(node.Parent, leftSiblingIndex)
        tree.prependChildren(node.Parent.Children[leftSiblingIndex], node)
        tree.deleteChild(node.Parent, leftSiblingIndex)
    }
    // make the merged node the root if its parent was the root and the root is empty
    if node.Parent == tree.Root && len(tree.Root.Entries) == 0 {
        tree.Root = node
        node.Parent = nil
        return
    }
    // parent might underflow, so try to rebalance if necessary
    tree.rebalance(node.Parent, deletedKey)
}