浅析三种多路搜索树

本是古典何须时尚 2022-07-15 12:51 125阅读 0赞

## B树家族 ##

磁盘I/O操作的基本单位为块。从磁盘上读取信息时，会把包含信息的整个块读入内存；将信息存储到磁盘上时，也需要将整个块写到磁盘上。当每次从磁盘上请求信息时，都必须先在磁盘上定位该信息。磁头移动到包含所请求信息的磁盘位置上方。然后，将磁盘旋转，将磁头下方的整个块传送到内存。也就是说，数据访问时间由几个时间段组成：

*   *  访问时间=寻道时间+转动延迟+数据传送时间

--------------------

与在内存中传送信息相比，这个过程是相当缓慢的，其中寻道时间由于倚赖与磁头在定位到正确的磁道过程中的磁头的机械运动是非常消耗时间的。转动延迟指的是磁头转动到正确的磁盘块所需的时间。

![这里写图片描述][20161117185839428]

如果程序需要不断的使用辅助存储器上的信息，在设计该程序时就应该考虑这种存储方式的特性。如果用平衡树（AVL，RB）来作为这种存储方式的数据结构，那么平衡树可能分布在磁盘的不同块上，所以平均需要访问两个磁盘块。如果程序经常使用该树，这种访问时间就会显著增加。此外在该树中的插入和删除键值也需要访问多个个磁盘块。可以看出，平衡树在内存中是一种非常高效的工具，而在磁盘上就会变得非常的低效。在涉及辅助存储器时，二叉查找树在其他方面的性能优点会变得微不足道，因为这种方法需要不断的访问辅助存储器，严重降低了性能。  
在磁盘上一次存取大量数据比在磁盘上的不同部分存取少量数据更好，比如给磁盘传送10KB数据时：

*  一个10KB片段上：
 *  访问时间=40ms(寻道)+10ms(转动延迟)+10ms(数据传送)=60ms
 *  两个5KB片段上：
 *  访问时间=2\*（40 + 10 +5）=110ms
    
    访问时间几乎是在一个片段上的两倍，因为每次磁盘访问都是很浪费时间的。如果可能，数据应该尽量使访问磁盘的次数减少。

## B树 ##

B树主要操作辅助存储器，并尽可能减小由这类存储器带来的影响。它的一个重要的特点是每个节点的大小可以与磁盘块的大小相等。节点中键值的数量可以根据可以根据键值的大小，数据的组织方式和磁盘块的大小而定。

![这里写图片描述][20161117104406740]

一个M阶B树是具有以下性质的多叉查找树：

*  1 . 根节点至少有两个孩子
 *  2 . 每个非根节点有\[M/2 , M\]个孩子
 *  3 . 每个非根节点有\[ M-1/2 , M-1 \]个关键字，并且以升序排列
 *  4 . key \[i\]和key \[i+ 1 \]之间的孩子节点的值介于key \[i\]、key \[i+ 1 \]之间
 *  5 . 所有的叶子节点都在同一层

### B树键值的插入 ###

![这里写图片描述][20161117110632113]

![这里写图片描述][20161117110658256]

## B+树 ##

B+树其实是B树的变体，它的基本定义与B树相同，除了以下部分：

1.  非叶子节点指针和节点中关键字的个数相等。
2.  非叶子节点的指针p\[i\]指向关键字在\_keys\[i\]和\_keys\[i+1\]之间的子树（前开后闭区间）。
3.  为所非叶子节点增加一个链指针，方便遍历。
    
    ![这里写图片描述][20161117191408683]

## B+树键值的插入 ##

![这里写图片描述][20161117200354231]

## B\*树 ##

B\*树也是B树的一个变种。在B\*树中除了根节点外，其他节点都必须至少2/3满，而不能像树一样半满，并且B\*树相比于B树在非叶子节点和叶子节点上都增加了指向兄弟节点的指针。  
![这里写图片描述][20161117201704562]

## B\*树的插入 ##

在B\*树中，为了延迟分解，当节点溢出时，会尝试在节点及其同级节点之间重新分配键值，如果其同级节点也是满的，就要分解节点创建一个新节点，将原节点及其同级节点以及父节点的键值重新分配到三个节点，用于划分三个节点的两个键值放入父节点，从而保证了2/3的填充率。

[20161117185839428]: /images/20220715/dbf25a1eff984bb1a54178ca39ca313c.png
[20161117104406740]: /images/20220715/120d889c1a83468196f74ee70d77f306.png
[20161117110632113]: /images/20220715/1adb0f62ac8a43fa951b796c7cb3783a.png
[20161117110658256]: /images/20220715/120dd64043c342b49060bbe93e0eed1c.png
[20161117191408683]: /images/20220715/1428d449a8af403ea58746382aa00fa3.png
[20161117200354231]: /images/20220715/fb7f1828abdc4eb6a7fe80b6f7acde0e.png
[20161117201704562]: /images/20220715/9b5c6a9316ca412a8f34ffd3dc93af5c.png