B-树

 

B-树概述

 

B-树，这里的 B 表示 balance（ 平衡的意思），B-树是一种多路自平衡的搜索树（B树是一颗多路平衡查找树）

 

它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。下图是 B-树的简化图。

 

B-树有如下特点：

 

所有键值分布在整颗树中（索引值和具体data都在每个节点里）；

 

任何一个关键字出现且只出现在一个结点中；

 

搜索有可能在非叶子结点结束（最好情况O（1）就能找到数据）；

 

在关键字全集内做一次查找，性能逼近二分查找；

 

B树深入

 

B树由来

 

定义：B-树是一类树，包括B-树、B+树、B*树等，是一棵自平衡的搜索树，它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。

 

B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。

 

定义只需要知道B-树允许每个节点有更多的子节点即可（多叉树）。子节点数量一般在上千，具体数量依赖外部存储器的特性。

 

先来看看为什么会出现B-树这类数据结构。

 

传统用来搜索的平衡二叉树有很多，如 AVL 树，红黑树等。这些树在一般情况下查询性能非常好，但当数据非常大的时候它们就无能为力了。原因当数据量非常大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

 

上图是一颗简单的平衡二叉树，平衡二叉树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

 

空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。

 

我们从“迎合”磁盘的角度来看看B-树的设计。

 

索引的效率依赖与磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。所以新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。

 

上图是一棵简化的B-树，多叉的好处非常明显，有效的降低了B-树的高度，为底数很大的 log n，底数大小与节点的子节点数目有关，一般一棵B-树的高度在 3 层左右。层数低，每个节点区确定的范围更精确，范围缩小的速度越快（比二叉树深层次的搜索肯定快很多）。上面说了一个节点需要进行一次 IO，那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列（a1,a2,a3…an），并将该节点的子节点分割成 n+1 个区间来进行索引（X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an）。

 

点评：B树的每个节点，都是存多个值的，不像二叉树那样，一个节点就一个值，B树把每个节点都给了一点的范围区间，区间更多的情况下，搜索也就更快了，比如：有1-100个数，二叉树一次只能分两个范围，0-50和51-100，而B树，分成4个范围 1-25， 25-50，51-75，76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

 

B-树的查找

 

我们来看看B-树的查找，假设每个节点有 n 个 key值，被分割为 n+1 个区间，注意，每个 key 值紧跟着 data 域，这说明B-树的 key 和 data 是聚合在一起的。一般而言，根节点都在内存中，B-树以每个节点为一次磁盘 IO，比如上图中，若搜索 key 为 25 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 25 小于 key 50，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。

 

查找伪代码：

 

Data* BTreeSearch（Root *node, Key key）

 

{

 

    Data* data;

 

    if（root == NULL）

 

        return NULL;

 

    data = BinarySearch（node）;

 

    if（data->key == key）

 

    {

 

        return data;

 

    }else{

 

        node = ReadDisk（data->next）;

 

        BTreeSearch（node, key）;

 

    }

 

}

 

B+ 树

 

B+树概述

 

B+树是B-树的变体，也是一种多路搜索树， 它与 B- 树的不同之处在于：

 

所有关键字存储在叶子节点出现，内部节点（非叶子节点并不存储真正的 data）

 

为所有叶子结点增加了一个链指针

 

简化 B+树 如下图

 

因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的，为一页。

 

为了增加 区间访问性，一般会对B+树做一些优化。

 

如下图带顺序访问的B+树。