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

因此：索引的本质是：索引是数据结构。

1.1 生活中的索引

​ 上面的理解比较抽象，举一个例子，平时看任何一本书，首先看到的都是目录，通过目录去查询书籍里面的内容会非常的迅速。

​ 上图是斗破苍穹章节目录，书籍的目录是按顺序放置的，有第一章，第二章，它本身就是一种顺序存放的数据结构，是一种顺序结构。

​ 另外通过目录（索引），可以快速查询到目录里面的内容，它能高效获取数据，通过这个简单的案例可以理解所以就是高效获取数据的数据结构

​ 再来看一个复杂的情况

​ 我们要去图书馆找一本书，这图书馆的书肯定不是线性存放的，它对不同的书籍内容进行了分类存放，整索引由于一个个节点组成，根节点有中间节点，中间节点下面又由子节点，最后一层是叶子节点，

​ 可见，整个索引结构是一棵倒挂着的树，其实它就是一种数据结构，这种数据结构比前面讲到的线性目录更好的增加了查询的速度。

1.2 MySQL中的索引

​ MySql 中的索引其实也是这么一回事，我们可以在数据库中建立一系列的索引，比如创建主键的时候默认会创建主键索引，上图是一种 BTREE 的索引。每一个节点都是主键的 ID。

​ 当我们通过 ID 来查询内容的时候，首先去查索引库，查到索引后能快速的根据索引定位数据的具体位置。

​ 所以索引是应用程序设计和开发的一个重要方面。若索引太多，应用程序的性能可能会受到影响。而索引太少，对查询性能又会产生影响。要找到一个合适的平衡点，这对应用程序的性能至关重要。

​ InnoDB 存储引擎支持以下几种常见的索引：B+树索引、全文索引、哈希索引。其中比较关键的是 B+树索引。

HashMap适合做数据库索引吗？

1. hash表只能匹配是否相等，不能实现范围查找；
2. 当需要按照索引进行order by时，hash值无法支持排序；
3. 组合索引可以支持部分索引查询，如：index(a,b,c)的组合索引，查询中只用到了a和b也是可以查询的，如果使用hash表，组合索引会将几个字段合并hash，没办法支持部分索引；
4. 当数据量很大时，hash冲突的概率也会非常大；

1.2.1 B+Tree

​ B+树索引就是传统意义上的索引，这是目前关系型数据库系统中查找最常用和最为有效的索引。

​ B+树索引的构造类似于二叉树，根据键值（Key Value）快速找到数据。

​ 注意：B+树中的B不是代表二叉（binary），而是代表平衡（balance），因为B+树是从最早的平衡二叉树演化而来，
但是B+树不是一个二叉树。

​ 在了解 B+树索引之前先要知道与之密切相关的一些算法与数据结构，这有助于我们更好的理解 B+树索引的工作方式，因为 B+树是通过二叉查找树，再由平衡二叉树，B 树演化而来。

1.2.1.1 二分查找

​ 二分查找法（binary search） 也称为折半查找法，用来查找一组有序的记录数组中的某一记录。

​ 其基本思想是：将记录按有序化（递增或递减）排列，在查找过程中采用跳跃式方式查找，即先以有序数列的中点位置作为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。

给出一个例子，注意该例子已经是升序排序的，且查找 数字 48
数据：5， 10， 19， 21， 31， 37， 42， 48， 50， 52
下标：0， 1， 2， 3， 4， 5， 6， 7， 8， 9
• 步骤一：设 low 为下标最小值 0 ， high 为下标最大值 9 ;
• 步骤二：通过 low 和 high 得到 mid ，mid=（low + high） / 2，初始时mid 为下标 4 (也可以=5，看具体算法实现)；
• 步骤三 ： mid=4 对应的数据值是 31，31 < 48（我们要找的数字）；
• 步骤四：通过二分查找的思路，将 low 设置为 31 对应的下标 4 ， high保持不变为 9 ，此时 mid 为 6 ；
• 步骤五 ： mid=6 对应的数据值是 42，42 < 48（我们要找的数字）；
• 步骤六：通过二分查找的思路，将 low 设置为 42 对应的下标 6 ， high保持不变为 9 ，此时 mid 为 7 ；
• 步骤七 ： mid=7 对应的数据值是 48，48 == 48（我们要找的数字），查找结束；
通过 3 次二分查找 就找到了我们所要的数字，而顺序查找需 8 次。

因此二分查找法的效率比顺序查找法要好（平均地来说)。但如果说查 5 这条记录，顺序查找只需 1 次，而二分查找法需要 4 次。我们来看，对于上面 10个数来说，顺序查找平均查找次数为（1+2+3+4+5+6+7+8+9+10)/10=5.5 次。

而二分查找法为(4+3+2+4+3+1+4+3+2+3)/10=2.9 次。在最坏的情况下，顺序查找的次数为 10，而二分查找的次数为 4。

1.2.1.2 二叉树系列

​ 本文数据结构不是重点，因此二叉树系列简单带过。

二叉树

​ 每个节点至多只有二颗子树，左子树和右子树，次序不能颠倒。

​ 逻辑上二叉树有五种基本形态：空二叉树、只有一个根结点的二叉树、只有左子树、只有右子树、完全二叉树（特例为满二叉树）。

​ 遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每个节点都被访问一次，而且只被访问一次，有前序、中序、后序遍历。

二叉查找(搜索)树

​ 二叉查找数首先肯定是一个二叉树，除此之外，还规定：在二叉查找树中，左子树的节点值总是小于根的节点值，右子树的节点值总是大于根的节点的值，也就是说：左子树节点值 < 根的节点值 < 右子树节点值。

因此可以通过中序遍历得到节点值的排序输出。以一个排序好的数组为例：

10、25、34、48、61、73、81

​ 可以将这个数组转为二叉树结构，其中数组的中间元素作为树的根结点，左半部分的中间元素作为根结点的左孩子，右半部分的中间元素作为根结点的右孩子，第二层的节点以此类推，最后树的层数就会越来越多，这样我们就构建好了一颗二叉树。

​ 同时这棵树，对于每个节点而言，其左孩子都小于它的父节点，右孩子都大于等于它的父节点。所以这样的二叉树也是一个二叉查找数（binary search tree），它的查找时间复杂度和二分查找一样，O(logN)。

​ 但是二叉查找树，如果设计不良，完全可以变成一颗极不平衡的二叉查找树：

​

​ 查找效率和顺序查找基本没差别了。因此若想最大性能地构造一棵二叉查找树，需要这棵二叉查找树是平衡的，从而引出了新的定义——平衡二叉树，或称为 AVL 树

平衡二叉树(AVL-树)

​ 平衡二叉树的定义如下：首先符合二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1.

​ 平衡二叉树的查找性能是比较高的，但不是最高的，只是接近最高性能，最好的性能需要建立一棵最优二叉树，但是最优二叉树的建立和维护需要大量的操作，因此，用户一般只需建立一棵平衡二叉树即可。

​ 平衡二叉树的查询速度的确很快，但是维护一棵平衡二叉树的代价是非常大的。通常来说，需要 1 次或多次左旋和右旋来得到插入、更新和删除后树的平衡性。

​

​ 平衡二叉树对一个数据库来说，有什么问题？

​ 因为二叉树每个节点最多只有两个直属子节点，所以当节点数比较多时，二叉树的高度增长很快，比如 1000个节点时，树的高度差不多有 9 到 10 层。
​ 我们知道数据库是持久化的，数据是要从磁盘上读取的，一般的机械磁盘每秒至少可以做 100 次 IO，一次 IO 的时间基本上在 0.01 秒，1000 个节点在查找时就需要 0.1 秒，如果是 10000 个节点，100000 个节点呢？
​ 所以对数据库来说，为了减少树的高度，提出了 B+树的数据结构。

1.2.1.3 B+树

B+树的定义

​ B+树和二叉树、平衡二叉树一样，都是经典的数据结构。B+树由B树和索引顺序访问方法演变而来，但是在现实使用过程中几乎已经没有使用B树的情况了。

​ B+树的定义在很多数据结构书中都能找到，非常复杂，我们概略它的定义：
​ B+树是B树的一种变形形式，B+树上的叶子结点存储关键字以及相应记录的地址(引用 or 指针)，叶子结点以上各层作为索引使用。

一颗m阶的B+树定义如下：

• 每个节点最多可以有m个元素；
• 除了根节点外，每个节点最少有（m/2）个元素；
• 如果根结点不是叶节点，那么它最少有2个孩子节点；
• 所有的叶子节点都在同一层；
• 一个有 k 个孩子节点的非叶子节点有 (k -1)个元素，按升序排列；
• 某个元素的左子树中的元素都比它小，右子树的元素都大于或等于它；
• 非叶子节点只存放关键字和指向下一个孩子节点的索引，记录只存放在叶子节点中；
• 相邻的叶子节点之间用指针相连；

B+树的变体为 B*树，在 B+树的非根和非叶子结点再增加指向兄弟的指针；
B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为 2/3（代替 B+树的 1/2）。

概要的了解下 B 树和 B+树。

B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。

​ 在B+树中，所有记录节点都是按键值的大小顺序存放在同一层的叶子节点上，由各叶子节点指针进行链接。

​

​ 从上图我们可以归纳出 B+树的几个特征，在 B+树的简要定义中其实已经包括了：
​ 1、相同节点数量的情况下，B+树高度远低于平衡二叉树；
​ 2、非叶子节点只保存索引信息和下一层节点的指针信息，不保存实际数据记录；
​ 3、每个叶子页（LeafPage）存储了实际的数据，比如上图中每个叶子页就存放了 4 条数据记录，当然可以更多，叶子节点由小到大（有序）串联在一起，叶子页中的数据也是排好序的；
​ 4、索引节点指示该节点的左子树比这个索引值小，而右子树大于等于这个索引值。

​ 注意：叶子节点中的数据在 物理存储上 完全可以 是无序 的，仅仅是在逻辑上有序（通过指针串在一起）。

B+树的插入

B+树的删除

磁盘和B+树

​ 为什么关系型数据库都选择了B+树，这个和磁盘的特性有着非常大的关系。

​

​ 简化一下，可以这么看

​

​ 一个磁盘由大小相同且同轴的圆形盘片组成，磁盘可以转动（各个磁盘必须同步转动）。

​ 在磁盘的一侧有磁头支架，磁头支架固定了一组磁头，每个磁头负责存取一个磁盘的内容。磁头不能转动，但是可以沿磁盘半径方向运动。

​ 盘片被划分成一些列同心环，圆心是盘片中心，每个同心环叫做一个磁道，所有半径相同的磁道组成一个柱面。磁道被沿半径线划分成一个个小的段，每个段叫做一个扇区，每个扇区是磁盘的最小存储单元也是最小读写单元。现在磁盘扇区一般是512字节~4K个字节。

​ 磁盘上数据必须用一个三维地址唯一标示：柱面号、盘面号、扇区号。

读/写磁盘上某一指定数据需要下面步骤：

• 首先移动臂根据柱面号使磁头移动到所需要的柱面上，这一过程被称作定位或查找。
• 所有磁头都定位到磁道上后，这时根据盘面号来确定指定盘面上的具体磁道。
• 盘面确定以后，盘片开始旋转，将指定块号的磁道段移动至磁头下。

​ 经过上面步骤，指定数据的存储位置就被找到。这时就可以开始读/写操作了。

磁盘读取依靠的是机械运动，分为寻道时间、旋转延迟、传输时间三个部分。
这三个部分耗时相加就是一次磁盘IO的时间，一般大概9ms左右。

寻道时间（seek）是将读写磁头移动至正确的磁道上所需要的时间，这部分时间代价最高；

旋转延迟（rotation）是磁盘旋转将目标扇区移动到读写磁头下方所需要的时间，取决于磁盘转速；

数据传输时间（transfer）是完成传输数据所需需要的时间，取决于接口的数据传输率，在纳秒级，远小于前两部分消耗时
间。

磁盘读取时间成本是访问内存的几百倍到几万倍之间。

为了提高效率，要尽量减少磁盘 I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存，这个称之为 预读。这样做的理论依据是计算机科学中著名的局部性原理：

当一个数据被用到时，其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间）。

一般来说，磁盘顺序读的效率是随机读的40到400倍都有可能，顺序写是随机写的10到100倍（SSD盘则差距要小的多，顺序读写的效率是随机读写的 7到 10 倍，但是有评测表明机械硬盘的顺序写性能稍优于 SSD。总的来说 Mysql数据库如果由硬盘由机械的换成 SSD 的，性能会有很大的提升），因此对于具有局部性的程序来说，预读可以提高I/O效率。

预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储
块称为一页，页大小通常为 4k 当然也有 16K 的，主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁
盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

按照磁盘的这种性质，如果是一个页存放一个 B+树的节点，自然是可以存放很多的数据的，比如 InnoDB 里，默认定义的 B+树的节点大小是 16KB，这就是
说，假如一个 Key 是 8 个字节（加指针4个字节），那么一个节点可以存放大约 1000 个 Key，意味着 B+数可以有 1000 个分叉。同时 InnoDB 每一次磁盘 I/O，读取的都是 16KB 的整数倍的数据。也就是说 InnoDB 在节点的读写上是可以充分利用磁盘顺序 IO 的高速读写特性。

同时按照 B+树逻辑结构来说，在叶子节点一层，所有记录的主键按照从小到大的顺序排列，并且形成了一个双向链表。同一层的非叶子节点也互相串联，
形成了一个双向链表。那么在实际读写的时候，很大的概率相邻的节点会放在相邻的页上，又可以充分利用磁盘顺序 IO 的高速读写特性。

所以我们对 MySQL 优化的一大方向就是 尽可能的多让数据顺序读写，少让数据随机读写。

总结B+树的作用

• 在块设备上，通过 B+树可以有效的存储数据；
• 所有记录都存储在叶子节点上，非叶子(non-leaf)存储索引(keys)信息；而且记录按照索引列的值由小到大排好了序。
• B+树含有非常高的扇出（fanout），通常超过 100，在查找一个记录时，可以有效的减少 IO 操作；

Tips：
扇出 是每个索引节点(Non-LeafPage)指向每个叶子节点(LeafPage)的指针；
扇出数 = 索引节点(Non-LeafPage)可存储的最大关键字个数 + 1

1.2.2 InnoDB中的索引

InnoDB 中的索引也是按照 B+树来组织的。

1.2.2.1. 聚集索引 / 聚簇索引

InnoDB 中使用了聚集索引，就是将表的主键用来构造一棵 B+树，并且将整张表的行记录数据存放在该 B+树的叶子节点中。也就是所谓的索引即数据，数据即索引。由于聚集索引是利用表的主键构建的，所以每张表只能拥有一个聚集索引。

聚集索引的叶子节点就是数据页。换句话说，数据页上存放的是完整的每行记录。因此聚集索引的一个优点就是：通过过聚集索引能获取完整的整行数据。另一个优点是：对于主键的排序查找和范围查找速度非常快。

如果我们没有定义主键呢？MySQL 会使用唯一性索引，没有唯一性索引，MySQL 也会创建一个隐含列RowID来做主键，然后用这个主键来建立聚集索引。

1.2.2.2 辅助索引 / 二级索引

聚簇索引只能在搜索条件是主键值时才能发挥作用，因为 B+树中的数据都是按照主键进行排序的,那如果我们想以别的列作为搜索条件怎么办？我们一般会建立多个索引，这些索引被称为辅助索引/二级索引。

对于辅助索引(Secondary Index，也称二级索引、非聚集索引)，叶子节点并不包含行记录的全部数据。

叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签( bookmark)。

该书签用来告诉 InnoDB 存储引擎哪里可以找到与索引相对应的行数据。因此 InnoDB 存储引擎的辅助索引的书签就是相应行数据的聚集索引键。

比如辅助索引 index(node)，那么叶子节点中包含的数据就包括了(主键、note)。

回表

辅助索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个辅助索引。

当通过辅助索引来寻找数据时，InnoDB 存储引擎会遍历辅助索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引（聚集索引）来找到一个完整的行记录。这个过程也被称为 回表。

也就是根据辅助索引的值查询一条完整的用户记录需要使用到 2 棵 B+树----一次辅助索引，一次聚集索引。

为什么我们还需要一次回表操作呢？直接把完整的用户记录放到辅助索引的叶子节点不就好了么？

如果把完整的用户记录放到叶子节点是可以不用回表，但是太占地方了，相当于每建立一棵 B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。而且每次对数据的变化要在所有包含数据的索引中全部都修改一次，性能也非常低下。
很明显，回表的记录越少，性能提升就越高，需要回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用二级索引。

那什么时候采用全表扫描的方式，什么时候使用采用二级索引 + 回表的方式去执行查询呢？

这个就是查询优化器做的工作，查询优化器会事先对表中的记录计算一些统计数据，然后再利用这些统计数据根据查询的条件来计算一下需要回表的记录数，需要回表的记录数越多，就越倾向于使用全表扫描，反之倾向于使用二级索引 + 回表的方式。(具体怎么算的，我们后面会详细说到。)

1.2.2.3 联合索引 / 复合索引

前面我们对索引的描述，隐含了一个条件，那就是构建索引的字段只有一个，但实践工作中构建索引的完全可以是多个字段。所以，将表上的多个列组合起来进行索引我们称之为联合索引或者复合索引，比如 index(a,b)就是将 a,b 两个列组合起来构成一个索引。

千万要注意一点，建立联合索引只会建立 1 棵 B+树，多个列分别建立索引会分别以每个列则建立 B+树，有几个列就有几个 B+树，比如，index(note)、index(b)，就分别对 note,b 两个列各构建了一个索引。

index(note,b)在索引构建上，包含了两个意思：
1、先把各个记录按照 note 列进行排序。
2、在记录的 note 列相同的情况下，采用 b 列进行排序

1.2.2.4 覆盖索引 / 索引覆盖

既然多个列可以组合起来构建为联合索引，那么辅助索引自然也可以由多个列组成。

InnoDB 存储引擎支持覆盖索引(covering index，或称索引覆盖)，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。

使用覆盖索引的一个好处是辅助索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的 IO 操作。

所以记住，覆盖索引并不是索引类型的一种。

1.2.2.5. 自适应哈希索引

InnoDB 存储引擎除了我们前面所说的各种索引，还有一种自适应哈希索引，我们知道 B+树的查找次数,取决于 B+树的高度,在生产环境中,B+树的高度一般为 3~4 层,故需要 3~4 次的 IO 查询。
所以在 InnoDB 存储引擎内部自己去监控索引表，如果监控到某个索引经常用，那么就认为是热数据，然后内部自己创建一个 hash 索引，称之为自适应哈希索引( Adaptive Hash Index,AHI).

创建以后，如果下次又查询到这个索引，那么直接通过 hash 算法推导出记录的地址，直接一次就能查到数据，比重复去B+tree 索引中查询三四次节点的效率高了不少。

InnoDB 存储引擎使用的哈希函数采用除法散列方式，其冲突机制采用链表方式。注意，对于自适应哈希索引仅是数据库自身创建并使用的，我们并不能对其进行干预。通过命令 show e engine b innodb G 可以看到当前自适应哈希索引的使用状况，如:

1.2.3 索引在查询中的使用

1、 一个索引就是一个 B+ 树 ， 索引让我们的查询可以快速定位和扫描到我们需要的数据记录上，加快查询的速度。
2、 一个 s st elect 查询语句在执行过程中一般最多能使用一个二级索引，即使在where 条件中用了多个二级索引。

1.2.3.1 扫描区间

对于某个查询来说，最简单粗暴的执行方案就是扫描表中的所有记录，判断每一条记录是否符合搜索条件。如果符合，就将其发送到客户端，否则就跳过该记录。这就是全表扫描。

对于使用 InnoDB 存储引擎的表来说，全表扫描意味着从聚簇索引第一个叶子节点的第一条记录开始，沿着记录所在的单向链表向后扫描，直到最后一个叶子节点的最后一条记录。虽然全表扫描是一种很笨的执行方案，但却是一种万能的执行方案，所有的查询都可以使用这种方案来执行，只是效率不高。

我们有了索引，利用 B+树查找索引列值等于某个值的记录，这样可以明显减少需要扫描的记录数量。由于 B+树叶子节点中的记录是按照索引列值由小到大的顺序排序的，所以即使只扫描某个区间或者某些区间中的记录也可以明显减少需要扫描的记录数量。比如下面这个查询语句:
SELECT * FROM order_exp WHERE id >= 3 AND id<= 99;

这个语句其实是想查找 id 值在[3,99]区间中的所有聚簇索引记录。我们可以通过聚簇索引对应的 B+树快速地定位到 id 值为 3 的那条聚簇索引记录，然后沿着记录所在的单向链表向后扫描,直到某条聚簇索引记录的 id 值不在[3,99]区间中为止。

与全表扫描相比，扫描 id 值在[3,99]区间中的记录已经很大程度地减少了需要扫描的记录数量，所以提升了查询效率。其实所谓的全表扫描，我们可以理解为扫描的区间是[负无穷，正无穷]或者[第一条记录，最后一条记录]。

再看下面这个查询语句:

SELECT * FROM order_exp WHERE id in(3,9) OR (id>=23 AND id<= 99);

这里有几个扫描区间？三个，两个单独扫描区间[3,3]、[9,9]，一个范围扫描区间[23,99]。

再看下面这个查询语句:

SELECT * FROM order_exp WHERE order_no <'DD00_10S' AND expire_time > '2021-03-22 18:28:28' AND order_note > '7 排';

这个语句里，order_no 和 expire_time 都有索引，order_note 没有索引，那会有两个扫描区间吗？并不会，请记住，一个 Select 查询语句在执行过程中一般最多能使用一个二级索引。那么也就是说：
如果用 idx_order_no 执行查询，那扫描区间就是 [第一条记录，'DD00_10S']，expire_time> '2021-03-22 18:28:28' AND order_note > '7 排'只能成为普通的搜索或者说判定条件。

如果说用 idx_expire_time 执行查询，那扫描区间就是['2021-03-22 18:28:28'，最后一条记录]，order_no <'DD00_10S' AND order_note > '7排'只能成为普通的搜索或者说判定条件。
无论用哪个索引执行查询，都需要获取到索引中的记录后，进行回表，获取到完整的用户记录后再根据判定条件判断这条记录是否满足 SQL 语句的要求。

1.2.3.2 范围区间扫描

其实对于 B+树索引来说，只要索引列和常数使用=、<=>、IN、NOT IN、IS NULL、IS NOT NULL、>、<、>=、<=、BETWEEN、!=（不等于也可以写成<>）或者 LIKE操作符连接起来，就可以产生一个区间。

1、IN 操作符的效果和若干个等值匹配操作符=之间用OR连接起来是一样的，也就是说会产生多个单点区间，比如下边这两个语句的效果是一样的：

SELECT * FROM order_exp WHERE insert_time IN (2021-03-22 18:23:42, yyyy);
SELECT * FROM order_exp WHERE insert_time= 2021-03-22 18:23:42 ORinsert_time = yyyy;

2、!=产生的扫描区间呢？比如

SELECT * FROM order_exp WHERE order_no != 'DD00_9S'

此时使用 idx_expire_time 执行查询时对应的扫描区间就是[第一条记录 ,'DD00_9S']和[ 'DD00_9S',最后一条记录]。

3、LIKE 操作符比较特殊，只有在匹配完整的字符串或者匹配字符串前缀时才产生合适的扫描区间。

对于某个索引列来说，字符串前缀相同的记录在由记录组成的单向链表中肯定是相邻的。比如我们有一个搜索条件是 note LIKE' b%'，对于二级索引 idx_note来说，所有字符串前缀为'b'的二级索引记录肯定是相邻的。这也就意味着我们只要定位到 idx_note 值的字符串前缀为'b'的第一条记录，就可以沿着记录所在的单向链表向后扫描，直到某条二级索引记录的字符串前缀不为 a 为止。

很显然，note LIKE' b%' 形成的扫描区间相当于['b', 'c')。
不过在日常的工作中，一个查询的 WHERE 子句可能有很多个小的搜索条件，这些搜索条件需要使用 AND 或者 OR 操作符连接起来，我们来看看怎么从由 AND或 OR组成的复杂搜索条件中提取出正确的范围区间。

1.2.3.3 所有搜索条件都可以使用某个索引的情况

有时候每个搜索条件都可以使用到某个索引，比如下边这个查询语句：

SELECT * FROM order_exp WHERE order_no > 'DD00_6S' AND order_no >'DD00_9S';

这个查询中的搜索条件都可以使用到 idx_order_no，也就是说每个搜索条件都对应着一个 idx_order_no 的范围区间。这两个小的搜索条件使用 AND 连接起来，也就是要取两个范围区间的交集，两者交集当然就是 order_no > 'DD00_9S'了，也就是说上边这个查询使用 idx_order_no 的范围区间就是('DD00_9S', 最后一条记录)。
再看一下使用 OR 将多个搜索条件连接在一起的情况：

SELECT * FROM order_exp WHERE order_no > 'DD00_6S' OR order_no >'DD00_9S';

OR 意味着需要取各个范围区间的并集，所以上边这个查询使用 idx_expire_time 的范围区间就是( 'DD00_6S' ,最后一条记录)。

1.2.3.4 有的搜索条件无法使用索引的情况

比如下边这个查询：

SELECT * FROM order_exp WHERE expire_time > '2021-03-22 18:35:09' AND order_note = 'abc';

请注意，这个查询语句中能利用的索引只有 idx_expire_time 一个，而idx_expire_time 这个二级索引的记录中又不包含 order_note 这个字段，所以在使用二级索引 idx_expire_time 定位记录的阶段用不到 order_note = 'abc'这个条件，这个条件是在回表获取了完整的用户记录后才使用的，而范围区间是为了到索引中取记录中提出的概念，所以在确定范围区间的时候不需要考虑 order_note ='abc'这个条件。

我们把上边的查询中用不到 idx_expire_time 的搜索条件化简之后就是这样：

SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:35:09';

也就是说最上边那个查询使用idx_expire_time的范围区间就是：('2021-03-22 18:35:09',最后一条记录)。

再来看一下使用 OR 的情况：

SELECT * FROM order_exp WHERE expire_time> '2021-03-22 18:35:09' OR order_note = 'abc';

这条语句在搜索时可以化简为：

SELECT * FROM order_exp ;

这也就说如果我们使用 idx_expire_time执行查询的话，对应的范围区间就是[第一条记录,最后一条记录]，也就是需要将全部二级索引的记录进行回表，这个代价肯定比直接全表扫描都大了。也就是说一个使用到索引的搜索条件和没有使用该索引的搜索条件使用 OR 连接起来后是无法使用该索引的。为什么？道理很简单，idx_expire_time 这个二级索引的记录中不包含 order_note 这个字段，那就说，即使二级索引 idx_expire_time 中找到了满足 expire_time> '2021-03-22 18:35:09'的记录，是无法判定 order_note 是否满足 order_note = 'abc'的，又因为是 OR 条件，所以必须要在主键索引中从第一条记录到最后一条记录逐条判定order_note 是否等于 'abc'。

1.2.3.5 复杂搜索条件下找出范围匹配的区间

有的查询的搜索条件可能特别复杂，比方说下边这个：

SELECT * FROM order_exp WHERE (order_no > 'DD00_9S' AND expire_time = '2021-03-22 18:35:09' ) OR (order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR (order_no LIKE '%0S' AND order_no > 'DD00_12S' AND (expire_time < '2021-03-22 18:28:28' OR order_note = 'abc')) ;

分析一下：
首先查看 WHERE 子句中的搜索条件都涉及到了哪些列，哪些列可能使用到索引。

这个查询的搜索条件涉及到了 order_no、expire_time、order_note这 3 个列。

其中 order_no 列有二级索引 idx_order_no，expire_time 列有二级索引idx_expire_time。

对于那些可能用到的索引，分析它们的范围区间。

使用 idx_order_no 执行查询

我们需要把那些用不到该索引的搜索条件暂时移除掉。上边的查询中除了有关 expire_time 和 order_note 列不能使用到 idx_order_no 索引外，order_no LIKE '%0S'也使用不到索引。

如果条件太复杂，看着演化怕出错，我们可以把所有用不到的搜索条件视为True 来进行中间替换，所以把这些搜索条件替换为 True 之后的样子就是这样：

(order_no > 'DD00_9S' AND TRUE ) OR
(order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR
(TRUE AND order_no > 'DD00_12S' AND (TRUE OR TRUE))

再化简：

(order_no > 'DD00_9S') OR
(order_no < 'DD00_6S' AND order_no > 'DD00_9S') OR
(order_no > 'DD00_12S')

接下来替换掉永远为 TRUE 或 FALSE 的条件
因为符合 order_no < 'DD00_6S' AND order_no > 'DD00_9S'永远为 FALSE，所以上边的搜索条件可以被写成这样：

(order_no > 'DD00_9S') OR (order_no > 'DD00_12S')

很明显，两者使用 OR 操作符连接起来的，意味着要取并集，所以最终的结果化简的到的区间就是：order_no > 'DD00_12S'。也就是说：上边那个复杂搜索条件的查询语句如果使用 idx_order_no 索引执行查询的话，需要把满足order_no > 'DD00_12S'的二级索引记录都取出来，然后拿着这些记录的 id 再进行回表，得到完整的用户记录之后再使用其他的搜索条件进行过滤。记住，我们说的是如果使用idx_order_no 索引执行查询，不代表 MySQL 一定会使用，因为MySQL 需要做整体评估，才能确定是否使用这个索引还是别的索引，或者是干脆全表扫描。

使用 idx_expire_time 执行查询

我们需要把那些用不到该索引的搜索条件暂时使用 TRUE 条件替换掉，其中有关 order_no 和 order_note 的搜索条件都需要被替换掉，替换结果就是：

(TRUE AND expire_time = '2021-03-22 18:35:09' ) OR
(TRUE AND TRUE) OR
(TRUE AND TRUE AND (expire_time < '2021-03-22 18:28:28' OR TRUE))

按照布尔运算的规则，expire_time < '2021-03-22 18:28:28' OR TRUE 的结果肯定是 TRUE，也就是说化简之后的搜索条件成这样了：

expire_time = '2021-03-22 18:35:09' OR TRUE

这个化简之后的结果就更简单了：TRUE
这个结果也就意味着如果我们要使用 idx_expire_time 索引执行查询语句的话，需要扫描 idx_expire_time 二级索引的所有记录，然后再回表，这种情况下为啥 MySQL 不直接全表扫描呢？所以一定不会使用 idx_expire_time 索引的。

Tips:上面这个 SQL 语句，执行全表扫描的代价大概是 2169，用 idx_order_no索引的代价大概是 6211，所以，实际执行的时候，MySQL 会选择全表扫描。

1.2.3.6 使用联合索引执行查询时对应的扫描区间

1.2.4 简单了解MyISAM中的索引

我们知道 InnoDB 中索引即数据，也就是聚簇索引的那棵 B+树的叶子节点中已经把所有完整的用户记录都包含了，而 MyISAM 的索引方案虽然也使用树形结构，但是却将索引和数据分开存储的。

MyISAM 将表中的记录按照记录的插入顺序单独存储在一个文件中，称之为数据文件。这个文件并不划分为若干个数据页，有多少记录就往这个文件中塞多少记录就成了。我们可以通过行号而快速访问到一条记录。

由于在插入数据的时候并没有刻意按照主键大小排序，所以我们并不能在这些数据上使用二分法进行查找。

使用 MyISAM 存储引擎的表会把索引信息另外存储到一个称为索引文件的另一个文件中。MyISAM 会单独为表的主键创建一个索引，只不过在索引的叶子节点中存储的不是完整的用户记录，而是主键值＋行号的组合。也就是先通过索引找到对应的行号，再通过行号去找对应的记录!

这一点和 InnoDB 是完全不相同的，在 InnoDB 存储引擎中，我们只需要根据主键值对聚簇索引进行一次查找就能找到对应的记录，而在 MyISAM 中却需要进行一次回表操作，意味着 MyISAM 中建立的索引相当于全部都是二级索引！

如果有需要的话，我们也可以对其它的列分别建立索引或者建立联合索引，原理和 InnoDB 中的索引差不多，不过在叶子节点处存储的是相应的列＋行号。这些索引也全部都是二级索引。

1.2.5 创建和删除索引的语句

那我们如何使用 SQL 语句去建立这种索引呢? InnoDB 和 MyISAM 会自动为主键或者声明为 UNIQUE 的列去自动建立 B+树索引，但是如果我们想为其他的列建立索引就需要我们显式的去指明。

查看索引

SHOW INDEX FROM table_name\G

创建修改索引

CREATE TALBE 表名 (
    各种列的信息 ··· ,
    [KEY|INDEX] 索引名 (需要被索引的单个列或多个列)
)

CREATE [UNIQUE] INDEX indexName ON mytable(columnname(length));

ALTER TABLE 表名 ADD [UNIQUE] INDEX [indexName] ON (columnname(length))

删除索引

DROP INDEX [indexName] ON mytable;
ALTER TABLE 表名 DROP [INDEX|KEY] 索引名;

1.2.6 索引的代价

虽然索引是个好东西，在学习如何更好的使用索引之前先要了解一下使用它的代价，它在空间和时间上都会拖后腿。

1.2.6.1 空间上的代价

这个是显而易见的，每建立一个索引都要为它建立一棵 B+树，
每一棵 B+树的每一个节点都是一个数据页，
一个页默认会占用 16KB 的存储空间，
一棵很大的 B+树由许多数据页组成会占据很多的存储空间。

1.2.6.2 时间上的代价

每次对表中的数据进行增、删、改操作时，都需要去修改各个 B+树索引。

而且我们讲过，B+树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是非叶子内节点中的记录都是按照索引列的值从小到大的顺序而形成了一个单向链表。

而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收的操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的 B+树都要进行相关的维护操作，这必然会对性能造成影响。