数据结构与算法——第9章-查找表-什么是B-树(9.9.1)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
4
1.B-树特性
2.结点结构
3.B-树图示
4.B-树查找过程

二 B-树特性

1
2
3
4
5
6
B-树，有时又写为 B_树（其中的“-”或者“_”只是连字符，并不读作“B 减树”），
一颗 m 阶的 B-树，或者本身是空树，否则必须满足以下特性：
1.树中每个结点至多有 m 棵子树；
2.若根结点不是叶子结点，则至少有两棵子树；
3.除根之外的所有非终端结点至少有棵子树；
3.所有的非终端结点中包含下列信息数据：（n，A 0 ，K 1 ，A 1 ，K 2 ，A 2 ，…，K n ，A n ）；

三 结点结构

1
2
3
4
n 表示结点中包含的关键字的个数，取值范围是：⌈ m/2⌉ -1≤ n ≤m-1。K i （i 从 1 到 n）为关键字，
且 K i < K i+1 ；
A i 代表指向子树根结点的指针，且指针 A i-1 所指的子树中所有结点的关键字都小于 K i ，
A n 所指子树中所有的结点的关键字都大于 K n。

1
2
3
如图 1 所示，当前结点中有 4 个关键字，之间的关系为：K 1 <K 2 <k 3 <K 4 。
同时对于 A 0 指针指向的子树中的所有关键字来说，其值都要比 K 1 小；
而 A 1 指向的子树中的所有的关键字的值，都比 K 1 大，但是都要比 K 2 小。

四 B-树图示

1
2
所有的叶子结点都出现在同一层次，实际上这些结点都不存在，指向这些结点的指针都为 NULL；
例如图 2 所示就是一棵 4 阶的 B-树，这棵树的深度为 4 ：

五 B-树查找过程

1
2
3
4
5
6
7
8
9
在使用 B-树进行查找操作时，例如在如图 2 所示的 B-树中查找关键字 47 的过程为：
1. 从整棵树的根结点开始，由于根结点只有一个关键字35，且35 < 47，
所以如果47存在于这棵树中，肯定位于A 1 指针指向的右子树中；
2. 然后顺着指针找到存有关键字 43 和 78 的结点，由于 43 < 47 < 78，
所以如果 47 存在，肯定位于 A 1 所指的子树中；
3. 然后找到存有 47、53 和 64 三个关键字的结点，最终找到 47 ，查找操作结束；

以图 2 中的 B-树为例，若查找到深度为 3 的结点还没结束，则会进入叶子结点，
但是由于叶子结点本身不存储任何信息，全部为 NULL，所以查找失败。

六 参考

  • C语言中文网—B-树及其基本操作