B+树索引和Hash索引

  • 为什么要使用索引呢?

稍厚的图书都会有自己的目录,能够便于读者快速定位关键信息所在的位置。类似地,索引的使用也是为了加快DBMS对数据的检索速度。

大多数数据查询操作,都是对数据表中的很小一部分数据进行查询。通常,如果待查询的数据量占到了全表的10%以上,我们就可以采用全表扫描的方法进行数据检索。相反,查找一小部分信息的时候,索引的作用就不言而喻了。

本文内容在数据库的课程中有所涉及。由于教材上的相关内容介绍十分简略,因此这里将笔记和其他参考书的详细内容加以解释和整理。

一、B+树索引

B+树:多路平衡树。

1.B+树的结构

B+树的本质就是一个多级索引,不过它跟下图所示的多级索引在结构上稍有差别

img

B+树是一种树状结构,我们先看它的结点。

img

如上图所示,B+树的一个结点通常由n个指针(Pointer:P1,P2…Pn)和n-1个查询关键字(Search Key:K1,K2…Kn,以下简称SK)构成。其中,n-1个关键字是顺序存放的,即:若i<j,则Ki<Kj(这里我们先假设数据之间各不相等)。结点可分为:叶结点、中间结点、根结点。

(1)叶结点

在叶结点上,SK就变成了对应数据表中存有的值。因此,一个叶结点最多可以存放n-1个值。指针Pi(i!=n)指向数据表,且所指的值和Ki相等。指针Pn指向下一个叶结点。

注意:一个叶结点至少存放⌈(n-1)/2⌉个值。即如果n=4,则至少存放2个值。

(2)中间结点

中间结点的结构跟叶结点一样,不过它们的指针Pi指向结点而不是数据表。对一个包含有m个指针(1<m<=n)的结点而言:P1指向SK小于K1的结点;当1<i<m时,Pi指向SK大于等于Ki-1,且小于Ki的结点;Pm指向SK大于Km的结点。

注意:一个中间结点至少要存放⌈n/2⌉个指针。

(3)根结点

与上述两者不同的是,一个根结点最少需存放两个指针(除非这棵树只有一个结点)。

以上内容介绍了B+树是一种‘多路’树。那么所谓的‘平衡’就更不难理解了:‘平衡’即代表从根结点出发到任意一个叶结点,所经过的高度是相等的。

下图就是一颗B+树的典型样式(n=4,n代表每个节点最多所允许存放的指针数量):

img

2.查询操作

下面我们给出B+树的查询算法(find)及其伪代码(假设要查询的值为‘V’,且任意两个SK不相等):

(1)算法

①将根结点赋值给变量C;

②判断C是否为叶结点。若是,则跳转到第④步;若不是则继续下一步;

③找到C中比大于等于V的最小SK(记作C.Ki)。如果没有合适的Ki,则令C为该结点中最后一个非空指针(记作C.Pm);若C.Ki=V,则令C=C.P(i+1);否则,令C=C.Pi。返回第②步;

④查询当前结点C,若存在Ki=V,则返回(C,i),否则返回空值。算法结束。

(2)伪码

img

(3)思考

如果在一颗B+树中存在两个或以上的相同SK,以上算法该如何调整呢?

下面我们介绍findFirst算法,顾名思义,它返回的是被查询值‘V’在叶子中第一次出现的位置。

既然可以有两个或以上的SK相等,就会存在有部分SK(假设为Ki)的左侧指针Pi所含的值与Ki相等,即:此时若i<j,则Ki<=Kj。那么算法的第三步“若C.Ki=V,则令C=C.P(i+1)”,就应该改为“若C.Ki=V,则令C=C.Pi”。

这样的修改会存在一个问题:找到的叶子结点没有我们想要的V,但是V在表中可能存在。这时就需要向右查找兄弟结点,直至找到V或返回空值。

3.更新操作

因为对原始数据的更新可以通过删除和插入两个步骤完成,因此我们重点介绍后两种操作。

不同于查询操作,插入和删除操作可能破坏原有的平衡性。比如在一个全满的叶结点上插入新的数据,或者在一个半满的叶结点上删除原有数据,都会使得我们对B+树创造的约束被破坏,为了对这些破坏进行修复,有了针对这两种操作的算法。

(1)插入算法

插入的原则是,如果结点中还有空位则直接插入,如果已满则将所在结点均等分裂,并取中间值传给父节点并插入,若父节点也满则再分裂,直至找到空位。若找到根结点都无空位,则新建根结点。假设我们要插入的值为K,对应的寻值指针为P,那么插入算法如下:

①如果树为空,那么创造一个新的结点作为根结点,算法结束;否则执行下一步;

②找到K应该被插入的叶结点L。如果L未满,则插入K和P,算法结束;否则执行下一步;

③将L的P1至K(n-1)放入临时存储块T中,并将K、P放置于T内的合适位置(按序放置);

④创建新的结点L’,将L’的Pn指针置为L.Pn,再将L的指针Pn指向L’,并擦去L中的其他内容;

⑤将T内的P1至K⌈n/2⌉放入L,将其余内容放入L’(均等分裂);

⑥设K’为L’中的最小SK,进而向父节点插入L,K,L’;

⑦如果L为根结点,则新建一个根结点,令其K1=K,P1和P2分别为L和L’,算法结束;否则执行下一步;

⑧设P为L的父节点。如果P未满,则直接将K放入P,K右侧的指针指向L’,算法结束;否则执行下一步;

⑨再将P均等分裂,按照类似于③-⑥的操作递归地执行下去,直到算法结束。

这部分算法比较复杂,如果需要对逻辑有更深刻的认识可以看如下伪码:

img

#### (2)删除算法

这里不对删除算法的规范过程作详细说明,仅大致描述算法思路。

首先我们用查询算法找到要删除的值所在的叶结点,如果进行删除后该结点不满足‘半满’的条件(所含值太少),则同它的左/右兄弟结点进行合并,同时调整父节点,若父节点在调整后也不满足‘半满’条件,则逐层回退,最坏情况会一直调整到根结点。

半满条件:对于叶结点,存储的值的个数不低于⌈(n-1)/2⌉(n为一个节点中指针的最大数量);对于中间结点,存储的指针个数不低于⌈n/2⌉;对于根结点,存储的指针个数不低于2。

删除算法的伪码如下:

img

#### (3)思考

更新操作的复杂度如何?

设一棵B+树中存储的值的数量为N,一个结点最多能容纳的指针数量为n,那么一次更新操作的平均复杂度为log⌈n/2⌉(N)。


## 二、Hash索引

B+树等类似的索引有一个明显的缺陷:无论需要查找什么数据,即便在根结点就有了这个数据的查询关键字,我们都要一直找到叶结点才能定位到数据的物理地址,这就造成了时间上的浪费。

Hash(哈希)索引很好地解决了这个问题,hash一词的直接解释是mess up,即打乱、切碎的意思。下面给出它的大致描述:

设K是我们的查询关键字(Search Key),B是其所存放的桶(Bucket,一个桶内可以存放若干个关键字)的编号,Hash函数就是一个将关键字映射到桶号的函数,记作h,即:B=h(K)。

下面详细介绍hash索引的相关内容。

### 1.Hash函数

经过上文的定义,我们不难想象hash函数执行后的一种最坏情况:所有的K全部落入同一个桶中。为了避免这种情况发生,需要对hash函数作出如下约束:

#### (1)均等:映射至每个桶中的K数量大致相等。

#### (2)随机:每个K被分到任意一个B中的概率大致相等。

这两个条件看似有重合之处,实则不然。(1)是后验条件,(2)是先验条件。

例如我们给出一个hash函数h(K)=K % 31 (%为取模运算),从先验条件判断,这个函数对任意自然数而言,计算结果是随机的,因此满足条件(2)。但是,如果K全部集中在某个小区间段(例如在校大学生的年龄,通常在18-22),那么执行了该函数过后,各个桶中K的数量相差极大,因此不满足条件(1)。

因此,任何一个hash函数都需要仔细设计,并在实际应用中反复验证,才能真正体现出hash索引的优点。

### 2.桶溢出及其解决策略

在向桶中放数据的时候,如果桶内已经没有空间容纳这个数据,那么我们称之为溢出。下面两种情况会导致桶内溢出:

(1)桶的数量不足:假设我们有10个数据和5个桶,每个桶内最多放两个数据且刚好已经放下了两个数据,当我们再向任何桶内放数据的时候就出现了溢出。这种情况下每个桶都是满的。

(2)分布偏斜(Skew):某些桶未满而另一些桶已满的时候,如果再向已满的桶内放数据,就会出现溢出。这种情况的发生可能是数据本身重合过多,或者hash函数未能做到均等分布。

解决方案主要有以下几种(某些方案可以共同采用):

(1)适当增加桶的数量:假设我们有Nr个待放置数据,每个桶内最多放置Fr个数据。那么我们可以将桶的数量设置为1.2*Nr/Fr,留出20%的多余空间以防溢出。

(2)衍生桶(overflow buckets):若在一个桶装满后还有待放入该桶的数据,则再建立一个等大的新桶,并将其串接在满桶之后,作为后续数据的存放处,若再满则再建立新桶,如此反复。

(3)探测函数:若在一个桶装满后还有待放入该桶的数据,则利用探测函数查找其他桶是否有空间存放。常见的探测函数有线性探测、平方探测等。线性探测即是按照编号查找后续的桶。

(4)动态hash(本文略去)

## 三、B+树索引与Hash索引的对比

### 1.本质

如果我们把B+树的构造过程等同于一个函数,那么可以认为B+树索引和Hash索引在本质上是相似的。它们均是将一组数据映射到存储空间的索引方法。

### 2.优缺点

B+树索引的最大优点是它保留了序

Hash索引的优点是它的访问速度快

对应到应用过程中,B+树索引更适合完成范围查询,即

img

而Hash索引更适合完成对特定数据的查询,即:

img


图片和主要内容引自《DATABASE SYSTEM CONCEPTS》(6th Edition)

(Abraham Silberschatz, Henry F. Korth, S. Sudarshan著)

假装有打赏功能