为什么大多数数据库索引都使用B+树来实现呢?这涉及到数据结构、操作系统、计算机存储层次结构等等复杂的理论知识。

聚集索引和非聚集索引结构参考:

今天我们来探讨一下数据库中一个很重要的概念:索引。

为什么使用B+树?

前两天有位朋友邀请我回答个问题,为什么 MongoDB (索引)使用B-树而 Mysql
使用
B+树?我觉得这个问题非常好,从实际应用的角度来学习数据结构,没有比这更好的方法了。因为像
Mysql 和 MongoDB
这种经久考验的大型软件在设计上都是精益求精的,它们为什么选择这些数据结构?:)

MySQL官方对索引的定义为:索引(Index)是帮助MySQL高效获取数据的数据结构,即索引是一种数据结构。

大家在数学课上一定听说过一个例子,在一堆已经排好序的数字当中找出一个特定的数字的最好办法是一种叫“二分查找”的方式。具体的过程就是先找到这些数字中间的那一个数,然后比较目标数字是大于还是小于这个数;然后根据结果继续在前一半或者后一半数字中继续查找。

本文从实际应用的角度来介绍以及分析B-树和B+树。

我们知道,数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快,因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear
search),这种复杂度为O(n)的算法在数据量很大时显然是糟糕的,好在计算机科学的发展提供了很多更优秀的查找算法,例如二分查找(binary
search)、二叉树查找(binary
tree
search)等。如果稍微分析一下会发现,每种查找算法都只能应用于特定的数据结构之上,例如二分查找要求被检索数据有序,而二叉树查找只能应用于二叉查找树上,但是数据本身的组织结构不可能完全满足各种数据结构(例如,理论上不可能同时将两列都按顺序进行组织),所以,在数据之外,数据库系统还维护着满足特定查找算法的数据结构,这些数据结构以某种方式引用(指向)数据,这样就可以在这些数据结构上实现高级查找算法。这种数据结构,就是索引。

这就类似于数据结构中的二叉树,二叉树就是如下的一种结构,树中的每个节点至多可以有两个子节点,而B+树每个节点则可以有N个子节点。


我们来看一个例子:

图片 1

B-树由来

定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

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

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

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

图片 2

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

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

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

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

图片 3

上图是一棵简化的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)。


图片 4

这里就不具体展开讲解二叉树了,我们只需要知道,平衡的二叉树是内存中查询效率最高的一种数据结构就可以了。

B-树

图片 5

上图是一颗B-树,B-树的每个节点有 d~2d 个
key,2 这个因子指明了树的分裂及合并的规则,这个规则维持了B-树的平衡。

B-树的插入和删除就不具体介绍了,很多资料都描述了这一过程。在普通平衡二叉树中,插入删除后若不满足平衡条件则进行 旋转 操作,而在B-树中,插入删除后不满足条件则进行分裂及合并操作。

简单叙述下分裂及合并操作。

分裂:如果有一个节点有 2d 个 key,增加一个后为 2d+1 个
key,不符合上述规则 B-树的每个节点有 d~2d 个 key,大于
2d,则将该节点进行分裂,分裂为两个 d 个 key 的节点并将中值 key
归还给父节点。 
合并:如果有一个节点有 d 个 key,删除一个后为 d-1 个
key,不符合上述规则 B-树的每个节点有 d~2d 个 key,小于
d,则将该节点进行合并,合并后若满足条件则合并完成,不满足则均分为两个节点。

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);
    }
}

上图展示了一种可能的索引方式。左边是数据表,一共有两列七条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Col2的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

但是目前常用的数据库中,绝大多数的索引都是使用B+树实现的。那么为什么明明是二叉树查询效率最高,数据库中却偏偏要使用B+树而不是二叉树来实现索引呢?

B+树

B+树是B-树的变种,它与B-树的不同之处在于:

  • 在B+树中,key 的副本存储在内部节点,真正的 key 和 data
    存储在叶子节点上 。
  • n 个 key 值的节点指针域为 n 而不是 n+1。

如下图为一颗B+树:

图片 6

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

为了增加 区间访问性,一般会对B+树做一些优化。 
如下图带顺序访问的B+树。

图片 7


虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black
tree)实现的,因为它们的效率相对于B树以及哈希来说特别的低。

发表评论

电子邮件地址不会被公开。 必填项已用*标注