视频合集

    B树与B+树详解

    • 课程笔记
    • 问答交流

    这节课重点会讲解以下7点:

    1.什么是B树
    2.B树的特征
    3.B树的应用场景
    4.什么是B+树
    5.B+树的特征
    6.B+树的应用场景
    7.B树和B+树的区别

    什么是B树

    B树与B+树详解-mikechen
    B树也叫平衡树,一种树状数据结构,英文为Blance-Tree,是一种多路平衡树
    B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。
    也称为:B树(或B-树、B_树)

    B树的特征

    B树与B+树详解-mikechen
    B 树可以看作是对查找树的一种扩展,拥有多于2个子节点的二叉查找树。

    根节点至少有两个子节点
    每个节点有M-1个key,并且以升序排列
    除根节点,其它节点至少有M/2个子节点
    B树中的叶子节点都是处在同一层中,一般都是用空指针表示,表示查找失败。

    B树的时间复杂度

    查找、顺序读取、插入和删除的数据结构: O(log n)的时间复杂度

    O(1):最低的时空复杂度,也就是耗时与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标

    O(n):代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。

    O(logn):当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。

    B树的应用场景

    评论交流
      说说你的看法
    欢迎您,新朋友,感谢参与互动!