1. B-Tree

1.1. B-Tree的节点结构

  1. class BTreeNode {
  2.     //关键字数量
  3.     int keyNum;
  5.     //关键字数组
  6.     Integer[] key;
  8.     //指向父节点
  9.     BTreeNode parent;
  11.     //指向孩子节点的节点数组
  12.     BTreeNode[] son;
  14.     public BTreeNode(int keyNum, BTreeNode parent){
  15.         this.keyNum = keyNum;
  16.         this.key = new Integer[keyNum];
  17.         this.parent = parent;
  18.         this.son = new BTreeNode[keyNum+1];
  19.     }
  21.     // 其他成员方法省略
  22.     public void otherMethods(){}
  23. }

1.2. B-Tree的特点：

B树的度M：非叶子节点最多有M个孩子，最少有M/2个孩子
B树关键字个数：M-1

  • B-tree是一种多路搜索树（并不是二叉的），对于一棵M阶树：
  • 定义任意非叶子结点最多只有M个孩子；且M>2；
  • 根结点的孩子数为[2, M]，除非根结点为叶子节点；
  • 除根结点以外的非叶子结点的儿子数为[M/2, M]；
  • 非叶子结点的关键字个数=指向儿子的指针个数-1；
  • 每个非叶子结点存放至少M/2-1（取上整）和至多M-1个关键字；
  • 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
  • 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
  • 所有叶子结点位于同一层；

例：2-3树——每个非叶子节点存放 1-2个关键字，每个节点有3个指针。
image.pngimage.pngimage.pngimage.png

1.3. B-Tree高度与复杂度

B树的高度是B-树（含 *） - 图5 ，而不是其他几种树的B-树（含 *） - 图6
其中T为度数（每个节点包含的元素个数），即阶数，n为总元素个数或总关键字个数。

B树查找的时间复杂度为O(log2N)。

1.4. B-Tree的基本操作

（1）查找操作
在B-树中查找给定关键字的方法类似于二叉排序树上的查找。不同的是在每个结点上确定向下查找的路径不一定是二路而是keynum+1路的。
对结点内的存放有序关键字序列的向量key[l..keynum] 用顺序查找或折半查找方法查找。若在某结点内找到待查的关键字K，则返回该结点的地址及K在key[1..keynum]中的位置；否则，确定K在某个key[i]和key[i+1]之间结点后，从磁盘中读son[i]所指的结点继续查找。直到在某结点中查找成功；或直至找到叶结点且叶结点中的查找仍不成功时，查找过程失败。

（2）查找操作的时间开销
B-树上的查找有两个基本步骤：
1.在B-树中查找结点，该查找涉及读盘DiskRead操作，属外查找；
2.在结点内查找，该查找属内查找。
查找操作的时间为：
1.外查找的读盘次数不超过树高h，故其时间是O(h)；
2.内查找中，每个结点内的关键字数目keynum注意：
1.实际上外查找时间可能远远大于内查找时间。
2.B-树作为数据库文件时，打开文件之后就必须将根结点读人内存，而直至文件关闭之前，此根一直驻留在内存中，故查找时可以不计读入根结点的时间。

（3）插入操作
插入一个元素时，首先在B树中是否存在，如果不存在，即在叶子结点处结束，然后在叶子结点中插入该新的元素，注意：如果叶子结点空间足够，这里需要向右移动该叶子结点中大于新插入关键字的元素，如果空间满了以致没有足够的空间去添加新的元素，则将该结点进行“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中（当然，如果父结点空间满了，也同样需要“分裂”操作），而且当结点中关键元素向右移动了，相关的指针也需要向右移。如果在根结点插入新元素，空间满了，则进行分裂操作，这样原来的根结点中的中间关键字元素向上移动到新的根结点中，因此导致树的高度增加一层。

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

1.5. 2-3树

2-3树是最简单的B树结构，具有如下特点：

  1. 2-3树所有叶子节点都在同一层（只要是B树都满足）；
  2. 有两个子节点的节点叫二节点，二节点要么没有子节点，要么有两个子节点；
  3. 有三个子节点的节点叫三节点，三节点要么没有子节点，要么有三个子节点；
  4. 2-3树是由二节点和三节点构成的树。

2. B+ Tree

B+ tree是应文件系统所需而产生的一种B-tree的变形树。
image.png
（1）B树和B+树的对比
一棵m阶的B+树和m阶的B树的异同点在于：
1.有n棵子树的结点中含有n-1 个关键字；
2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息，B+的数据只能在叶子节点命中)
3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

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

  • B+tree的磁盘读写代价更低

B+tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。
如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。
一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。
一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

  • B+tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

3. B* Tree

B*tree是B+tree的变体，在B+树的基础上(所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)，

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

image.png

4. B树、B+树、B*树的优缺点比较

B-树，B+树与B*树的优缺点比较

4.1. B与B+比较：

  • B-树是一种平衡的多路查找(又称排序)树，在文件系统中有所应用。主要用作文件的索引。其中的B就表示平衡(Balance)
  • B+树有一个最大的好处，方便扫库，B树必须用中序遍历的方法按序扫库，而B+树直接从叶子结点挨个扫一遍就完了。
  • B+树支持range-query(区间查询)非常方便，而B树不支持。这是数据库选用B+树的最主要原因。
  • B树成功查询比B+树快：当要查询的值处于一个非叶子节点，B树找到该点成功并结束查询，B+树的非叶节点只是索引部分，需要到叶子节点中获取数据。


4.2. B+与B*比较：

  • B*树是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；B树定义了非叶子结点关键字个数至少为(2/3)M，即块的最低使用率为2/3（代替B+树的1/2）；
  • B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；
  • B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；
  • 所以，B*树分配新结点的概率比B+树要低，空间使用率更高；