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

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

一 概述

1
2
1.B+树和B-树差异
2.B+树图示

二 B+树和B-树差异

1
2
3
4
5
6
7
8
9
一颗 m 阶的 B+树和 m 阶的 B-树的差异在于：
1.有 n 棵子树的结点中含有 n 个关键字；
在上一节中，在 B-树中的每个结点关键字个数 n 的取值范围为⌈ m/2⌉ -1≤n≤m-1，
而在 B+树中每个结点中关键字个数 n 的取值范围为：⌈ m/2⌉ ≤n≤m。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，
且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点（非叶子结点）可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。

三 B+树图示

3.1 图示

1
2
3
4
例如，图 1 中所示的就是一棵深度为 4 的 3 阶 B+树：

如图 1 所示，B+树中含有两个头指针，一个指向整棵树的根结点，另一个指向关键字最小的叶子结点。
同时所有的叶子结点依据其关键字的大小自小而大顺序链接，所有的叶子结点构成了一个 sqt 指针为头指针的链表。

3.2 说明

1
2
3
4
5
6
7
8
所有，B+树可以进行两种查找运算：
一种是利用 sqt 链表做顺序查找，另一种是从树的根结点开始，进行类似于二分查找的查找方式。

在 B+树中，所有非终端结点都相当于是终端结点的索引，而所有的关键字都存放在终端结点中，
所有在从根结点出发做查找操作时，如果非终端结点上的关键字恰好等于给定值，
此时并不算查找完成，而是要继续向下直到叶子结点。

B+树的查找操作，无论查找成功与否，每次查找操作都是走了一条从根结点到叶子结点的路径。

四 参考

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