树(7)B-树

Published on with 0 views and 0 comments

为什么需要 B-树?

B-树是一种平衡的多路查找树,注意: B 树就是 B-树,"-"是个连字符号,不是减号 。 在大多数的平衡查找树(Self-balancing search trees),比如 AVL 树 和红黑树,都假设所有的数据放在主存当中。那为什么要使用 B-树呢(或者说为啥要有 B-树呢)?要解释清楚这一点,我们假设我们的数据量达到了亿级别,主存当中根本存储不下,我们只能以块的形式从磁盘读取数据,与主存的访问时间相比,磁盘的 I/O 操作相当耗时,而提出 B-树的主要目的就是减少磁盘的 I/O 操作。大多数平衡树的操作(查找、插入、删除,最大值、最小值等等)需要 [公式] 次磁盘访问操作,其中 [公式] 是树的高度。但是对于 B-树而言,树的高度将不再是 [公式] (其中 [公式] 是树中的结点个数),而是一个我们可控的高度 [公式] (通过调整 B-树中结点所包含的键【你也可以叫做数据库中的索引,本质上就是在磁盘上的一个位置信息】的数目,使得 B-树的高度保持一个较小的值)。一般而言,B-树的结点所包含的键的数目和磁盘块大小一样,从数个到数千个不等。由于 B-树的高度 h 可控(一般远小于 [公式] ),所以与 AVL 树和红黑树相比,B-树的磁盘访问时间将极大地降低。

我们之前谈过红黑树与 AVL 树相比较,红黑树更好一些,这里我们将红黑树与 B-树进行比较,并以一个例子对第一段的内容进行解释。

假设我们现在有 838,8608 条记录,对于红黑树而言,树的高度 [公式] ,也就是说如果要查找到叶子结点需要 23 次磁盘 I/O 操作;但是 B-树,情况就不同了,假设每一个结点可以包含 8 个键(当然真实情况下没有这么平均,有的结点包含的键可能比 8 多一些,有些比 8 少一些),那么整颗树的高度将最多 8 ([公式] ) 层,也就意味着磁盘查找一个叶子结点上的键的磁盘访问时间只有 8 次,这就是 B-树提出来的原因所在。

B 树的特征

image20220408111443zpqceuo.png

一个 m 阶的 B 树具有如下几个特征:

1.根结点至少有两个子女。

2.每个中间节点都包含 k-1 个元素和 k 个孩子,其中 m/2 <= k <= m

3.每一个叶子节点都包含 k-1 个元素,其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。

B 树的插入

以上图自顶向下查找 4 的节点位置,发现 4 应当插入到节点元素 3,5 之间。
image20220408111539tczqw1b.png

节点 3,5 已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点 9 是单元素节点,可以升级为两元素节点。于是拆分节点 3,5 与节点 2,6,让根节点 9 升级为两元素节点 4,9。节点 6 独立为根节点的第二个孩子。
image20220408111705nza499o.png

B 树的删除

自顶向下查找元素 11 的节点位置。
image202204081117454djyjsk.png

删除 11 后,节点 12 只有一个孩子,不符合 B 树规范。因此找出 12,13,15 三个节点的中位数 13,取代节点 12,而节点 12 自身下移成为第一个孩子。(这个过程称为 左旋
image20220408111815lu2a5he.png

B 树的应用

由于 B 树比较矮胖,适合磁盘 IO,所以常用于文件系统以及部分数据库索引,比如 MongoDB


标题:树(7)B-树
作者:cuijianzhe
地址:https://cjzshilong.cn/articles/2022/04/08/1649401388460.html