本文将为大家介绍 B 树和 B + 树, 首先介绍了 B 树的应用场景, 为什么需要 B 树; 然后介绍了 B 树的查询和插入过程; 最后谈了 B + 树针对 B 树的改进.
在谈 B 树之前, 先说一下 B 树所针对的应用场景. 那么 B 树是用来做什么的呢? B 树是一种为辅助存储设计的一种数据结构, 普遍运用在数据库和文件系统中. 举个例子来说, 数据库大家肯定都不陌生, 比如现在有一张表, 其中有 100 万条记录, 现在要查找查找其中的某条数据, 如何快速地从 100 万条记录中找到需要的那条记录呢? 大家的第一反应肯定是二叉查找树, 下面先谈谈为什么二叉树不行.
为什么二叉查找树不行
还是刚刚那个例子, 现在一张表中有 100 万条记录, 我们以表的主键来构建一个二叉查找树. 先不考虑二叉树不平衡退化成链表的情况, 假设是理想情况, 这个二叉树是完全平衡的. 那么构建完成之后应该是下面这个样子的 (示意图)
树的高度应该为
现在开始查找, 加入我们要查找值为 100 的节点, 怎么找呢? 首先应该获取树的根节点. 一般来说, 表的索引本身也很大, 不可能全部存储在内存中, 因此索引往往以索引文件的形式存储的磁盘上. 也就是说我们构建的二叉查找树太大了, 内存放不下, 一般要存在磁盘上, 用的时候再从磁盘读入到内存. 现在假设我们知道了根节点所在的磁盘位置, 那么应该首先将根节点读入内存中, 这里进行了一次 IO 操作, 然后判断要找的值比根节点大还是小, 100 比 4 大, 所以去右子树查找. 那么如何找到 6 所在的节点呢? 根节点中存储着 6 所在节点在磁盘上存放的位置. 同样, 需要将其先读入内存中, 然后再判断继续向下查找, 这里又是一次 IO 操作. 下面的过程类似, 不再展开. 总结一下, 查找到我们所需的那条记录大概需要进行 20 次 IO 操作, 也就是树的高度, 因为每向下查找一层, 就要进行一次 IO 操作.
为什么要强调 IO 操作, 而不是在内存中比较的次数呢? 因为磁盘的速度相比内存而言是非常的慢. 比如常见的 7200RPM 的硬盘, 摇臂转一圈需要 60/7200≈8.33ms, 换句话说, 让磁盘完整的旋转一圈找到所需要的数据需要 8.33ms, 这比内存常见的 100ns 慢 100000 倍左右, 这还不包括移动摇臂的时间. 所以在这里制约查找速度的不是比较次数, 而是 IO 操作的次数. 换句话说, 如果能够减少一次 IO 操作, 那么多在内存中比较 100 次也无所谓, 因为二者的速度相差 100000 倍. 而我们可以认为 IO 操作的次数就大约等于树的高度, 树的高度是如何计算的呢? 看一下这个公式
我们想让这个值尽可能的小, 就只能让真数小, 或者底数大. 真数是数据记录的条数, 不是我们能决定的. 那么底数呢? 这个 2 来自哪呢? 当然是来自二叉树中的那个二. 那么这个底数能不能变大呢? 当然能!!! 那就是不要用二叉树, 而要用多叉树, 这就是我们要说的 B 树了.
B 树是什么
B 树也称 B - 树, 它是一颗多路平衡查找树. B 树和后面讲到的 B + 树都是从最简单的二叉树变换而来的. 描述一颗 B 树时需要指定它的阶数, 阶数表示了一个节点最多有多少个孩子节点, 一般用字母 m 表示阶数. 下面我们来看看 B 树的定义
(1) 树中每个节点至多有 m 棵子树 (m 指的是树的阶);
解释: 有的定义说的是每个节点最多有 m-1 个关键字, 是一样的, 对于每个节点来说子树的数目等于关键字数目加 1, 下面会举例说明.
(2) 若根结点不是叶子结点, 则至少有两棵子树;
解释: 当根节点为叶子节点时, 可以没有子树; 不为叶子节点时, 至少有一个关键字, 也就是至少有两棵子树.
(3) 除根结点之外的所有非叶子结点至少有m/2个子节点;
解释:m/2表示向上取整, 比如 m=5 时,m/2=3, 表示至少有 3 个子节点, 当然最多有 5 个.
(4) 所有的非叶子结点中包含以下数据:(n,A0,K1,A1,K2,...,Kn,An)
解释: n 为节点中关键字的数目, Ki(i=1,2,...,n) 为关键字, 且 Ki<Ki+1
Ai 为指向孩子节点的指针 (i=0,1,...,n), 且指针 Ai-1 所指子树中所有结点的关键字均小于 Ki (i=1,2,...,n),An 所指子树中所有结点的关键字均大于 Kn.(这里也可以看到对于每个节点来说子节点数量比关键字数量多 1)
(5) 所有的叶子结点都出现在同一层次上, 即所有叶节点具有相同的深度, 等于树高度. 叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为 null.
下面具体举个例子说明, 相信看了这个例子会对上面的定义有更加深刻的理解.
B 树的查找
以上图为例, 假设要查找 15 的节点, 查找流程如下
(1) 获取根节点的关键字进行比较, 当前根节点关键字为 50,50>15, 所以找到指向左边的子节点;
(2) 拿到关键字 10 和 30,10<15<30 所以直接找到 10 和 30 中间的指针指向的子节点;
(3) 拿到关键字 15, 就是要查找的目标值, 所以直接返回关键字和指针信息 (如果树结构里面没有包含所要查找的节点则返回 null)
至此我们便完成了 B 树的查找过程, 比较简单, 且与二叉查找树类似.
关于 B 树的插入操作, 可以参考 [为什么有红黑树? 什么是红黑树? 看完这篇你就明白了] https://mp.weixin.qq.com/s/pwBnKfgivdE5EzBCXubZww 这篇推文中关于 2-3 树的插入操作的详细介绍, 其实 2-3 树就是一种特殊的 B 树. 限于篇幅, 本文不再赘述.
从 B 树到 B + 树
B + 树是从 B 树衍生而来的, 比 B 树更具有优越性. B + 树相对于 B 树主要做了两点改进:
(1) 非叶结点仅具有索引作用, 跟记录有关的信息均存放在叶结点中.
解释: B + 树的非叶子节点不保存关键字记录的指针, 只进行数据索引; B + 树叶子节点保存了父节点的所有关键字记录的指针, 所有数据地址必须要到叶子节点才能获取到. 还是举刚才 B 树的例子, B 树中根节点的关键字为 50. 假如我们就要查找主键为 50 的记录, 那么在 B 树中只需进行一次 IO 操作, 将根节点读入内存, 便可以直接命中. 而在 B + 树中则不同, B + 树中任何查询必须要到叶子节点才能获取到, 所以每次数据查询的次数都一样, 这一点和 B 树有很大区别.
(2) 树的所有叶节点构成一个有序链表, 可以按照关键字排序的次序遍历全部记录.
解释: 这样做有两点好处. 一是进行范围查询更快, 数据紧密性很高, 缓存的命中率也会比 B 树高. 二是 B + 树全节点遍历更快, B + 树遍历整棵树只需要遍历所有的叶子节点即可, 而不需要像 B 树一样需要对每一层进行遍历, 这有利于数据库做全表扫描.
来源: https://www.cnblogs.com/exzlc/p/12208793.html