视频课程
小黑屋思过中,禁止观看!
评论并刷新后可见

您需要在视频最下面评论并刷新后,方可查看完整视频

视频课程
立即观看
付费视频

您支付费用,方可查看完整视频

¥{{user.role.value}}
课程视频
开始学习
会员专享

视频合集

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树的应用场景

评论交流
    说说你的看法