B树，B+树，B树和B*树

B树

       即二叉搜索树&＃xff1a;

       1.所有非叶子结点至多拥有两个儿子&＃xff08;Left和Right&＃xff09;&＃xff1b;

       2.所有结点存储一个关键字&＃xff1b;

       3.非叶子结点的左指针指向小于其关键字的子树&＃xff0c;右指针指向大于其关键字的子树&＃xff1b;

       如&＃xff1a;

       B树的搜索&＃xff0c;从根结点开始&＃xff0c;如果查询的关键字与结点的关键字相等&＃xff0c;那么就命中&＃xff1b;

否则&＃xff0c;如果查询关键字比结点关键字小&＃xff0c;就进入左儿子&＃xff1b;如果比结点关键字大&＃xff0c;就进入

右儿子&＃xff1b;如果左儿子或右儿子的指针为空&＃xff0c;则报告找不到相应的关键字&＃xff1b;

       如果B树的所有非叶子结点的左右子树的结点数目均保持差不多&＃xff08;平衡&＃xff09;&＃xff0c;那么B树

的搜索性能逼近二分查找&＃xff1b;但它比连续内存空间的二分查找的优点是&＃xff0c;改变B树结构

&＃xff08;插入与删除结点&＃xff09;不需要移动大段的内存数据&＃xff0c;甚至通常是常数开销&＃xff1b;

       如&＃xff1a;

   但B树在经过多次插入与删除后&＃xff0c;有可能导致不同的结构&＃xff1a;

   右边也是一个B树&＃xff0c;但它的搜索性能已经是线性的了&＃xff1b;同样的关键字集合有可能导致不同的

树结构索引&＃xff1b;所以&＃xff0c;使用B树还要考虑尽可能让B树保持左图的结构&＃xff0c;和避免右图的结构&＃xff0c;也就

是所谓的“平衡”问题&＃xff1b;      

       实际使用的B树都是在原B树的基础上加上平衡算法&＃xff0c;即“平衡二叉树”&＃xff1b;如何保持B树

结点分布均匀的平衡算法是平衡二叉树的关键&＃xff1b;平衡算法是一种在B树中插入和删除结点的

策略&＃xff1b;

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] &＃xff1b;

       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;

小结

       B树&＃xff1a;二叉树&＃xff0c;每个结点只存储一个关键字&＃xff0c;等于则命中&＃xff0c;小于走左结点&＃xff0c;大于

走右结点&＃xff1b;

       B-树&＃xff1a;多路搜索树&＃xff0c;每个结点存储M/2到M个关键字&＃xff0c;非叶子结点存储指向关键

字范围的子结点&＃xff1b;

       所有关键字在整颗树中出现&＃xff0c;且只出现一次&＃xff0c;非叶子结点可以命中&＃xff1b;

       B&＃43;树&＃xff1a;在B-树基础上&＃xff0c;为叶子结点增加链表指针&＃xff0c;所有关键字都在叶子结点

中出现&＃xff0c;非叶子结点作为叶子结点的索引&＃xff1b;B&＃43;树总是到叶子结点才命中&＃xff1b;

       B*树&＃xff1a;在B&＃43;树基础上&＃xff0c;为非叶子结点也增加链表指针&＃xff0c;将结点的最低利用率

从1/2提高到2/3&＃xff1b;