B+树tips

作者: Jiafu | 来源:发表于2020-01-27 11:14 被阅读0次
    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+树的应用

    用于存储索引数据。

    相关文章

      网友评论

        本文标题:B+树tips

        本文链接:https://www.haomeiwen.com/subject/phasthtx.html