B树第末节学习（高度及性能分析）

B-树的高度及性能分析 

    　B-树上操作的时间通常由存取磁盘的时间和CPU计算时间这两部分构成。B-树上大部分基本操作所需访问盘的次数均取决于树高h。关键字总数相同的情况下B-树的高度越小，磁盘I/O所花的时间越少。

 

    　与高速的CPU计算相比，磁盘I/O要慢得多，所以有时忽略CPU的计算时间，只分析算法所需的磁盘访问次数（磁盘访问次数乘以一次读写盘的平均时间(每次读写的时间略有差别)就是磁盘I/O的总时间）。

 

1、B-树的高度

    　定理9.1 若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高h至多为：log_t((n+1)/2)+1。

 

这里t是每个(除根外)内部结点的最小度数，即t=[m/2]。

         

    　由上述定理可知：B-树的高度为O(logtn)。于是在B-树上查找、插入和删除的读写盘的次数为O(log_tn)，CPU计算时间为O(mlog_tn)。

 

2、性能分析

 

　　①n个结点的平衡的二叉排序的高度H（即lgn）比B-树的高度h约大lgt倍。

     【例】若m=1024，则lgt=lg512=9。此时若B-树高度为4，则平衡的二叉排序树的高度约为36。显然，若m越大，则B-树高度越小。

②若要作为内存中的查找表，B-树却不一定比平衡的二叉排序树好，尤其当m较大时更是如此。

  因为查找等操作的CPU计算时间在B-树上是

        O(mlog_tn)=0(lgn·(m/lgt))

 

而m/lgt>1，所以m较大时O(mlogtn)比平衡的二叉排序树上相应操作的时间O(lgn)大得多。因此，仅在内存中使用的B-树必须取较小的m。（通常取最小值m=3，此时B-树中每个内部结点可以有2或3个孩子，这种3阶的B-树称为2-3树）。

 

B+树       

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

       

1.其定义基本与B-树同，除了非叶子结点的子树指针与关键字个数相同；       

2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

       

 3.为所有叶子结点增加一个链指针；  

  

 4.所有关键字都在叶子结点出现；如：（M=3）。如图：

 

 

 

 B+的搜索与B-树也基本相同，区别是B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分    查找； 

 

B+的特性： 

1.所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2. 不可能在非叶子结点命中；

 

3.  .非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层； 

4.更适合文件索引系统；

 

 B*树       

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；  

如图：

 

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）； 

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

 

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

 

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