索引的 “哲学思想”
我们为什么需要索引？
显而易见，使用索引可以加快我们检索数据的速度，生活中书籍的目录、图书馆里的各种书架编号、号码簿上的检索页等，都少不了索引的身影。
回到计算机的世界，任何一种数据结构都不是凭空产生的，一定会有它的诞生背景和解决的问题。我们先举个最简单的例子，下图是一个有序递增的数组，里面包含十个元素，没有重复。
如果我想要查找元素 24 ，该怎么做呢？第一想到的自然是遍历数组，如果数组长度为 N 那么算法的时间复杂度是 O(N)。有没有更快的办法呢？随即我们想到，鉴于数组已经有序了，我们还可以使用二分查找，每次都折半，时间复杂度降为 O(logN)。甚至于，我们还可以建立树形的数据结构来搜索，最常见的就是二叉搜索树（BST）或者 AVL 树。
到目前为止，好像一切都很容易，下面我们为之前的数据再增加一个关联的数据属性（或者多个数据属性）。
看看是不是有点眼熟，好像这种结构在哪里见过？想象一下，将这个数据集横向拓展，发现这其实就是数据库中一张表，它有两列，一列主键一列数字，其中第一行的数据就对应数据库表的主键（Primary Key），每个 PK 关联与之对应的一整行数据记录。
回想下我们刚刚做的努力，我们用 PK 的值来构建了某种查询数据结构（例如 BST、AVL），然后通过它快速找到了 PK 的值，如果树的节点保存一整行的记录，那么当我们的查询命中某个 PK 之后，就能在该节点顺势读取到这一行其他的数据了。
例如我们查询主键为 27 的节点，便可以顺势读到第二行的 7 这个数值。
上述的例子是很显而易见的，即使你没接触过索引，要设计一种加速查询的方法，也可能会想到这种方案，但是仅仅做到这些远远不够，数据库系统受庞大的数据量、查询条件的复杂性（等值、范围、模糊）的影响，其索引的实现复杂许多，但是起源的哲学思想都是一样的。
索引是越多越好吗？
虽说索引可以加速查询，但索引未必是越多越好，因为：
- 数据的增删都会涉及到随索引的修改，索引越多维护成本越高；
- 索引越多也意味着存储空间需要越大；
- 有时候未必需要索引，如果一列数据重复项非常多，建索引反而没有必要，例如第一节中我们列举了一个内存中、极少量数据如何采用不同的方法做高效查询的例子，但其实这种容量的数组在内存中直接遍历才是王道，不需要关心性能问题。
数据库对索引结构的要求
在真正的数据库设计中，例如 MySQL 这样的关系型数据库，它对索引结构的设计也是有要求的：
- 查询速度要尽可能快
- 索引显然也需要存储在磁盘上进行持久化，如何尽可能减少索引查询过程中的磁盘
IO次数 - 不仅仅是等值查询，也要能做范围查询（
BETWEEN、IN、<、>）、模糊查询（LIKE）、并集查询（OR）
我们来仔细思考下上面的三个要求，第一个要求显然排除了线性数据结构，只能采用树形结构，相比于 BST 在最差情况下会退化至 O(N)，AVL 树因为加入了自平衡算法因此读写操作均能很好地保持 O(logN) 的时间复杂度。
我们决定从平衡搜索树中进行选择，那为什么不选择平衡二叉搜索树呢，这得看第二项要求。索引在数据量大时是无法全部读进内存的，通常情况下索引 : 数据量的比例能达到 1 : 5，如果一张表上多个列存在索引、联合索引等，该比例还会继续上升。磁盘上每存储 1GB 的数据就要耗费 200MB 用来存储索引，一旦数据量大内存是存放不下全部的索引的，况且索引不持久化难道每次启动时都新建么？因此索引必须在磁盘上存储，读入索引会产生磁盘 IO。
众所周知，相比内存（DRAM），磁盘读取会慢上十万倍，因此如何减少索引查找过程中的磁盘 IO 次数至关重要，这个条件限制了二叉搜索树成为索引数据结构的机会，反而是高度可控的多路搜索树更适合。因此，文件系统及数据库系统普遍采用 B+ 树 作为索引结构，至于为什么最终选择 B+ 树，它的优点是什么，弄清楚这些得先从磁盘 I/O 的知识入手，然后再结合这些原理分析 B+ 树作为索引结构的优势在哪里。
磁盘 I/O 与磁盘预读
本节内容选自《深入理解计算机系统》第六章 存储器层次结构
磁盘 I/O
先简单介绍一下磁盘 I/O 和预读，磁盘以扇区大小的块来读写数据，对扇区的访问时间主要有三个组成部分：寻道时间、旋转时间和传送时间。
寻道时间
为了读取某个扇区的内容，传动臂需要首先将读写头定位到包含目标扇区的磁道上，移动传动臂所需要的时间称为寻道时间。寻道时间依赖于读写头原本的位置和传动臂在磁盘上的移动速度，主流磁盘一般在 3 ~ 9ms，最大寻道时间在 20ms。
旋转时间
一旦读写头定位到了期望的磁道，驱动器等待目标扇区的第一个位旋转到读写头下，这个步骤的性能依赖于读写头到达目标扇区的位置和磁盘的选择速度。
传送时间
当目标扇区的第一位位于读写头下，驱动器就可以开始读或者写该扇区的内容了。一个扇区的传送速度依赖于旋转速度和每条磁道的扇区数目。相对于前两个时间，读写数据过程中，传送时间可以忽略不计。
逻辑磁盘块
现代磁盘构造复杂，有多个盘面，盘面又有不同的记录区，为了屏蔽复杂性，现代磁盘将它们组织成一种简单的视图，一个 B 个扇区大小的逻辑块序列，编号 0，1 …… B-1。磁盘中有一个名为磁盘控制器的固件设备，维护者逻辑块号和实际物理磁盘扇区之间的映射关系。
当操作系统想要执行一个 I/O 操作时，例如读取一个磁盘扇区的数据到主存，它就会发送一个命令到磁盘控制器，让它读取某个逻辑块号，控制器上一个固件会将逻辑块号翻译为由盘面、磁道、扇区三个元素组成的三元组，这个三元组唯一标识了一个物理扇区，然后驱动器将读写头移动到指定位置，将数据读到主存。
磁盘预读
因为主存和磁盘访问效率的巨大差异，磁盘 I/O 变成了一个很重量级的操作，因此需要尽可能减少磁盘 I/O 的次数，为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是局部性原理，即当计算机访问一个地址的数据的时候，通常与其相邻的数据也会很快被访问到。
预读的长度一般为页（page）的整倍数，页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为 4K），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
想要详细了解这部分内容，推荐阅读《深入理解计算机系统》第九章 虚拟存储器
B+ 树的优势
上文我们介绍了磁盘读取的一些知识，结合我们之前说的 —— 索引结构的优劣与磁盘 I/O 次数大小紧密相关。因此合适的索引结构必定能最大限度发挥磁盘的性能，那 B+ 树又是如何做到的呢？
从 B+ 树的结构中可知，如果树高是 h 的话，访问一个叶子节点需要经过 h 次查询操作，也即访问 h 个节点。考虑索引实际上存储在磁盘上，载入索引节点的过程需要经历磁盘 I/O，B+ 树由于出色的高度控制，导致 h 的值不会太大，一般来说百万数量级可以控制在 2 ~ 4 左右，意为访问节点的数量主需要 2 ~ 4 个。
数据库系统的设计者又巧妙利用了磁盘预读原理，将一个节点的大小设置成一个页，这样每个节点只需要一次磁盘 I/O 就可以载入主存。这样的话，B+ 树访问一个叶子节点需要 h-1 次磁盘 I/O 就可以，因为其根节点是常驻内存的，极大减少了磁盘 I/O 次数，提高了索引结构的效率
MySQL 中的索引
索引的类型有很多种，可以为不同的场景提供更好的性能。MySQL 中索引是在存储引擎层面而不是服务器层面实现的，所以没有统一的标准，不同存储引擎的索引工作方式也不一样。我们先看看 MySQL 中支持的索引类型。
B-Tree 索引
虽说叫 B-Tree 索引，甚至显示时也是显示成 BTREE，但其实内部实现多使用的是其变种 B+ 树索引，大多数 MySQL 存储引擎都支持这种索引，包括 InnoDB。
因此，B+ 树索引实际上就是我们所说的传统意义上的索引，也是目前关系型数据库中最为常用的、最有效的索引类型。B+ 树在关系型数据库的索引设计中如此流行主要得益于它的高扇出性，B+ 树索引的高度一般维持在 2 ~ 4 层，也就是说查询某一键值的行记录最多只需要 2 ~ 4 次 IO，极大减少了磁盘操作的次数。
哈希索引
基于哈希表实现，只有精确匹配所有列的查询才有效。实现方法为，对于每一行数据，存储引擎都会对所有的索引列计算出一个哈希码，哈希码是一个较小的值，哈希索引将所有行算出的哈希码存储在索引中，并为每一个哈希码维护指向具体某一行的指针。
MySQL 中只有 Memory 引擎显式支持哈希索引。InnoDB 支持的哈希索引是自适应的，用户无法进行配置，InnoDB 引擎会根据表的使用情况自动为表生成哈希索引。使用哈希索引的好处在于时间复杂度为 O(1)，因此哈希索引的查询效率要远高于 BTree 索引。但是其限制在于：
- 只有精确匹配索引所有列的查询才有效,因为哈希索引是利用索引的所有列的字段值来计算哈希值的。
- 只支持等值比较查询，不能用于范围查询。
- 哈希索引的只包含索引字段的哈希值和指向数据的指针，所以不能使用索引中的值来避免读取行。
- 哈希索引的数据并不是顺序存储的，无法用于排序。
空间数据索引
MyISAM 存储引擎支持空间索引，可以用作地理数据存储。平日使用场景不多此处不再详述。
全文索引
全文索引是一种特殊的索引类型，它查找的是文本中的关键词，而不是直接比较索引中的值。它更类似于搜索引擎做的事情，而不是简单的 WHERE 条件匹配。实现方法是通过建立倒排索引，快速匹配文档，这种实现方式也在 Apache Lucene 这种全文检索库中出现。
MyISAM 中的索引详解
MyISAM 存储引擎的索引文件和数据文件是分开的，MyISAM 引擎按照数据插入顺序，将数据文件存储在磁盘上，例如下图中 99 条记录从上到下依次存储。MyISAM 引擎使用 B+ 树作为索引结构，叶节点存放的是数据记录的行指针，图中为了方便阅读以行号代替。
在 MyISAM 引擎中，对主键列建立的主索引和对其他列建立的辅助索引在结构上没有区别，主键索引就是一个名为 Primary
的唯一非空索引。
总结一下，MyISAM 引擎中索引查询的步骤为，先按照 B+ 树查询到叶子节点，如果指定的键值存在，则取出其对应的行指针的值，然后通过行指针，读取相应数据行的记录。
InnoDB 中的索引详解
聚簇索引
同 MyISAM 引擎不同，InnoDB 的数据文件本身就是索引文件，表数据文件本身就是按 B+ 树组织的一个索引结构，其叶子节点的键值就是表的主键，这种数据存储方式也被称为聚簇索引。由此可见，聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。
聚簇索引的叶子节点都包含主键值、事务 ID、用于事务 MVCC 的回滚指针以及所有的剩余列。
辅助索引
辅助索引也叫非聚簇索引，二级索引等。同 MyISAM 引擎的辅助索引实现不同，InnoDB 的辅助索引，其叶子节点存储的不是行指针而是主键值，得到主键值再要查询具体行数据的话，要去聚簇索引中再查找一次，也叫回表。这样的策略优势是减少了当出现行移动或者数据页分裂时二级索引的维护工作。
参考资料
- 《高性能 MySQL》Baron Scbwartz, Peter Zaitsev, Vadim Tkacbenko 著，宁海元，周振兴，彭立勋，翟卫祥等译，电子工业出版社，2010
- 《MySQL技术内幕 InnoDB存储引擎》姜承尧著，机械工业出版社，2011
- MySQL索引背后的数据结构及算法原理
- mysql索引需要了解的几个注意
- MySQL索引原理及慢查询优化
写在最后
这是一个不定时更新的、披着程序员外衣的文青小号，欢迎关注。
