- 为什么要使用索引呢？
稍厚的图书都会有自己的目录，能够便于读者快速定位关键信息所在的位置。类似地，索引的使用也是为了加快DBMS对数据的检索速度。
大多数数据查询操作，都是对数据表中的很小一部分数据进行查询。通常，如果待查询的数据量占到了全表的10%以上，我们就可以采用全表扫描的方法进行数据检索。相反，查找一小部分信息的时候，索引的作用就不言而喻了。
本文内容在数据库的课程中有所涉及。由于教材上的相关内容介绍十分简略，因此这里将笔记和其他参考书的详细内容加以解释和整理。
一、B+树索引
B+树：多路平衡树。
1.B+树的结构
B+树的本质就是一个多级索引，不过它跟下图所示的多级索引在结构上稍有差别。
B+树是一种树状结构，我们先看它的结点。
如上图所示，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代表每个节点最多所允许存放的指针数量）：
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）伪码
（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均等分裂，按照类似于③-⑥的操作递归地执行下去，直到算法结束。
这部分算法比较复杂，如果需要对逻辑有更深刻的认识可以看如下伪码：
（2）删除算法
这里不对删除算法的规范过程作详细说明，仅大致描述算法思路。
首先我们用查询算法找到要删除的值所在的叶结点，如果进行删除后该结点不满足‘半满’的条件（所含值太少），则同它的左／右兄弟结点进行合并，同时调整父节点，若父节点在调整后也不满足‘半满’条件，则逐层回退，最坏情况会一直调整到根结点。
半满条件：对于叶结点，存储的值的个数不低于⌈(n-1)/2⌉（n为一个节点中指针的最大数量）；对于中间结点，存储的指针个数不低于⌈n/2⌉；对于根结点，存储的指针个数不低于2。
删除算法的伪码如下：
（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+树索引更适合完成范围查询，即
而Hash索引更适合完成对特定数据的查询，即：
图片和主要内容引自《DATABASE SYSTEM CONCEPTS》(6th Edition)
(Abraham Silberschatz, Henry F. Korth, S. Sudarshan著)