关于b+树:数据结构-B树B树B-树

一、B- 树

1. B- 树是一种多路搜寻树（并不一定是二叉的）

1970 年，R.Bayer 和 E.mccreight 提出了一种实用于外查找的树，它是一种均衡的多叉树，称为 B 树（或 B - 树、B_树）。

2. 一棵 m 阶 B 树 (balanced tree of order m) 是一棵均衡的 m 路搜寻树。它或者是空树，或者是满足下列性质的树：

1. 根结点至多有两个子女；
2. 每个非根节点所蕴含的关键字个数 j 满足：┌m/2┐ – 1 <= j <= m – 1；
3. 除根结点以外的所有结点（不包含叶子结点）的度数正好是关键字总数加 1，故外部子树个数 k 满足：┌m/2┐ <= k <= m；
4. 所有的叶子结点都位于同一层。

二、特点：

是一种多路搜寻树（并不是二叉的）：

1. 定义任意非叶子结点最多只有 M 个儿子；且 M >2；
2. 根结点的儿子数为[2, M]；
3. 除根结点以外的非叶子结点的儿子数为[M/2, M]；
4. 每个结点寄存至多 M /2-1（取上整）和至少 M - 1 个关键字；（至多 2 个关键字）
5. 非叶子结点的关键字个数 = 指向儿子的指针个数 -1；
6. 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且 K[i] < K[i+1]；
7. 非叶子结点的指针：P[1], P[2], …, P[M]；其中 P[1]指向关键字小于 K[1]的子树，P[M]指向关键字大于 K[M-1]的子树，其它 P[i]指向关键字属于 (K[i-1], K[i]) 的子树；
8. 所有叶子结点位于同一层；

如：（M=3）

B- 树的搜寻，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果

命中则完结，否则进入查问关键字所属范畴的儿子结点；反复，直到所对应的儿子指针为

空，或曾经是叶子结点；

三、B- 树的个性：

1. 关键字汇合散布在整颗树中；
2. 任何一个关键字呈现且只呈现在一个结点中；
3. 搜寻有可能在非叶子结点完结；
4. 其搜寻性能等价于在关键字选集内做一次二分查找；
5. 主动档次管制；

四、B+ 树

B+ 树是一种树数据结构，是一个 n 叉树，每个节点通常有多个孩子，一棵 B + 树蕴含根节点、外部节点和叶子节点。根节点可能是一个叶子节点，也可能是一个蕴含两个或两个以上孩子节点的节点。

五、用处：

B+ 树通常用于数据库和操作系统的文件系统中。NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和 BFS 等文件系统都在应用 B + 树作为元数据索引。B+ 树的特点是可能保持数据稳固有序，其插入与批改领有较稳固的对数工夫复杂度。B+ 树元素自底向上插入。

六、B+ 树的定义

1. B+ 树是应文件系统所需而出的一种 B - 树的变型树。一棵 m 阶的 B + 树和 m 阶的 B - 树的差别在于：

1. 有 n 棵子树的结点中含有 n 个关键字，每个关键字不保留数据，只用来索引，所有数据都保留在叶子节点。
2. 所有的叶子结点中蕴含了全副关键字的信息，及指向含这些关键字记录的指针，且叶子结点自身依关键字的大小自小而大程序链接。
3. 所有的非终端结点能够看成是索引局部，结点中仅含其子树（根结点）中的最大（或最小）关键字。
   通常在 B + 树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

2. B+ 树是 B - 树的变体，也是一种多路搜寻树：

1. 其定义根本与 B - 树同，除了：
2. 非叶子结点的子树指针与关键字个数雷同；
3. 非叶子结点的子树指针 P[i]，指向关键字值属于 [K[i], K[i+1]) 的子树（B- 树是开区间）；
4. 为所有叶子结点减少一个链指针；
5. 所有关键字都在叶子结点呈现；

如：（M=3）

B+ 的搜寻与 B - 树也基本相同，区别是 B + 树只有达到叶子结点才命中（B- 树能够在

非叶子结点命中），其性能也等价于在关键字选集做一次二分查找；

七、B+ 的个性：

1. 所有关键字都呈现在叶子结点的链表中（浓密索引），且链表中的关键字恰好是有序的；
2. 不可能在非叶子结点命中；
3. 非叶子结点相当于是叶子结点的索引（稠密索引），叶子结点相当于是存储（关键字）数据的数据层；
4. 更适宜文件索引零碎；

八、B* 树：

1. 是 B + 树的变体，在 B + 树的非根和非叶子结点再减少指向兄弟的指针；

2. B*树定义了非叶子结点关键字个数至多为(2/3)*M，即块的最低使用率为 2 /3（代替 B + 树的 1 /2）；

B+ 树的决裂：当一个结点满时，调配一个新的结点，并将原结点中 1 / 2 的数据复制到新结点，最初在父结点中减少新结点的指针；B+ 树的决裂只影响原结点和父结点，而不会影响兄弟结点，所以它不须要指向兄弟的指针；

B_树的决裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字（因为兄弟结点的关键字范畴扭转了）；如果兄弟也满了，则在原结点与兄弟结点之间减少新结点，并各复制 1 / 3 的数据到新结点，最初在父结点减少新结点的指针；所以，B_树调配新结点的概率比 B + 树要低，空间使用率更高；

九、小结：

1. B- 树：

多路搜寻树，每个结点存储 M / 2 到 M 个关键字，非叶子结点存储指向关键字范畴的子结点；所有关键字在整颗树中呈现，且只呈现一次，非叶子结点能够命中；

2. B+ 树：

在 B - 树根底上，为叶子结点减少链表指针，所有关键字都在叶子结点中呈现，非叶子结点作为叶子结点的索引；B+ 树总是到叶子结点才命；

3. B*树：

在 B + 树根底上，为非叶子结点也减少链表指针，将结点的最低利用率从 1 / 2 进步到 2 /3；

十、B- 树，B+ 树与 B * 树的优缺点比拟

首先留神：B 树就是 B - 树，”-“ 是个连字符号，不是减号。

B- 树是一种均衡的多路查找 (又称排序) 树，在文件系统中有所利用。次要用作文件的索引。其中的 B 就示意均衡(Balance)

B+ 树有一个最大的益处，不便扫库，B 树必须用中序遍历的办法按序扫库，而 B + 树间接从叶子结点挨个扫一遍就完了。

B+ 树反对 range-query(区间查问)十分不便，而 B 树不反对。这是数据库选用 B + 树的最次要起因。

比方要查 5-10 之间的，B+ 树一把到 5 这个标记，再一把到 10，而后串起来就行了，B 树就十分麻烦。B 树的益处，就是胜利查问特地无利，因为树的高度总体要比 B + 树矮。不胜利的状况下，B 树也比 B + 树稍稍占一点点便宜。

B 树的劣势是当你要查找的值恰好处在一个非叶子节点时，查找到该节点就会胜利并完结查问，而 B + 树因为非叶节点只是索引局部，这些节点中只含有其子树中的最大 (或最小) 关键字，当非终端节点上的关键字等于给点值时，查找并不终止，而是持续向下直到叶子节点。因而在 B + 树中，无论查找胜利与否，都是走了一条从根到叶子节点的门路。

有很多基于频率的搜寻是选用 B 树，越频繁 query 的结点越往根上走，前提是须要对 query 做统计，而且要对 key 做一些变动。
另外 B 树也好 B + 树也好，根或者下面几层因为被重复 query，所以这几块根本都在内存中，不会呈现读磁盘 IO，个别已启动的时候，就会被动换入内存。mysql 底层存储是用 B + 树实现的，因为内存中 B + 树是没有劣势的，然而一到磁盘，B+ 树的威力就进去了。

B* 树

是 B + 树的变体，在 B + 树的非根和非叶子结点再减少指向兄弟的指针；B_树定义了非叶子结点关键字个数至多为(2/3)_M，即块的最低使用率为 2 /3（代替 B + 树的 1 /2）；

B+ 树的决裂：当一个结点满时，调配一个新的结点，并将原结点中 1 / 2 的数据复制到新结点，最初在父结点中减少新结点的指针；B+ 树的决裂只影响原结点和父结点，而不会影响兄弟结点，所以它不须要指向兄弟的指针；

B*树的决裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最初批改父结点中兄弟结点的关键字（因为兄弟结点的关键字范畴扭转了）；如果兄弟也满了，则在原结点与兄弟结点之间减少新结点，并各复制 1 / 3 的数据到新结点，最初在父结点减少新结点的指针；所以，B* 树调配新结点的概率比 B + 树要低，空间使用率更高；