索引的数据结构

索引本质

MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。

从MYSQL的官方定义我们可以知道，索引是一种数据结构，这种数据结构的目的是为了优化查询。那我们就从查询算法的角度来理解下索引，最基本的查询算法当然是顺序查找，此外还有二分查找，二叉树查找，分块查找，哈希散列法等等。每种查找算法只能应用于特定的数据结构中，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），但是查询情况是多种多样的，比如查询的条件字段不一样，条件类型不一样（等值查询，范围查询，in查询，连表查询）等。所以，除把数据按一定数据结构组织外，针对特定的查询场景，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

看一个例子：

图1

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

虽然这是一个货真价实的索引，但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树（red-black tree）实现的，文件系统及数据库系统普遍采用B-/+Tree作为索引结构，下面我们将将结合计算机组成原理相关知识讨论B-/+Tree作为索引的理论基础。

一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储在磁盘上。下面我们结合主存存取原理和磁盘存取原理来说明为何不用二叉查找树。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度（大O表示法）。所以，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

主存存取原理

目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，抽象出一个十分简单的存取模型来说明RAM的工作原理。

4 x 4的主存模型：

图2

从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址：通过一个行地址和一个列地址可以唯一定位到一个存储单元。

主存的存取过程如下：

当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。一次存取操作的时间大概是100ns。快的代价就是贵。

磁盘存取原理

上面说过，索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

磁盘的整体结构示意图：

图3

一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动（实际是斜切向运动），每个磁头同一时刻也必须是同轴的，即从正上方向下看，所有磁头任何时候都是重叠的（不过目前已经有多磁头独立技术，可不受此限制）。

磁盘结构的示意图：

图4

盘片被划分成一系列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元。为了简单起见，我们下面假设磁盘只有一个盘片和一个磁头。

当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间。

也就是说磁盘IO时间由寻道时间、旋转延迟、传输时间组成。

寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在 5ms 以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘 7200 转，表示每分钟能转 7200 次，也就是说 1 秒钟能转 120 次，旋转延迟就是 1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘 IO 的时间约等于 5+4.17 = 9ms 左右。对于数据库表十万百万乃至千万级数据来说，每次 9 毫秒的时间，这效率简直是个灾难。

局部预读性原理

考虑到磁盘 IO 是非常高昂的操作，计算机操作系统做了一些优化，当一次 IO 时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次 IO 读取的数据我们称之为一页 (page)。具体一页有多大数据跟操作系统有关，若干个扇区为一块，若干块为一页，一页一般为 4k 或 8k，也就是我们读取一页内的数据时候，实际上才发生了一次 IO。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。

而红黑树（特殊的二叉查找树）这种结构，h明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的I/O渐进复杂度也为O(h)，效率明显比B-Tree差很多。

B树索引和哈希索引

前面讲了索引本质上是一种提升查询效率数据结构，又讲了内存和磁盘的存取原理以及局部预读性原理，目的是为了从索引的产生背景和使用场景说明为什么数据库和文件系统索引不用二叉查找树和红黑树而选择B树和B+树。我们现在总结一下，我们需要索引的数据结构每次查找数据时把磁盘 IO 次数控制在一个很小的数量级，最好是常数数量级。下面就介绍两种满足这个要求的数据结构，同时也是这次分享的重点内容。

B树和B+树索引

B 树又叫平衡多路查找树。一棵m阶的B 树 (m叉树)的特性如下：

（1）树中每个结点最多含有m个孩子（m>=2）；（2）除根结点和叶子结点外，其它每个结点至少有[ceil(m / 2)]个孩子（其中ceil(x)是一个取上限的函数）；（3）若根结点不是叶子结点，则至少有2个孩子（特殊情况：没有孩子的根结点，即根结点为叶子结点，整棵树只有一个根节点）；（4）所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点，实际上这些结点不存在，指向这些结点的指针都为null)；（5）每个非终端结点中包含有n个关键字信息： (P1，K1，P2，K2，P3，......，Kn，Pn+1)。其中： a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。 b) Pi为指向子树根的接点，且指针P(i)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。 c) 关键字的个数n必须满足： [ceil(m / 2)-1]<= n <= m-1。

图5

查找29的过程：

假设内存中只有索引的根结点指针

(1) 根据根结点指针找到文件目录的17、35所在的根磁盘块，将其中的信息导入内存。【磁盘IO操作1次】

(2) 此时内存中有两个文件名17，35和三个存储其他磁盘页面地址的数据。根据算法我们发现17<29<35，因此我们找到指针p2。

(3) 根据p2指针，我们定位到关键字26、30所在磁盘块，并将其中的信息导入内存。【磁盘IO操作2次】

(4) 此时内存中有两个文件名关键字26，30和三个存储其他磁盘页面地址的数据。根据算法我们发现26<29<30，因此我们找到指针p2。

(5) 根据p2指针，我们定位到关键字28、29所在磁盘块，并将其中的信息导入内存。【磁盘IO操作3次】

(6) 此时内存中有两个文件名28，29。根据算法我们查找到文件29，并定位了该文件内存的磁盘地址。

下面再说一说B树的插入和删除操作。B树的节点关键字数量大于等于[ceil(m/2)-1],小于等于m-1。所以插入和删除时关键字数大了（超过4个）就分裂，小了（小于2个）就合并。

插入操作

生成从空树开始，逐个插入关键字。但是由于B树节点关键字必须大于等于[ceil(m/2)-1],所以每次插入一个关键字不是在树中添加一个叶子结点，而是首先在最底层的某个非终端节点中添加一个“关键字”，该结点的关键字不超过m-1,则插入完成；否则要产生结点的“分裂”，将一半数量的关键字元素分裂到新的其相邻右结点中，中间关键字元素上移到父结点中。

B树插入操作流程图

例子：按顺序插入3、14、7、1、8、5、11、17、13、6、23、12、20、26、4、16、18、24、25、19字符字母到一棵空的B 树中

删除操作

首先查找B树中需删除的元素，如果该元素在B树中存在，则将该元素在其结点中进行删除

删除关键字的几种情况

（1）、删除的关键字所在的节点没有孩子，也就是说在B树的最底层，这时候直接在节点中删除该关键字，判断节点的关键字是否满足ceil(m / 2)-1<= n <= m-1，满足的话结束操作，不满足的话，判断相邻的兄弟节点是否丰满（关键字数大于ceil(m / 2)-1），丰满的话则向父亲节点借一个关键字，丰满兄弟节点则上移一个关键字到父亲节点，不丰满则和父亲节点、兄弟节点合并成一个节点。

（2）、删除的关键字所在节点有孩子，则上移孩子结点中继承元素到父节点中，判断移动后的孩子节点中关键字是否满足ceil(m / 2)-1<= n <= m-1

B树删除关键字操作流程图

举栗环节：

上述的B树中删除8、20、18、5

B+树

在B_树中关键字分布在整个B_树，并且在上层结点中出现过的关键字不再出现在最底层的结点中。顺序链中所有的关键字不能连接在一起。也就是说范围查询时，需要多次磁盘io,同时还需要额外进行排序操作。

一颗m阶的B+树和m阶的B树的差异在于：

1.有n棵子树的结点中含有n个关键字； (而B树是n棵子树有n-1个关键字)

2.所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)

3.所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)

图6

1) B+-tree的磁盘读写代价更低

B+-tree的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
举个例子，假设磁盘中的一个盘块容纳16bytes，而一个关键字2bytes，一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候，B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

2) B+-tree的查询效率更加稳定

由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

哈希索引

哈希表

很多语言都有Hash Table这种数据结构，有的叫哈希表，有的叫散列表，有的叫字典，有的叫map。大体上讲，这就是一种存储键值对的数据结构，通过hash算法，将给定的key算出一个hash值，将value存到hash值对应的地方。下次查找key的时候，以同样的hash算法算出key的hash值，到相应的地方找到该value。从原理可以看出，这种数据结构的好处是，无论多大的一个数据量（如果内存无限），算法复杂度总是Ο(1)的。所以大多数的编程语言都实现了这种数据结构。

可以看出，从key值到hash值其实就是数学上的映射，一般来说，这个映射的定义域会大于值域。

哈希索引

图7

哈希索引用索引列的值计算该值的hashCode，然后在hashCode相应的位置存执该值所在行数据的物理位置，因为使用散列算法，因此访问速度非常快，但是一个值只能对应一个hashCode，而且是散列的分布方式，因此哈希索引不支持范围查找和排序的功能。

任何事物都是有两面性的，Hash 索引也一样，虽然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。 1).Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。 2).Hash 索引无法被用来避免数据的排序操作。由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算； 3).Hash 索引不能利用部分索引键查询。对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。 4).Hash 索引在任何时候都不能避免表扫描。前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值（哈希碰撞），所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。 5).Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下

Hash 索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引。

现在来分析下B+树索引和哈希索引的区别： 1).如果是等值查询，那么哈希索引明显有绝对优势，因为只需要经过一次算法即可找到相应的键值；当然了，这个前提是，键值都是唯一的。如果键值不是唯一的，就需要先找到该键所在位置，然后再根据链表往后扫描，直到找到相应的数据； 2).从示意图中也能看到，如果是范围查询检索，这时候哈希索引就毫无用武之地了，因为原先是有序的键值，经过哈希算法后，有可能变成不连续的了，就没办法再利用索引完成范围查询检索； 3).同理，哈希索引也没办法利用索引完成排序，以及like ‘xxx%’ 这样的部分模糊查询（这种部分模糊查询，其实本质上也是范围查询）； 4).哈希索引也不支持多列联合索引的最左匹配规则； 5).B+树索引的关键字检索效率比较平均，不像B树那样波动幅度大，在有大量重复键值情况下，哈希索引的效率也是极低的，因为存在所谓的哈希碰撞问题。

结束语

数据库索引的第一期分享就介绍到这里，后面的分享还会介绍下mysql各引擎对索引的具体实现，mysql优化器是如何用索引来优化查询，索引的设计和优化的一些原则