索引这个概念大家基本都会遇到。即使你不知道数据库中的索引，生活中也难免会接触到它。比如图书的目录、词典的查询页、图书馆的主题检索等等。其实这些都是各种指标，作用也差不多。而对于数据库，只是抽象了索引的概念，让索引的过程更加灵活自由，从而在不同的场景下优化数据库的查询效率。索引在数据库的实际应用场景中非常常见，数据库的优化也离不开索引的优化。同时，指标相关知识也是面试的高频考点之一，是应聘者理论与实际相结合的最直接体现。因此，本文将从基础理论出发，从逻辑的角度介绍MySQL的索引分类和实现，并通过数据结构的实现原理来说明不同结构建立索引的优缺点。分析应用场景。最后，根据不同的应用场景，尝试探索如何构建高性能索引。文章结构如下：1概念什么是索引索引似乎没有一个很明确的定义，更多的是一种定性的描述。简单地说，索引就是一种数据结构，它以一种特殊的形式将记录存储在数据库中。通过索引，可以显着提高数据查询的效率，从而提高服务器的性能。从技术上讲，索引是一个排序列表，其中存储了索引的值和包含该值的数据的行的物理地址。当数据库很大时，索引可以大大加快查询速度。这是因为使用索引后，不需要扫描整张表来定位某一行的数据，而是先通过索引表找到该行数据对应的物理地址，然后访问对应的数据。说到索引，它并不是MySQL数据库独有的机制。关系数据库中有相似和不同的实现。这里我们也只讨论MySQL数据库中的索引实现。其实说它是MySQL索引是不准确的。因为在MySQL中，索引是在存储引擎层实现的，而不是服务器层。这意味着我们所说的索引正是InnoDB引擎或MyISAM引擎或其他存储引擎实现的。因此即使在MySQL中也没有统一的索引标准，不同的存储引擎实现的索引方式也不尽相同。并非所有存储引擎都支持相同类型的索引。即使多个引擎支持相同类型的索引，它们的底层实现也可能不同。为什么需要索引说了这么多，索引好像给数据库增加了一个“目录页”，可以方便数据查询。但指数的作用仅此而已吗？为什么需要花那么多时间建立和优化索引？说句题外话，其实我查字典的时候从来不喜欢查目录页，不管是中文还是英文。因为我觉得那样很慢，一个一个找索引效率很低。我习惯的方式是直接打开字典，根据打开的位置前后调整。比如我要找“酱江”这个词，我会先翻到一个随机的页面，可能是“F”开头的，在“J”之前再往回翻一点；如果我随机转向“L”，则向前翻转一点。重复直到找到。这大概类似于二分查找的方式，似乎摆脱了索引的束缚，也可以获得比较高的查询效率。但其实仔细想想，在计算机的运算处理中，“一个一个地找索引”的过程其实是非常快的，和我们人工比较部首的效率是没法比的。同时，为什么我可以直接打开字典，根据字母进行调整呢？不是因为脑子里有个大概的“索引表”，知道每个字母在字典里对应的位置。虽然模糊，却是真实的。（终于强行解释了一波。。。）这样就可以看出索引的一大好处就是在它的概念中提到的。使用索引后，不需要扫描整张表就可以定位到一行数据，而是先通过索引表找到该行数据对应的物理地址，然后访问对应的数据。这种方式自然减少了服务器在响应时需要扫描数据库的数据量。不仅如此，如果在对数据库进行范围查询时不使用索引，MySQL会先扫描数据库中的所有行数据并过滤掉目标范围内的行记录，对这些行记录进行排序并生成一个临时表table，然后通过临时表返回用户查询到的目标行记录。这个过程会涉及临时表的创建和行记录的排序。当目标行记录较多时，范围查询的效率会受到很大影响。因此，在添加索引时，由于索引本身的顺序性，过滤后的行记录在进行范围查询时就已经排序好了，从而避免了重新排序的问题和需要创建临时表的问题。同时，由于索引底层的有序执行，可以避免数据查询时在磁盘不同扇区的随机寻址。使用索引后，可以通过磁盘预读大致顺序地访问磁盘上的数据。这本质上是根据局部性原则实现的。局部性原则：当一条数据被使用时，附近的数据通常会立即被使用。程序运行过程中需要的数据通常比较集中。由于磁盘顺序读取的效率高（不需要寻道时间，旋转时间非常少），磁盘预读可以提高具有局部性的程序的I/O效率。磁盘预读要求每次预读的长度一般是页的整数倍。并且数据库系统将一个节点的大小设置为一个页面，这样每个节点只需要一次I/O就可以完全加载。这里的pages是通过page-style的内存管理实现的，这里简单提一下概念。分页机制是将内存地址空间分成几个固定大小的小页，每个页的大小由内存决定。这样做是为了通过从虚拟地址映射到物理地址来提高内存和磁盘利用率。所以，总结一下。索引的存在有很大的优势，主要有以下三点：索引大大减少了服务器需要扫描的数据量索引可以帮助服务器避免排序临时表索引可以把随机I/O变成顺序I/O以上三点可以大大提高数据库查询效率，优化服务器性能。因此，一般来说，为数据库添加一个高效的索引是优化数据库的重要工作之一。然而，任何事情都有两个方面。索引的存在可以带来性能的提升，自然会有其他方面的额外成本。索引本身是以表的形式存储的，因此会占用额外的存储空间；索引表的创建和维护需要时间成本，而且这个成本随着数据量的增加而增加；建立索引会降低数据修改操作（删除、添加、修改）的效率，因为修改数据表的同时需要修改索引表；所以对于非常小的表，使用索引的代价会比直接扫描全表更大，这时候就没有必要使用索引了。没办法，大人的世界总是那么好，避免坏的。2逻辑分类索引如果从逻辑的角度来划分，可以分为单列索引、全文索引、复合索引和空间索引。单列索引可以分为主键索引、唯一索引和普通索引。这里的逻辑可以从SQL语句的角度来理解，也可以从数据库关系表的角度来理解。下面简单介绍一下这些索引的作用和用法，以及修改表时如何添加索引。主键索引就是主索引。索引基于主键建立，不允许重复，不允许空值；主键：数据库表中一列或列组合（字段）的值，可以唯一标识表中的每一行。加速查询+唯一列值（不允许为null）+只有一个ALTERTABLE'table_name'ADDPRIMARYKEYpk_index('col');用于索引的列的值必须是唯一的，允许空值。唯一索引不允许表中的任何两行具有相同的索引值。例如，如果在员工表中对员工的姓氏创建唯一索引，则意味着任何两个员工的姓氏都不能相同。加速查询+唯一列值（可以为空）ALTERTABLE'table_name'ADDUNIQUEindex_name('col');普通索引用表中的普通列建立的索引，没有任何限制。只加速查询ALTERTABLE'table_name'ADDINDEXindex_name('col');全文索引是用大文本对象的列建立的索引ALTERTABLE'table_name'ADDFULLTEXTINDEXft_index('col');复合索引是用多个列组合建立的索引，即多个列中的值不允许空值。多列值组成一个索引，专门用于组合查找，其效率大于索引合并。ALTERTABLE'table_name'ADDINDEXindex_name('col1','col2','col3');在对多个列的组合进行索引时，会遵循“最左前缀”原则。最左前缀原则：顾名思义，就是最左在前。在上面的例子中，我们创建了一个(col1,col2,col3)多列索引，相当于创建了一个(col1)单列索引，(col1,col2)复合索引和(col1,col2,col3)复合指数。所以我们在创建多列索引的时候，根据业务场景，应该把where子句中使用频率最高的列放在最左边。空间索引是建立在空间数据类型的字段上的索引，底层可以通过R树来实现。只是用得少，可以理解。3实现原理我们知道索引本身底层是通过数据结构来实现的。常见的索引类型按照其底层结构可以分为hash索引、BTree索引、B+Tree索引等，这里主要介绍这三种索引背后的实现机制。哈希索引顾名思义，哈希索引是通过哈希表来实现的。哈希表的特点在之前的文章《九大数据结构》中已经详细介绍过了。通过哈希表的键值之间的对应关系，可以在查询时准确匹配索引的所有列。哈希索引将所有根据索引列计算得到的哈希码存储在索引中，并在哈希表中保存指向每个数据行的指针。上图是通过哈希索引查询行数据的示意图。可以发现哈希索引也存在哈希冲突，通过链地址的方式解决冲突。发送冲突时，还需要遍历比较链表，找到最终的结果。在MySQL中，只有Memory存储引擎明确支持哈希索引，而innodb隐式支持哈希索引。这里隐含的支持意味着innodb引擎有一个特殊的功能“自适应哈希索引”。相同），它将在内存中的B-Tree索引之上创建一个哈希索引。这样，BTree索引也具有散列索引的一些优点。这是一种完全自动的内部行为。由于哈希结构的特殊性，使用它的检索效率非常高，通过哈希函数的映射可以一步完成。但也因为特殊的结构，哈希索引只适用于特定的场合。哈希索引[1]的限制：不支持范围查询，如WHEREa>5；只支持相等比较查询，包括=、IN、<=>不能用来规避数据排序操作；因为经过哈希函数的映射过程，使得哈希前后的大小关系丢失，所以不能按照索引值的顺序存储。不支持对部分索引列进行匹配查找，因为散列索引始终使用索引列的全部内容来计算散列值。比如在数据列（A，B）上创建哈希索引，如果查询只有数据列A，则无法使用该索引。没有办法避免表扫描。因为当发生哈希冲突时，存储引擎必须遍历链表中的所有行指针（拉链法），逐行比较，直到找到所有符合条件的行。在hash冲突较多的情况下，索引维护成本高，性能不一定比BTree索引高。BTree索引BTree实际上是一个多叉平衡搜索树。从名字可以看出，BTree首先是一个多叉搜索树，也就是说它是有顺序的；其次，BTree仍然是平衡的，即其左右子树的高度差小于等于1。实际上，一棵BTree需要满足以下条件：每个叶子节点的高度相同；每个非叶子节点由n-1个键和n个指针点组成，其中d<=n<=2d，键和点是分开的，节点的两端必须是键；叶节点指针全部为空；非叶子节点的key是[key,data]二进制组，其中key表示用作索引的key，data是key值所在行的数据；一棵常见的BTree树如下图所示。这是一个三阶BTree，可以通过键值的大小排序来查询和检索数据。叶子节点的指针都是空的，所以省略了绘制。从上图可以看出，BTree的树形比我们之前常见的二叉树等结构更扁平、更粗壮。之所以这样设计，还是跟读盘的特性有关。我们知道，在建立索引的时候，也是需要占用物理空间的。其实当数据量比较大的时候，索引文件的大??小也是很吓人的。考虑到一个表上可能有多个索引、组合索引和更小的数据行，索引文件的大??小可能达到物理磁盘数据的1/10，甚至1/3。这意味着索引不能完全适合内存。当通过索引访问数据时，对磁盘的读写访问是不可避免的。同时我们也知道内存的读写速度比磁盘快几个数量级。因此，在设计索引结构时，需要尽可能减少对磁盘的读写次数，也就是所谓的磁盘I/O次数。这也是索引采用BTree等扁平树结构的原因。树的层数越少，磁盘I/O的数量就越少。不仅如此，我们在上面提到了磁盘预读的局部性原则。根据这个原理和页表机制，从磁盘读取时性能可以得到很大的提升。与其他二叉树结构相比，BTree对磁盘的I/O非常少。但是在实际的数据库应用中还存在一些无法解决的问题。一是无法定位数据行。通过BTree，可以根据主键的排序定位主键的位置，但是由于数据表的记录有多个字段，定位主键是不够的，还需要定位数据排。虽然这个问题可以通过在BTree的节点中存储数据行或者添加定位字段来解决，但是这种方法会大大增加BTree的深度，同时也会导致I/O数量的增加。第二个是它不能处理范围查询。在实际应用中，数据库范围查询的频率很高，BTree只能定位一个索引位置。虽然可以通过顺序查询范围的左右边界得到，但是这样的操作实际上并不能很好的利用磁盘预读的局部性原理。顺序查询可能会导致预读传递的物理地址离散，导致I/O效率不高。三是数据量大的时候，BTree的高度还是会变得很高，搜索效率还是会明显下降。问题始终是推动改进的先决条件。基于以上考虑，出现了BTree的一个优化版本，即B+Tree。B+Tree索引B+Tree看起来像是在BTree的基础上进行的改进，那么究竟发生了什么变化呢？话不多说，我们先上图。上图其实就是一个带有顺序索引的B+Tree。与最基本的B+Tree的区别在于叶子节点是否通过指针连接。一般数据库常用的结构就是这种B+Tree，顺序索引。后面还会讨论顺序索引的B+Tree结构。对比BTree和B+Tree，我们可以发现两者主要有以下三个方面的不同：非叶子节点只存储key-value信息，不再存储数据。所有叶子节点之间有一个链指针，指向下一个叶子节点。数据存储在叶节点中。再看B+Tree，好像是树和有序链表的结合体。所以其实B+Tree也有树和链表的一些优点。树形结构使得有序检索更简单，I/O次数更少；有序的链表结构使得可以按照键值排序的顺序遍历所有记录。B+Tree作为索引结构可以带来的好处是：1.更少的I/O次数。这是因为如上所述，BTree的节点存储在内存页中。那么在内存页大小相同（一般为4k）的情况下，B+Tree可以存储更多的key值，那么整个树结构的高度就会更小，需要的I/O次数也会更小。二是数据遍历更方便。这个优势显然是有序链表带来的。通过叶子节点的链接，所有数据的遍历只需要在线性链表上完成，非常适合范围检索和范围查询。第三，查询性能更稳定。这自然是因为数据只存储在叶子节点中，所以所有的数据查询都会到达叶子节点，而叶子节点的高度是一样的，所以理论上所有数据的查询速度是一样的。正是因为B+Tree优秀的结构特性，才经常被用来作为索引的实现结构。在MySQL中，存储引擎MyISAM和InnoDB都分别用B+Tree实现了相应的索引设计。4物理存储虽然B+Tree结构在MyISAM和InnoDB中都可以使用，但是两种索引在物理存储层面的实现方式是不同的。InnoDB实现的是聚集索引，而MyISAM实现的是非聚集索引。在介绍聚簇索引之前，我们需要了解什么是页，不，什么是“主键索引”和“辅助索引”。其实这个概念很简单。刚才我们在讲B+Tree的时候说过，树的非叶子节点只存储键值。没错，就是关键值。当键值为数据表的主键时，则创建主键索引；当键值为其他字段时，为辅助索引。因此可以得出结论，主键索引只能有一个，而辅助索引可以有多个。聚簇索引和非聚簇索引的区别是根据对应的主键索引和辅助索引的不同特性来实现的。聚簇索引说回聚簇索引。先丢个定义。聚簇索引的主键索引的叶子节点存放的是键值本身对应的数据；辅助索引的叶子节点存储键值对应的数据的主键键值。这句话的信息量还是挺大的。首先分析第一句，主键索引的叶子节点存放的是key值对应的数据本身。我们知道，主键索引中存储的键值就是主键。也就是说，聚簇索引的主键索引在叶子节点中存储了主键和主键对应的数据。数据和主键索引作为叶节点的一部分存储在一起。然后分析第二句，辅助索引的叶子节点存放的是key值对应的数据的主键key值。我们也知道，辅助索引中存储的键值是一个非主键字段。也就是说，通过辅助索引，可以找到非主键字段对应的数据行中的主键。重点来了。当然，主键索引和辅助索引的结合又能做什么呢？当直接使用主键进行检索时，可以直接通过主键索引获取数据；而使用非主键进行检索时，需要先通过辅助索引得到主键，然后通过这个主键在主键索引中找到对应的数据行。让我举一个例子。假设有这样一张数据表。然后使用聚簇索引存储方式，对应的主键索引为：（主键为ID）对应的辅助索引为：（键值为Name，大致意思）：所以当使用whereID=7的条件时找到主键，然后根据B+树的检索算法，找到对应的叶子节点，进而得到行数据。对Name列进行条件查找，需要两步：第一步在辅助索引B+树中检索Name，到达其叶子节点获取对应的主键。第二步，使用主键对主键索引B+树种再进行一次B+树检索操作，最终到达叶子节点，得到整行数据。最后总结一下上面的过程，聚簇索引的实际过程分为以下两个过程。图片现在应该是可以理解的了。非聚集索引学习了聚集索引后，非聚集索引就简单多了。同样，让我们??先定义。非聚集索引的主键索引和辅助索引几乎是一样的，只是主索引不允许重复和空值，它们的叶子节点存储的是指向键值对应数据的物理地址。和聚簇索引相比，上面的定义能说明什么。首先，主键索引和辅助索引的叶子节点存储的是键值对应的数据的物理地址，也就是说主键索引和辅助索引都可以直接获取数据，不需要像聚簇索引这样的检索辅助。索引的时候多了一个弯路。同时也说明了一点，叶子节点存储的是物理地址，也就是说数据实际上存在于另外一个地方，而不是B+树的节点中。这说明非聚集索引的数据表和索引表是分开存储的。同样，非聚集索引的检索过程的总结。无论是主键索引还是辅助索引的检索过程，都只需要查找对应的B+Tree，得到数据对应的物理地址，然后通过顺序磁盘I/O访问数据即可。比较聚集索引和非聚集索引可以发现，两者的主要区别在于是否将数据存储在B+Tree的节点中，即数据和索引是否存储在一起。这种差异带来的最大问题是聚簇索引的索引顺序与数据本身的顺序相同，而非聚簇索引的顺序与数据的顺序无关。5索引优化引入这么多索引，其实归根结底就是要建立高性能的索引策略，对数据库中的索引进行优化。索引优化有很多角度，针对不同的业务场景可以采用不同的优化策略。这里考虑到文章篇幅，就不详细介绍了。下一次，我将发布一篇专门针对索引优化的文章。简单列举几个优化时可以考虑的方向：1独立列。索引列不能是表达式的一部分，也不能是函数的参数。2前缀索引和索引选择性。两者其实是相互制约的，制约条件在于前缀的长度。一般来说，你应该选择一个足够长的前缀来保证高选择性（保证查询效率），但又不能太长以节省空间。3尽量使用覆盖索引。覆盖索引是指包含所有需要查询的字段的值的索引，这样查询时只需要扫描索引，而不需要读取数据行，从而大大提高性能。4使用索引扫描进行排序。你应该知道扫描索引本身是非常快的。在设计索引时，尽量使用同一个索引，同时满足排序和行数据查找。最后，在建索引时有几个小技巧：1、优先使用自增键作为主键。2、记住最左前缀匹配原则。3、索引列不能参与计算。4、选择差异化程度高的列作为索引。索引6小结索引的概念和原理是我们在理解和掌握数据库过程中绕不开的重点。事实上，建立高性能指标对于实际应用场景也具有重要意义。这篇文章的目的还是介绍索引这个东西由浅入深，从概念到实现再到最后的优化策略。学无止境。在掌握了基本的理论和概念之后，需要在实际的服务器开发场景中，针对具体的问题和服务设计和使用索引优化方案。功力还不够，还需努力。7ReferenceHigh-performanceMySQL，BaronSchwartz等人撰写，电子工业出版社公众号码海系列文章https://www.jianshu.com/p/9e9aca844c13https://www.runoob.com/mysql/mysql-index.htmlhttps://www.cnblogs.com/Aiapple/p/5693239.htmlhttps://blog.csdn.net/tongdanping/article/details/79878302https://www.cnblogs.com/igoodful/p/9361500.html本文转载自微信公众号“业余码农”，可通过以下二维码关注。转载本文请联系业余码农公众号。
