1.1 什么是索引
我们用一个例子来逐渐引出啥是索引。话说大老板东哥有一天想体验一下快递小哥的生活，就去自家快递公司准备干活了，一进仓库看到一地的快递，兴冲冲的就问旁边的快递小哥 “这么多快递，我要找一个人的快递怎么办？”。快递小哥说 “你可以一件件找，直到找到你要的那件快递”，东哥一听脸顿时黑了 “淦！上十万件快递你要我一件件找，是想累死我，然后继承我的白条吗？” 说完一甩修了扭头就会豪宅去了。
第二天，快递公司老板去找东哥说 “领导，我们已经改进了，再去指导指导呗”。东哥一听，哎呀！动作挺快，然后就又到快递公司了，问 “你们想出什么办法了吗”。快递小哥连忙回答 “我们给所有的快递都编了号，做了一个表格，只要从表格中找到编号就可以找到快递了”，东哥心想，我从上十万的名单里找出了编码，还要去上十万的快递里扒出快递，还是太累了就说 “我时间有限有没有更快的办法”。
快递公司老板一听，这还得了，大 BOOS 不满意了，得亏有备用方案，就说 “领导，我们还有个方案，我们做个快递柜，1 ~ 10 号快递放 0 号，10 ~ 20 放 1 号，依次类推，只要找到了快递编码，很快就可以找到快递了”。东哥一听，不错哈！这么干就快多了，但是我还要从上十万的表格中找出编码，难受啊！一脸的难受。快递公司老板冷汗直流，这是嫌找编码满了啊，该怎么办，BOOS 一怒，回家种地。这时一个程序员站住来说 “领导，我们还有个方案，我们把表格进行优化，按照姓名首字母来分类，就可以很快的找到指定的名字和编码”。东哥大喜，升职加薪！
从上面的例子可以推出，如果没有索引，必须遍历整个表，直到指定快递被找到为止；有了索引之后，即可在索引中查找。由于索引是经过某种算法优化过的，因而查找次数要少的多。可见，索引是用来定位的。官方来讲就是：索引是对数据库表中一列或多列的值进行排序的一种结构，使用索引可快速访问数据库表中的特定信息。
1.2 索引的本质
1.2.1 概述
MySQL 官方对索引的定义为：索引(Index)是帮助 MySQL 高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。最基本的查询算法当然是顺序查找(linear search)，这种复杂度为 O(n) 的算法在数据量很大时显然是糟糕的，好在计算机科学的发展提供了很多更优秀的查找算法，例如：二分查找(binary search)、二叉树查找(binary tree search)等。
稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如：二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构，所以在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用(指向)数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构
1.2.2 B-Tree
在计算机科学中，B 树(英语：B-Tree)是一种自平衡的树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B 树，概括来说是一个一般化的二叉查找树(binary search tree)，可以拥有多于 2 个子节点。与自平衡二叉查找树不同，B 树为系统大块数据的读写操作做了优化。B 树减少定位记录时所经历的中间过程，从而加快存取速度。B 树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。B树是一种多路平衡搜索树(非二叉)，若其是 M 路，则：
任意非叶子节点最多可以有 M 个子女，且 M > 2；
根节点的子女数为 [2，M]；
除了根节点以外的非叶子节点的子女数目为 M / 2 (向上取整)个到 M 个；
每个节点存放至少 M / 2-1 (向上取整)和至多 M – 1 个键值(至少两个)；
非叶子节点的关键字个数 = 指向子女的指针个数 – 1；
非叶子节点的关键字 K[1]，K[2]，··· ，K[M-1] 且有 K[i] < K[i+1]；
非叶子节点的指针 P[1]，P[2]，··· ，P[M]；其中 P[1] 指向关键字小于 K[1] 的子树，P[M] 指向关键字大于 K[M-1] 的子树，其他 P[i] 指向关键字属于(K[i-1]，K[i])的子树；
所有叶子节点都位于同一层。
B 树与二叉搜索树的最大区别在于其每个节点可以存不止一个键值，并且其子女不止两个，不过还是需要满足键值数 = 子女数 – 1。因此，对于相同数量的键值，B 树比二叉搜索树要更加矮一些，特别是当 M 较大时，树高会更低。
每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个键将数据划分成的三个范围域，对应三个指针指向的子树的数据的范围域。以根节点为例，关键字为 17 和 35，P1 指针指向的子树的数据范围为小于 17，P2 指针指向的子树的数据范围为 17~35，P3 指针指向的子树的数据范围为大于 35。模拟查找关键字 29 的过程：
根据根节点找到磁盘块 1，读入内存。【磁盘第 1 次 IO 操作】
比较关键字 29 在区间(17，35)，找到磁盘块 1 的指针 P2
根据 P2 指针找到磁盘块 3，读入内存。【磁盘第 2 次 IO 操作】
比较关键字 29 在区间(26，30)，找到磁盘块 3 的指针 P2
根据 P2 指针找到磁盘块 8，读入内存。【磁盘第 3 次 IO 操作】
在磁盘块 8 中的关键字列表中找到关键字 29
分析上面过程，发现需要 3 次磁盘 IO 操作，和 3 次内存查找操作，由于内存中的关键字是一个有序表结构，可以利用二分法快速定位到目标数据，而 3 次磁盘 IO 操作是影响整个 B-Tree 查找效率的决定因素。
MySQL 采用页方式来读写数据，每页是16KB，我们用 B 树来存储 MySQL 的记录，每个节点对应 MySQL 中的一页 16 KB，假如每行记录加上树节点中的 1 个指针占 160 Byte，那么每个节点可以存储 16 KB / 160 byte = 1000 条数据，树的高度为 3 的节点大概可以存储 1000(第一层) + 10002(第二层) + 10003(第三层) 条记录，即一个高度为 3 的 B 树大概可以存储 10 亿条记录，我们从 10 亿记录中查找数据只需要 3 次 IO 操作可以定位到目标数据所在的页，而页内部的数据又是有序的，然后将其加载到内存中用二分法查找，是非常快的。
可以看出使用 B 树定位某个值还是很快的，但是也是有缺点的 B 树不利于范围查找，比如上图中我们需要查找 [15，36] 区间的数据，需要访问 1、2、7、3、8、4、9 一共 7 个磁盘块，IO 次数又上去了，范围查找也是我们经常用到的，所以 b 树也不太适合在磁盘中存储需要检索的数据。
1.2.3 B+Tree
B+ 树是 B 树的一种变形形式，B+ 树上的叶子结点存储关键字以及相应记录的地址，叶子结点以上各层作为索引使用。一棵 m 阶的 B+ 树定义如下：
每个结点至多有 m 个子女；
除根结点外，每个结点至少有[m / 2]个子女，根结点至少有两个子女；
有 k 个子女的结点必有 k 个关键字。
B+ 树的查找与 B 树不同，当索引部分某个结点的关键字与所查的关键字相等时，并不停止查找，应继续沿着这个关键字左边的指针向下，一直查到该关键字所在的叶子结点为止。
在 B+Tree 的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的 B+Tree。做这个优化的目的是为了提高区间访问的性能，如果要查询 key 为从 15 到 36 的所有数据记录，当找到 15 后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。
B-Tree 因为非叶子结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而 B+Tree 所有的数据都在叶子结点，每次查找都得到叶子结点。所以在同样高度的 B-Tree 和 B+Tree 中，B-Tree 查找某个关键字的效率更高。B+Tree 所有的数据都在叶子结点，并且结点之间有指针连接，在找大于某个关键字或者小于某个关键字的数据的时候，B+Tree 只需要找到该关键字然后沿着链表遍历就可以了，而 B-Tree 还需要遍历该关键字结点的根结点去搜索。B-Tree 的每个结点都存储主键 + 实际数据，而 B+Tree 非叶子结点只存储关键字信息，而每个页的大小有限是有限的，所以同一页能存储的 B-Tree 的数据会比 B+Tree 存储的更少。这样同样总量的数据，B-Tree 的深度会更大，增大查询时的磁盘 IO 次数，进而影响查询效率。
1.3 索引的管理
1.3.1 索引实现
MyISAM
MyISAM 引擎使用 B+Tree 作为索引结构，叶节点的 data 域存放的是数据记录的地址。下图是 MyISAM 索引的原理图：
这里设表一共有三列，假设我们以 Col1 为主键，则上图是一个 MyISAM 表的主索引(Primary key)示意。可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM 中，主索引和辅助索引(Secondary key)在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。如果我们在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一颗 B+Tree，data 域保存数据记录的地址。因此，MyISAM 中索引检索的算法为首先按照 B+Tree 搜索算法搜索索引，如果指定的 Key 存在，则取出其 data 域的值，然后以 data 域的值为地址，读取相应数据记录。MyISAM 的索引方式也叫做非聚集索引(辅助索引)
InnoDB
虽然 InnoDB 也使用 B+Tree 作为索引结构，但具体实现方式却与 MyISAM 截然不同。第一个重大区别是 InnoDB 的数据文件本身就是索引文件。从上文知道，MyISAM 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在 InnoDB 中，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的 key 是数据表的主键，因此 InnoDB 表数据文件本身就是主索引。
上图是 InnoDB 主索引(同时也是数据文件)的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为 InnoDB 的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键(MyISAM可以没有)，如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为 6 个字节，类型为长整形。第二个与 MyISAM 索引的不同是 InnoDB 的辅助索引 data 域存储相应记录主键的值而不是地址。换句话说，InnoDB 的所有辅助索引都引用主键作为 data 域。下图以英文字符的 ASCII 码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了 InnoDB 的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在 InnoDB 中不是个好主意，因为 InnoDB 数据文件本身是一颗 B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持 B+Tree 的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
1.3.2 索引的操作
创建索引
# 第一种方式，unique 可以省略，如果加上了 unique，表示创建唯一索引。
create [unique] index index_name on tb_name(col_name[(length)]);
# 第二种方式
alter tb_name add [unique] index index_name on (col_name[(length)]);
删除索引
# 索引修改是先删除索引，再重建索引。
drop index index_name on tb_name;
查看索引
show index from tb_name;
1.4 数据检索过程
1.4.1 唯一记录检索
如上图，所有的数据都是唯一的，查询 105 的记录，过程如下：
① 将 P1 页加载到内存
② 在内存中采用二分法查找，可以确定 105 位于[100,150)中间，所以我们需要去加载 100 关联 P4 页
③ 将 P4 加载到内存中，采用二分法找到 105 的记录后退出
1.4.2 查询某个值的所有记录
如上图，查询 105 的所有记录，过程如下：
① 将 P1 页加载到内存
② 在内存中采用二分法查找，可以确定 105 位于[100,150)中间，所以我们需要去加载 100 关联 P4 页
③ 将 P4 加载到内存中，采用二分法找到最有一个小于 105 的记录，即 100，然后通过链表从 100 开始向后访问，找到所有的 105 记录，直到遇到第一个大于 100 的值为止
1.4.3 范围查找
数据如上图，查询[55,150]所有记录，由于页和页之间是双向链表升序结构，页内部的数据是单项升序链表结构，所以只用找到范围的起始值所在的位置，然后通过依靠链表访问两个位置之间所有的数据即可，过程如下：
① 将 P1 页加载到内存
② 内存中采用二分法找到 55 位于 50 关联的 P3 页中，150 位于 P5 页中
③ 将 P3 加载到内存中，采用二分法找到第一个 55 的记录，然后通过链表结构继续向后访问 P3 中的 60、67，当 P3 访问完毕之后，通过 P3 的 nextpage 指针访问下一页 P4 中所有记录，继续遍历 P4 中的所有记录，直到访问到 P5 中所有的 150 为止。
1.4.4 模糊匹配
查询以f开头的所有记录，过程如下：
① 将 P1 数据加载到内存中
② 在 P1 页的记录中采用二分法找到最后一个小于等于 f 的值，这个值是 f，以及第一个大于 f 的，这个值是 z，f 指向叶节点 P3，z 指向叶节点 P6，此时可以断定以f开头的记录可能存在于[P3,P6)这个范围的页内，即 P3、P4、P5 这三个页中
③ 加载 P3 这个页，在内部以二分法找到第一条 f 开头的记录，然后以链表方式继续向后访问 P4、P5 中的记录，即可以找到所有已 f 开头的数据
查询包含f的记录，包含的查询在 sql 中的写法是 %f%，可以看一下上面的数据，f 在每个页中都存在，我们通过 P1 页中的记录是无法判断包含f的记录在那些页的，只能通过 io 的方式加载所有叶子节点，并且遍历所有记录进行过滤，才可以找到包含 f 的记录。以如果使用了 %值% 这种方式，索引对查询是无效的。
最左匹配原则
当 b+ 树的数据项是复合的数据结构，比如(name，age，sex)的时候，b+ 树是按照从左到右的顺序来建立搜索树的，比如当(张三，20，F)这样的数据来检索的时候，b+ 树会优先比较 name 来确定下一步的所搜方向，如果 name 相同再依次比较 age 和 sex，最后得到检索的数据；但当(20，F)这样的没有 name 的数据来的时候，b+ 树就不知道下一步该查哪个节点，因为建立搜索树的时候 name 就是第一个比较因子，必须要先根据 name 来搜索才能知道下一步去哪里查询。比如当(张三，F)这样的数据来检索时，b+ 树可以用 name 来指定搜索方向，但下一个字段 age 的缺失，所以只能把名字等于张三的数据都找到，然后再匹配性别是 F 的数据了， 这个是非常重要的性质，即索引的最左匹配特性。
关注公众号一起学习 Java 开发，跟大家分享我的学习成长过程
本文地址：https://blog.csdn.net/Demo_Null/article/details/107133757