B-Tree

1. B-Tree

平衡多路查找树

一棵 m 阶的 B-Tree, 或为空树, 或为满足以下特性的 m 叉树:

1. 树中的每个结点至多有 m 棵子树
2. 若根结点不是叶子结点, 则至少有 2 棵子树
3. 除根结点外的所有分支结点至少有 $\lceil m/2 \rceil$ 棵子树
   $\lceil m/2 \rceil$ 即不超过 m/2 的整数
4. 所有的非叶子结点中包含下列信息数据: $(n, P_0, K_1, P_1, K_2, P_2, ..., K_n, P_n)$
   n 为关键字数量, $\lceil m/2 \rceil\le n \le m-1$, n+1 为子树个数
   $K_i$(i=1…n) 为关键字, 且关键字按从小到大顺序排列
   $P_{j-1}$(j=0…n) 为指向指向子树的指针, 且关键字 K 左指针指向的子树中的所有关键字都比 K 小, 关键字 K 右指针指向的子树中的所有关键字都比 K 大
5. 所有叶子结点都出现在同一层次, 并且不带信息(可以看作是外部结点或查找失败的结点, 实际上这些结点不存在, 指向这些结点的指针为空)

2. B+Tree

B+Tree 是应文件系统所需而出的 B-Tree 的变型树.

一棵 m 阶的 B-Tree 和一棵 m 阶的 B+Tree 差异在于:

1. 有 n 棵子树的结点中含有 n 个关键字
   关键字个数与指针个数相同
2. 所有的非叶子结点可以看成是索引部分, 结点中仅含有其子树中的最大(或最小)关键字
3. 所有的叶子结点中包含了全部的关键字信息, 及指向含这些关键字记录的指针, 且叶子结点本身按关键字的大小从小到大链接

非叶子不包含数据, 只是索引, 只有叶子结点才包含数据.

通常 B+Tree 上有两个头指针, 一个指向根结点, 另一个指向关键字最小的叶子结点.
因此可以堆 B+Tree 进行两种遍历运算:

• 从根结点开始进行随机查找
• 从最小关键字开始顺序查找

B+Tree 查找时, 如果非叶子结点上的关键字等于给定的值, 并不终止, 而是继续修改下直到叶子结点.

3. B*Tree

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

B+树的分裂: 当一个结点满时, 分配一个新的结点, 并将原结点中1/2的数据复制到新结点, 最后在父结点中增加新结点的指针; B+树的分裂只影响原结点和父结点, 而不会影响兄弟结点, 所以它不需要指向兄弟的指针;
B*树的分裂: 当一个结点满时, 如果它的下一个兄弟结点未满, 那么将一部分数据移到兄弟结点中, 再在原结点插入关键字, 最后修改父结点中兄弟结点的关键字 (因为兄弟结点的关键字范围改变了) ; 如果兄弟也满了, 则在原结点与兄弟结点之间增加新结点, 并各复制1/3的数据到新结点, 最后在父结点增加新结点的指针;