三 . B树、B+树、B*树

3.1 B树(B-树)

3.1.1 B树简介

• B-树是一种多路搜索树（并不一定是二叉的）
• 1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

B-Tree的接点结构B-tree中，每个结点包含：

本结点所含关键字的个数；
指向父结点的指针；
关键字；
指向子结点的指针数组；

一棵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、所有的叶子结点都位于同一层。

3.1.2 B树特点

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

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. 所有叶子结点位于同一层；

3.1.3 B树的查找

在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。

1. 若在某结点内找到待查的关键字K，则返回该结点的地址及K在key[1..keynum]中的位置；
2. 否则，确定K在某个key[i]和key[i+1]之间结点后，从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

查找操作的时间开销

B-树上的查找有两个基本步骤：

1. 在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；
2. 在结点内查找，该查找属内查找。

查找操作的时间为：

1. 外查找的读盘次数不超过树高h，故其时间是O(h)；
2. 内查找中，每个结点内的关键字数目keynum

注意：

1. 实际上外查找时间可能远远大于内查找时间。
2. B-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。

3.1.4 B树的插入

插入一个元素时：

1. 首先判断在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素

注意：
1.1 如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，

1.2 如果叶子节点空间满了以致没有足够的空间去添加新的元素，则将该结点进行"分裂"，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要"分裂"操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。
1.3 如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。

3.1.5 B树的删除

1. 首先查找B树中需删除的元素,如果该元素在B树中存在，则将该元素在其结点中进行删除，
2. 如果删除该元素后，首先判断该元素是否有左右孩子结点，如果有，则上移孩子结点中的某相近元素到父节点中，然后是移动之后的情况；如果没有，直接删除后，移动之后的情况。

3.2 B+树

3.2.1 B+树简介

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

B+树用途

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

3.2.2 B+树定义

B+树是应文件系统所需而出的一种B-树的变型树。

一棵m阶的B+树和m阶的B-树的差异在于：
1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。
通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

B+树与B-树的不同

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

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

3.2.3 B+树的特性：

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

3.2.4 B+树 vs B树

为什么说B+-tree比B 树更适合实际应用中操作系统的文件索引和数据库索引？

• B+-tree的磁盘读写代价更低
  B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
  举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。
• B+-tree的查询效率更加稳定
  由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3.3 B*树

3.3.1 B*树简介

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

3.3.2 B*树 vs B+树

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

• B*树的分裂：
  当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

3.4 小结：

• B-树：
  多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；
  所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

• B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；
  B+树总是到叶子结点才命中；

• B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；