B+树tips

B+树定义

一个m阶B+树定义：

1. 每一个节点最多有 m 个子节点
2. 每一个非叶子节点（除根节点）最少有 ⌈m/2⌉ 个子节点
3. 如果根节点不是叶子节点，那么它至少有两个子节点
4. 有 k 个子节点的非叶子节点拥有 k − 1 个键
5. 所有的叶子节点都在同一层
6. 内部节点只有key，没有value。
7. 所有key都出现在叶子节点。
8. 所有叶子节点用链表链接起来。

B+树和B-树的区别

1~5实际上是B-tree的定义，而B+ tree相当于是B-tree的变种，具体的变化就体现在6~8这几条。所以B+tree相对于B-tree有哪些好处呢？由于内部节点只有key，没有value，所以同样大小的节点可以放下更多的key，因此树的高度更低了，查找也会更快。所有叶子节点用链表链接后，遍历效率高很多。

搜索

k表示待搜索的key，d表示key的个数，下面的伪码表示了搜索过程，并且假设key值是不重复的，且key值一定存在。

function search(k) is
    return tree_search(k, root)
 
function: tree_search(k, node) is
    if node is a leaf then
        return node
    switch k do
    case k ≤ k_0
        return tree_search(k, p_0)
    case k_i < k ≤ k_{i+1}
        return tree_search(k, p_{i+1})
    case k_d < k
        return tree_search(k, p_{d})

伪码来自wiki B+tree。

B+树的插入删除

B+树的插入伴随着节点的新建和拆分，是一个自底向上的过程，以后有用到再补充吧。

B+树的应用

用于存储索引数据。