作者 | Amazing10
责编 | 屠敏
头图 | CSDN 下载自视觉中国
本文为「业余码农」投稿
索引的概念基本所有人都会遇到过，就算没有了解过数据库中的索引，在生活中也不可避免的接触到。比方说书籍的目录，字典的查询页，图书馆的科目检索等等。其实这些都是一种索引，并且所起到的作用大同小异。
而对于数据库而言，只不过是将索引的概念抽象出来，让建立索引的过程更为灵活而自由，从而可以在不同的场景下优化数据库的查询效率。
索引在数据库的实际应用场景中十分普遍，数据库的优化也离不开对索引的优化。同时，索引相关的知识也是面试高频的考点之一，是应试者理论结合现实最为直接的体现。
因此，本文将从基础理论出发，介绍 MySQL 按照逻辑角度的索引分类和实现，通过数据结构的实现原理阐述不同结构对建立索引带来的优劣势，同时针对物理存储的方式对索引的组织特点和应用场景进行分析。最后根据不同的应用场景尽可能的探究如何建立起高性能的索引。文章结构如下：
概念
什么是索引？
索引似乎并没有十分明确的定义，更多的是一种定性的描述。简单来讲，索引就是一种将数据库中的记录按照特殊形式存储的数据结构。通过索引，能够显著地提高数据查询的效率，从而提升服务器的性能。
专业一点来说呢，索引是一个排好序的列表，在这个列表中存储着索引的值和包含这个值的数据所在行的物理地址。在数据库十分庞大的时候，索引可以大大加快查询的速度，这是因为使用索引后可以不用扫描全表来定位某行的数据，而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。
说起索引，其实并不是 MySQL 数据库特有的机制，在关系型数据库中都会有类似不同的实现。这里我们也只是讨论 MySQL 数据库中的索引实现。
事实上，说是 MySQL 的索引其实并不准确。因为在 MySQL 中，索引是在存储引擎层而不是服务器层实现的。这意味着我们所讨论的索引准确来说是 InnoDB 引擎或 MyISAM 引擎或其它存储引擎所实现的。
所以索引即便是在 MySQL 中也没有统一的标准，不同存储引擎的所实现的索引工作方式也并不一样。不是所有的存储引擎都支持相同类型的索引，即便是多个引擎支持同一种类型的索引，其底层的实现也可能不同。
为什么需要索引
说了这么多，索引似乎就是给数据库添加了一个「目录页」，能够方便查询数据。但是索引的作用就仅此而已了吗，为什么需要大费周章的建立并优化索引？
说个题外话，我其实查字典从来都不喜欢查目录页，无论是查中文还是英文。因为觉得那样很慢，一个个找索引，效率很低。我习惯用的方式就是直接翻开字典，根据翻开的位置进行前后调整。比方说我想找「酱 JIANG」字，会先随机翻到一页，可能是「F」开头，在「J」前面，就往后翻一点；如果随机翻到「L」，那就往前翻一点。重复直至找到。
这大概就是类似于二分查找的方式，看起来好像是摆脱了索引的束缚，并且也能够获得比较高的查询效率。但是其实转念一想，在计算机的运行处理中，「一个个找索引」这个过程其实非常快，不能跟我们手动比对偏旁部首的效率相提并论。同时，为什么我可以直接翻开字典根据字母进行调整呢，这其实不就是因为我的脑子里存在一个大概的「索引表」，知道每个字母大概对应于字典的哪一个位置。虽然是模糊的，但却是真实存在的。（好不容易强行解释了一波...）
如此一来，可以看出索引的一大好处是如其概念中所提及的，使用索引后可以不用扫描全表来定位某行的数据，而是先通过索引表找到该行数据对应的物理地址然后访问相应的数据。这样的方式自然减少了服务器在响应时所需要对数据库扫描的数据量。
不仅如此，在执行数据库的范围查询时，若不使用索引，那么MySQL会先扫描数据库的所有行数据并从中筛选出目标范围内的行记录，将这些行记录进行排序并生成一张临时表，然后通过临时表返回用户查询的目标行记录。这个过程会涉及到临时表的建立和行记录的排序，当目标行记录较多的时候，会大大影响范围查询的效率。
所以当添加索引时，由于索引本身具有的顺序性，使得在进行范围查询时，所筛选出的行记录已经排好序，从而避免了再次排序和需要建立临时表的问题。
同时，由于索引底层实现的有序性，使得在进行数据查询时，能够避免在磁盘不同扇区的随机寻址。使用索引后能够通过磁盘预读使得在磁盘上对数据的访问大致呈顺序的寻址。这本质上是依据局部性原理所实现的。
局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高(不需要寻道时间，只需很少的旋转时间) ，因此对于具有局部性的程序来说，磁盘预读可以提高I/O效率。
磁盘预读要求每次都会预读的长度一般为页的整数倍。而且数据库系统将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。这里的页是通过页式的内存管理所实现的，概念在这里简单提一嘴。
分页机制就是把内存地址空间分为若干个很小的固定大小的页，每一页的大小由内存决定。这样做是为了从虚拟地址映射到物理地址，提高内存和磁盘的利用率。
所以呢，总结一下。索引的存在具有很大的优势，主要表现为以下三点：
索引大大减少了服务器需要扫描的数据量
索引可以帮助服务器避免排序和临时表
索引可以将随机 I/O 变成顺序 I/O
以上三点能够大大提高数据库查询的效率，优化服务器的性能。因此一般来说，为数据库添加高效的索引对数据库进行优化的重要工作之一。
不过，凡事都有两面性。索引的存在能够带来性能的提升，自然在其它方面也会付出额外的代价。
索引本身以表的形式存储，因此会占用额外的存储空间；
索引表的创建和维护需要时间成本，这个成本随着数据量增大而增大；
构建索引会降低数据的修改操作（删除，添加，修改）的效率，因为在修改数据表的同时还需要修改索引表；
所以对于非常小的表而言，使用索引的代价会大于直接进行全表扫描，这时候就并不一定非得使用索引了。没办法，成年人的世界总是这么的趋利避害。
