B树介绍

B- 树

        是一种多路搜索树&＃xff08;并不是二叉的&＃xff09;&＃xff1a;

       1. 定义任意非叶子结点最多只有 M 个儿子&＃xff1b;且 M>2 &＃xff1b;

       2. 根结点的儿子数为 [2, M] &＃xff1b;

       3. 除根结点以外的非叶子结点的儿子数为 [M/2, M] &＃xff1b;

       4. 每个结点存放至少 M/2-1 &＃xff08;取上整&＃xff09;和至多 M-1 个关键字&＃xff1b;&＃xff08;至少 2 个关键字&＃xff09;

       5. 非叶子结点的关键字个数 &＃61; 指向儿子的指针个数 -1 &＃xff1b;

       6. 非叶子结点的关键字&＃xff1a; K[1], K[2], …, K[M-1] &＃xff1b;且 K[i]

       7. 非叶子结点的指针&＃xff1a; P[1], P[2], …, P[M] &＃xff1b;其中 P[1] 指向关键字小于 K[1] 的子树&＃xff0c; P[M] 指向关键字大于 K[M-1] 的子树&＃xff0c;其它 P[i] 指向关键字属于 (K[i-1], K[i]) 的子树&＃xff1b;

       8. 所有叶子结点位于同一层&＃xff1b;

        如&＃xff1a;&＃xff08; M&＃61;3 &＃xff09;

      ‍ 

       B- 树的搜索&＃xff0c;从根结点开始&＃xff0c;对结点内的关键字&＃xff08;有序&＃xff09;序列进行二分查找&＃xff0c;如果命中则结束&＃xff0c;否则进入查询关键字所属范围的儿子结点&＃xff1b;重复&＃xff0c;直到所对应的儿子指针为空&＃xff0c;或已经是叶子结点&＃xff1b;

B- 树的特性&＃xff1a;

       1. 关键字集合分布在整颗树中&＃xff1b;

       2. 任何一个关键字出现且只出现在一个结点中&＃xff1b;

       3. 搜索有可能在非叶子结点结束&＃xff1b;

       4. 其搜索性能等价于在关键字全集内做一次二分查找&＃xff1b;

       5. 自动层次控制&＃xff1b;

        由于限制了除根结点以外的非叶子结点&＃xff0c;至少含有 M/2 个儿子&＃xff0c;确保了结点的至少利用率&＃xff0c;其最底搜索性能为&＃xff1a;

              ‍

        其中&＃xff0c; M 为设定的非叶子结点最多子树个数&＃xff0c; N 为关键字总数&＃xff1b;

        所以 B- 树的性能总是等价于二分查找&＃xff08;与 M 值无关&＃xff09;&＃xff0c;也就没有 B 树平衡的问题&＃xff1b;

        由于 M/2 的限制&＃xff0c;在插入结点时&＃xff0c;如果结点已满&＃xff0c;需要将结点分裂为两个各占 M/2 的结点&＃xff1b;删除结点时&＃xff0c;需将两个不足 M/2 的兄弟结点合并&＃xff1b;

B&＃43; 树

       B&＃43; 树是 B- 树的变体&＃xff0c;也是一种多路搜索树&＃xff1a;

       1. 其定义基本与 B- 树同&＃xff0c;除了&＃xff1a;

       2. 非叶子结点的子树指针与关键字个数相同&＃xff1b;

       3. 非叶子结点的子树指针 P[i] &＃xff0c;指向关键字值属于 [K[i], K[i&＃43;1]) 的子树&＃xff08; B- 树是开区间&＃xff09;&＃xff1b;

       5. 为所有叶子结点增加一个链指针&＃xff1b;

       6. 所有关键字都在叶子结点出现&＃xff1b;

        如&＃xff1a;&＃xff08; M&＃61;3 &＃xff09;

      ‍ 

    B&＃43; 的搜索与 B- 树也基本相同&＃xff0c;区别是 B&＃43; 树只有达到叶子结点才命中&＃xff08; B- 树可以在非叶子结点命中&＃xff09;&＃xff0c;其性能也等价于在关键字全集做一次二分查找&＃xff1b;

       B&＃43; 的特性&＃xff1a;

       1. 所有关键字都出现在叶子结点的链表中&＃xff08;稠密索引&＃xff09;&＃xff0c;且链表中的关键字恰好是有序的&＃xff1b;

       2. 不可能在非叶子结点命中&＃xff1b;

       3. 非叶子结点相当于是叶子结点的索引&＃xff08;稀疏索引&＃xff09;&＃xff0c;叶子结点相当于是存储&＃xff08;关键字&＃xff09;数据的数据层&＃xff1b;

       4. 更适合文件索引系统&＃xff1b;

B* 树

        是 B&＃43; 树的变体&＃xff0c;在 B&＃43; 树的非根和非叶子结点再增加指向兄弟的指针&＃xff1b;

      ‍ 

    B* 树定义了非叶子结点关键字个数至少为 (2/3)*M &＃xff0c;即块的最低使用率为 2/3 &＃xff08;代替 B&＃43; 树的 1/2 &＃xff09;&＃xff1b;

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

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

        所以&＃xff0c; B* 树分配新结点的概率比 B&＃43; 树要低&＃xff0c;空间使用率更高&＃xff1b;