如下内容参考和摘自：

http://www.cnblogs.com/linhaifeng/articles/7274563.html

https://www.cnblogs.com/tkzL/p/8708671.html

https://blog.csdn.net/qq_35892775/article/details/82668247

为什么要用索引，什么是索引？

对于大多数数据库，插入操作和一般的更新操作很少出现性能问题。在生产环境中，遇到最多的，也是最容易出问题的，还是一些复杂的查询操作，因此对查询语句的优化显然是重中之重。说起加速查询，就不得不提到索引了。

索引是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键，尤其是当表中的数据量越来越大时，索引对于性能的影响愈发重要。

索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高好几个数量级。

索引相当于字典的音序表，如果要查某个字，如果不使用音序表，则需要从几百页中逐页去查。

索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响，要找到一个平衡点，这对应用程序的性能至关重要。一些开发人员总是在事后才想起添加索引----这是一种错误的开发模式。如果知道数据的使用，从一开始就应该在需要处添加索引。开发人员往往对数据库的使用停留在应用的层面，比如编写SQL语句、存储过程之类，他们甚至可能不知道索引的存在，或认为事后让相关DBA加上即可。DBA往往不够了解业务的数据流，而添加索引需要通过监控大量的SQL语句进而从中找到问题，这个步骤所需的时间肯定是远大于初始添加索引所需的时间，并且可能会遗漏一部分的索引。当然索引也并不是越多越好：作者曾经遇到过某台MySQL服务器iostat显示磁盘使用率一直处于100%，经过分析后发现是由于开发人员添加了太多的索引，在删除一些不必要的索引之后，磁盘使用率马上下降为20%。可见索引的添加也是非常有技术含量的。

索引原理

数据库存储数据最终是以文件的形式存储到硬盘的。讲索引原理前先铺垫下硬盘的存储原理。

一般来说，在程序中使用的时候肯定要把磁盘文件中的数据读到内存中。那么就这个 “读” 的过程是什么样子的呢？磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。

图1-1 磁盘结构图1

图1-2 磁盘结构图2

图1-3 磁盘结构图3

图1-4 工作原理图

l   寻道时间指的是磁臂移动到指定磁道所需要的时间。寻道时间越短，I/O操作越快。主流磁盘的寻道时间一般在5ms以下。

l   旋转延迟

首先，读写头沿径向移动，移到要读取的扇区所在磁道的上方，这段时间称为寻道时间（seek time）。

然后，通过盘片的旋转，使得要读取的扇区转到读写头的下方，这段时间称为旋转延迟时间（rotational latency time）。

例：一个7200（转 /每分钟）的硬盘，每旋转一周所需时间为60×1000÷7200＝8.33毫秒，则平均旋转延迟时间为8.33÷2＝4.17毫秒（最多旋转１圈，最少不用旋转，平均情况下，需要旋转半圈）。

l   传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台 500 - MIPS 的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令（如果以 CPU 的指令执行效率来比较的话），数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。下图是计算机硬件延迟的对比图，供大家参考；

所以，问题的症结就在于磁盘 IO 是非常高昂的操作。

解决方案：

1.         计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO（一次 IO 的数据包括当前要读取的磁盘地址的数据+与之相邻的数据），这个理论对于索引的数据结构设计非常有帮助。

2.         每次查找数据时把磁盘IO次数控制在一个很小的数量级。

很明显：第1种解决方案是系统已经提供好的。要想实现第2种解决方案就需要一种稳定的数据结构能够满足几乎每次查询数据进行磁盘的 IO 次数是很少的。这个条件可以解释为：每次查询数据进行的 IO 次数都很少，说明这个数据结构不能像红黑树一样树的高度不可控，于是一个高度可控的多路搜索树就产生了，这就是 B + 树（B+树是通过二叉查找树，再由平衡二叉树，B树演化而来）。

B + 树的每一个节点（以磁盘的角度可以称作：磁盘块；参照下图）究竟存的是什么？

以一张表的 id 列为例，也就是主键列如果是索引的话，那么这张表的每一个 id 都会以 B+ 树的每一个节点存储到 B+ 树上，如果数据过多，一个节点就会存储多个 id（这里只是形象的认识，下面有详细解释）。

如上图，是一颗 B + 树，关于 B + 树的定义可以参见 B + 树，这里只说一些重点，浅蓝色的块我们称之为一个磁盘块，可以看到每个磁盘块包含几个数据项（深蓝色所示）和指针（黄色所示），如磁盘块1包含数据项17和35（如果以 id 为例的话，就代表一个节点（磁盘块）存放了两个 id），包含指针P1、P2、P3，P1表示小于17的磁盘块，P2表示在17和35之间的磁盘块，P3表示大于35的磁盘块。真实的数据存在于叶子节点即3、5、9、10、13、15、28、29、36、60、75、79、90、99。非叶子节点不存储真实的数据，只存储指引搜索方向的数据项（也就是说可以理解为是17、35的一个缩影），17、35并不真实存在于非叶子节点中。

那么 B + 树的查找数据的过程又是怎样的呢？

如图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存（并不是将所有的磁盘块（节点）一次性都加入到内存中），此时发生一次IO（磁盘加载块到内存的这个过程称为一次 IO），在内存中使用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据（以 id 作为索引的话就是几百万个 id 也就是几百万条数据），如果上百万的数据查找只需要三次IO（每一个磁盘块中存储多个 id），性能提高将是巨大的，如果没有索引，每个磁盘块都要发生一次IO（即使磁盘块里面可以装多个数据项的缩影，但是由于单个磁盘块的大小是 4k 或者 8k，这是由于操作系统限制的，所以单个磁盘块中不可能存储太多数据，所以磁盘块的数目依然很多），显然成本非常非常高。

B + 树的性质

1、索引字段要尽量的小：通过上面的查找数据的过程，我们知道 IO 次数取决于 B +树的高度 h，假设当前数据表的数据为 N，每个磁盘块的数据项的数量是 m，则有 h = ㏒(m+1) N，当数据量 N 一定的情况下，m 越大，h 越小；而 m = 磁盘块的大小 / 数据项的大小，磁盘块的大小也就是一个数据页的大小，是固定的，如果数据项占的空间越小，数据项的数量越多，树的高度越低。这就是为什么每个数据项，即索引字段要尽量的小（虽然数据项中存储的是索引字段的缩影,但是缩影的占字节数还是和真实的数据有关系的），比如 int 占4字节，要比 bigint8 字节少一半。这也是为什么 B + 树要求把真实的数据放到叶子节点而不是内层节点，一旦放到内层节点，磁盘块的数据项会大幅度下降，导致树增高。当数据项等于1（一个数据项占用一个磁盘块）时将会退化成线性表。

2、索引的最左匹配特性：当 B + 树的数据项是复合的数据结构，比如（name,age,gender）的时候，B + 树是按照从左到右的顺序来建立搜索树的，比如当(张三,20,F)这样的数据来检索的时候，B + 树会优先比较 name 来确定下一步的搜索方向，如果 name 相同再依次比较 age 和 gender，最后得到检索的数据；但当（20,F）这样的没有 name 的数据来的时候，B + 树就不知道下一步该查哪个节点，因为建立搜索树的时候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查询。比如当（张三,F）这样的数据来检索时，B + 树可以用 name 来指定搜索方向，但下一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是F的数据了， 这个是非常重要的性质，即索引的最左匹配特性。

到这里，大概了解了为什么要使用索引和对于索引及数据的存储的数据结构。

索引类型及分类

有关索引的类型和分类，可以参见下面这篇博客。

https://www.cnblogs.com/LiLiliang/p/9960895.html