文章目录

一、前言

二、默认索引：B+树索引(重点)

人们谈论索引的时候,如果没有特别指明类型,那多半说的是B+Tree索引(因为大多数MySQL引擎都支持这种索引),它使用Tree数据结构来存储数据。

即使是使用B+树索引，不同存储引擎的实现方式也有所不同：
（1）MyISAM 使用前缀压缩技术使得索引更小,但 InnoDB则按照原数据格式进行存储；
（2）MyISAM 索引通过数据的物理位置引用被索引的行,而 InnoDB则根据主键引用被索引的行。

2.1 数据结构：B树和B+树（非重点，面试问不了这么细）

2.1.1 B树

B树(B tree)是一种平衡的多路查找树,主要面向动态查找,通常用在文件系统中。

2.1.1.1 B树性质

一棵m阶的B树两种情况，要么为空树,要么为满足下列特性的m叉树：
(1)叶子节点：所有的叶子结点都出现在同一层,并且不带信息。叶子结点的双亲称为终端结点;
(2)每个节点：每个结点至多有m棵子树;（金手指：m叉树）
(3)根节点：若根结点不是终端结点,则至少有两棵子树;
(4)非根节点：除根结点之外的所有非终端结点至少有⌈m/2⌉棵子树;
(5)非终端节点(非叶子节点) ：所有的非终端结点都包含以下数据: (n,A0,K1,A1,K2,…,Kn,An)
其中,n(⌈m/2⌉-1≤n≤m-1)为关键码的个数,Ki(1≤i≤n)为关键码,且Ki<K(i+1)(1≤i≤n-1),Ai(0≤i≤n)为指向子树根结点的指针,且指针Ai所指子树中所有结点的关键码均小于K(i+1)大于Ki。
一般情况下,B树的叶子结点可以看做是外部结点(即查找失败)的结点,通常称为外结点。实际上这些结点不存在,指向这些结点的指针为空。所以,B树的叶子可以不画出来。因为叶子都出现在同一层上，所以B树也是树高平衡的。另外,每个结点中关键码的个数为子树的个数减1。
B树是2-3树的推广,2-3树是一个3阶B树。通常B树中的一个结点的大小能够填满一个磁盘页,存储在B树中的指针实际上是包含其孩子结点的块号,每个结点一般允许100个或者更多个孩子。

2.1.1.2 B树查找

B树的查找类似于2-3树的查找,所不同的是B树的每个结点上是多关键码的有序表,在到达某个结点时,先在有序表中查找,若找到,则查找成功;否则,按照指针信息到相应的子树中查找。当到达叶子结点时,则说明树中没有对应的关键码,查找失败。在

B树上的查找过程是一个顺指针查找结点和在结点中查找关键码交叉进行的过程。比如,上图中查找关键码为53的记录。首先,从root指向的根结点a开始,根结点a 中只有一个关键码,且53大于它,因此,按根结点a的指针域A1到结点c去查找,c结点有两个关键码(43、78),而53大于43小于78,应按结点c指针域A1到结点g去查找,在结点g中顺序比较关键码,找到关键码53。

所以,在B树上进行查找包含两种基本操作:
(1)定位节点：在B树中查找结点;
(2)定位节点中的关键码：在结点中查找关键码。
由于B树通常存储在磁盘上,则前一个查找操作(指在B树中查找结点)是在磁盘上进行的,而后一个查找操作(指在结点中查找关键码)是在内存中进行的,即在磁盘上找到某结点后,先将结点的信息读入内存,然后再查找等于k的关键码。显然,在磁盘上进行一次查找比在内存中进行一次查找耗费的时间多得多,因此,在磁盘上进行查找的次数,即待查关键码所在结点在B树的层数,是决定B树查找效率的首要因素。

2.1.1.3 B树插入

B树的插入是2-3树插入的推广

假定要在m阶B树中插入关键码key,设n=m-1,即n为结点中关键码数目的最大值,B树的插入过程如下:

(1)定位:查找插人位置。由于是在终端结点中插入,因此要确定它属于哪个终端结点。定位的结果是返回了key所属终端结点的指针p。若p中的关键码个数小于n,则直接插人关键码key;否则,结点p的关键码个数溢出,执行“分裂一提升”过程。

(2)分裂一提升:将结点p“分裂”成两个结点,分别是p1和p2,把中间的关键码k“提升”到父结点,并且k的左指针指向p1,右指针指向p2。如果父结点的关键码个数也溢出,则继续执行“分裂一提升”过程。显然,这种分裂可能一直上传,如果根结点也分裂了,则树的高度增加了一层。

整个插入过程保证所有的结点至少是半满的。例如,当一个4阶B树的内部结点已满时,将会有5个子女。这个结点分裂成为两个结点,每个结点包含两个关键码,这样就保持了B树的特性。下图给出了在3阶B树中进行插入的示例：

2.1.1.4 B树删除

B树的删除是2-3树删除的推广。

设在m阶B树中删除关键码key。首先要找到key的位置,即“定位”。定位的结果是返回了key所在结点的指针q,假定key是结点q中第i个关键码K,若结点q不是终结点,则用Ai所指的子树中的最小键值x来“替换”Ki。由于x所在结点一定是终端结点,这样,删除问题就归结为在终端结点中删除关键码。
如果终端结点中关键码的个数大于⌈m/2⌉-1,则可直接删除该关键码,如下图：

如果在终端结点中删除一个关键码后其关键码的个数不足⌈m/2⌉-2,则不符合m阶B树的要求,需要从兄弟结点借关键码或合并结点,以保证B树的特性。具体分两种情况：

(1)兄弟够借,查看相邻的兄弟结点,如果兄弟结点有足够多的记录(多于⌈m/2⌉),就从兄弟结点借来一个记录,将借来的关键码“上移”到被删结点的双亲结点中,同时将双亲结点中的相应关键码“下移”到被删结点中。这样做的目的是为了尽可能地延迟由于删除而引起的结点中关键码个数的下溢。

(2)兄弟不够借。如果没有一个兄弟结点可以把记录借给这个记录太少的被删结点,那么被删结点就必须把它的关键码让给一个兄弟结点,即执行“合并”操作,并且从树中把这个空结点删除。兄弟结点当然有空间,因为兄弟结点至多半满,合并后被删结点的双亲少了一个结点,所以要把双亲结点中的一个关键码“下移”到合并结点中。如果被删结点的双亲结点中的关键码的个数没有下溢,则合并过程结束;否则,双亲结点也要进行借关键码或合并结点。显然,合并过程可能会上传到根结点,如果根结点的两个子女合并到一起,则B树就会减少一层。

下图给出了在3阶B树中删除关键码时,出现被删结点中关键码个数发生下溢的情况以及处理示意图。

2.1.2 B+树（性质、插入、删除、查找、范围查找）

B+树是B树的变体，是由B树和索引顺序访问方法(ISAM,Indexed Sequential Access Methed)演变而来，B+树是为磁盘或其他直接存取辅助设备设计的一种平衡查找树。在B+树中，所有记录都是按键值的大小顺序存放在同一层的叶子结点上，由各叶子节点指针进行拼接。

一棵m阶的B+树在结构上与m阶的B树相同,但在关键码的内部安排上有所不同。具体如下:
(1)具有m棵子树的结点含有m个关键码,即每一个关键码对应一棵子树;
(2)关键码K,是它所对应的子树的根结点中的最大(或最小)关键码;
(3)所有的终端结点中包含了全部关键码信息,及指向关键码记录的指针;
(4)各终端结点按关键码的大小次序链在一起,形成单链表,并设置头指针与B_树类似,在B树中,结点内的关键码仍然有序排列,并且对同一结点内的任意两个关键码K和K,若K,<K,则K,小于K,对应的子树中的所有关键码。

与二叉排序树和2-3树最显著的区别是B+树只在终端结点存储记录,内部结点存储关键码,但是这些关键码只是用于引导查找的。这意味着内部结点在结构上与终端结点有显著的区别。内部结点存储关键码用于引导查找,把每个关键码与一个指向子女结点的指针相关联;终端结点存储实际记录,在B+树纯粹作为索引的情况下则存储关键码和指向实际记录的指针。一个B+树的终端结点一般链接起来,形成一个链表,这样,通过访问链表中的所有终端结点,就可以按照排序的顺序遍历全部记录。

例如,下图所示为一棵3阶的B+树,通常在B+树上有两个头指针,一个指向根结点,另一个指向关键码最小的终端结点。因此,可以对B+树进行两种查找操作:一种是从最小关键码起顺序查找,另一种是从根结点开始随机查找。

在B+树上进行随机查找、插入和删除的过程基本上与B树类似。除了查找必须一直到达终端结点外,在一棵B树中的查找几乎与在一棵B树中的查找完全一样。即使在一个内部结点找到了待查找的关键码值,但它只是用来引导索引的,并不提供对实际记录的访问,所以

B+树查找：B+树中查找时,必须到达包含有该关键码值的终端结点。

B+树插入：B+树的插入仅在终端结点上进行,当结点中的关键码个数大于m时要分裂成两个结点,并且它们的双亲结点中应同时包含这两个结点中的最大关键码。

B+树删除：B+树的删除也仅在终端结点上进行,当终端结点中的最大关键码被删除时,其在非终端结点中的值可以作为一个“分界关键码”存在。若因删除而使结点中关键码的个数少于时,和兄弟结点的合并过程和B树类似。

B+树范围查找：B+树特别适合范围查找。一旦找到了范围中的第一个记录,通过顺序处理结点中的其余记录,然后继续下去,尽可能地深入终端结点,就可以找到范围中的全部记录。

B+树查找
先来看一个B+树，其高度为2，每页可存放4条记录，扇出(fan out)为5，如下图。
所有记录都在叶子节点上，并且都是顺序存放的，如果用户从最左边的叶子节点开始顺序遍历，可以得到所有键值的顺序排序：5、10、15、20、25、30、50、55、60、65、70、75、80、85、90。

2.1.3 小结

B树和B+树统称为B树,是需要插入、删除和关键码范围检索的应用程序的标准组织方法,解决了实现基于磁盘的检索时遇到的下列所有问题：
(1)B树总是树高平衡的,所有叶结点都在同一层;
(2)査找、插入和删除等操作只影响最少数量的结点(即磁盘页),因此性能很好;
(3)B树把相关的记录放在同一个磁盘页中,从而利用了访问局部性原理;
(4)B树保证树中至少有一定比例的结点是满的,这样能够改进空间的利用率,同时在查找和更新操作期间减少对磁盘的读取次数。

2.2 索引：B+树索引（重点001）

2.2.1 索引有哪些数据结构？

Hash、B+

大家去设计索引的时候，会发现索引类型是可以选择的。

在这里插入图片描述

2.2.2 B+树数据结构的优势（哈希表、二叉树、平衡二叉树、B树、B+树）？

总问题：从mysql索引考数据结构基础的内容？
回答：从二叉树、平衡二叉树、B树、B+树是一个不断升级的过程，最后选择B+树很合理，但是适用B+树：非叶子节点的检索 + 叶子节点中有序数组的二分法
加上hash表就是：非叶子节点的检索 + 叶子节点中hash数组

2.2.2.1 Hash索引（两个缺点：哈希冲突和不能范围查找）

MySQL默认索引为什么是B+树索引，不是Hash索引？Hash索引两个缺点
缺点1：数据库使用哈希索引，所有字段值所对应的数组下标是哈希算法随机算出来的，所以可能出现哈希冲突。
缺点2：数据库使用哈希索引，只能快速的精确查询 =，但是不支持范围查询 >。

那么对于这样一个索引结构，现在来执行下面的sql语句：

select * from table1 where name='csdn'
复制代码

可以直接对‘csdn’按哈希算法算出来一个数组下标，然后可以直接从数据中取出数据并拿到所对应那一行数据的地址，进而查询那一行数据，那么如果现在执行下面的sql语句：

select * from table1 where name>'csdn'
复制代码

则无能为力，因为哈希表的特点就是可以快速的精确查询，但是不支持范围查询。

如果做成了索引，那速度也是很慢的，要全部扫描。

那Hash表在哪些场景比较适合？
等值查询的场景，就只有KV（Key，Value）的情况，例如Redis、Memcached等这些NoSQL的中间件。

有序数组
你说的是无序的Hash表，那有没有有序的数据结构？
有序数组，它就比较优秀了呀，它在等值查询的和范围查询的时候都很Nice。可以用来做静态存储引擎啊，用来保存静态数据，例如你2019年的支付宝账单，2019年的淘宝购物记录等等都是很合适的，都是不会变动的历史数据。
有序数组缺点：
有序的适合静态数据，因为如果我们新增、删除、修改数据的时候就会改变他的结构。
有序数组底层是一个数组结构（底层数据结构只有两种：数组和链表，树和图是链表变式）你新增一个，那在你新增的位置后面所有的节点都会后移，成本很高。

2.2.2.2 二叉树做索引

第一，二叉树是有序的，所以是支持范围查询的。

2.2.2.3 平衡二叉树做索引

第一，二叉树是有序的，所以是支持范围查询的。
第二，时间复杂度是O(log(N))，为了维持这个时间复杂度，更新的时间复杂度也应该是O(log(N))。

因平衡二叉树做索引，因为索引也不只是在内存里面存储的，还是要落盘持久化的，如果数据多了，树高会很高，查询的成本就会随着树高的增加而增加（金手指：树高一层就要读磁盘一次）。

为了节约成本很多公司的磁盘还是采用的机械硬盘，这样一次千万级别的查询差不多就要10秒了，这谁顶得住啊？

2.2.2.4 用B树做索引

同样的元素，B树的表示要比完全平衡二叉树要“矮”，原因在于B树中的一个节点可以存储多个元素。

B树其实就已经是一个不错的数据结构，用来做索引效果还是不错的。

2.2.2.5 用B+树做索引

存储同样的元素，B+树和B树树高相同，但是，B+树的表示要比B树要“胖”，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。

B+树在结构上相对于B树的不同？
1、B+树中的非叶子节点会冗余一份在叶子节点中
2、叶子节点之间用指针相连

为什么最后选择B+树（二叉树、平衡二叉树、B树、B+树）？囊括各种数据结构的优缺点？ （重点001）
Hash不支持范围查询，
二叉树解决了hash的范围查询问题，但是树高很高，
平衡二叉树解决了二叉树树高的问题，但是每一个节点都只能放一个元素
B树解决了平衡二叉树每一个节点只能放一个元素的问题，一个节点放满足B树定义的多个元素，进一步解决树高的问题，磁盘IO效率提高了，减少访问磁盘的平均次数。
B+树相对于B树，解决树高没有改进，但是结构上有两个变化：
（1）B+树中的非叶子节点会冗余一份在叶子节点中，提高了范围查找的效率，提高了的原因也无非是会有指针指向下一个节点的叶子节点。
（2）叶子节点之间用指针相连。
小结：到这里可以总结出来，Mysql选用B+树这种数据结构作为索引，可以提高查询索引时的磁盘IO效率，并且可以提高范围查询的效率，并且B+树里的元素也是有序的。

2.2.3 附加：B+树中一个节点到底多大合适？ + 操作系统页的概念？

第一，B+树中一个节点到底多大合适？
B+树中一个节点为一页或页的倍数最为合适。
如果一个节点的大小小于1页，比如0.8页，那么读取这个节点的时候其实也会读出1页，造成资源的浪费。
如果一个节点的大小大于1页，比如1.2页，那么读取这个节点的时候会读出2页，也会造成资源的浪费。
所以为了不造成浪费，所以最后把一个节点的大小控制在1页、2页、3页、4页等倍数页大小最为合适。

第二，操作系统，页的概念？
首先Mysql的基本存储结构是页(记录都存在页里边)：

1、页间+页内：各个数据页可以组成一个双向链表，而每个数据页中的记录又可以组成一个单向链表；
2、每个数据页都会为存储在它里面的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录；
3、以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

页的概念？
如果我们写 select * from table1 where website=’csdn’这样没有进行任何优化的sql语句，默认会这样做：
第一，定位到记录所在的页（注意：需要遍历双向链表，找到所在的页，时间复杂度为O(n)，因为各个数据页组成双向链表，使用了B+树索引后，时间复杂度为O(lgN)就可以定位到指定页了）
第二，从所在的页内中查找相应的记录（注意：由于不是根据主键查询，只能遍历所在页的单链表了，因为数据页中的记录组成单链表）
很明显，在数据量很大的情况下这样查找会很慢！看起来跟回表有点点像。

2.2.4 附加：B+树作为索引，特征决定优势(重要)

特征1：B+Tree通常意味着所有的值都是按顺序存储的,并且每一个叶子页到根的距离相同。

特征2：B+Tree索引能够加快访问数据的速度,
B+Tree索引能够加快访问数据的速度,因为存储引擎不再需要进行全表扫描来获取需要的数据,取而代之的是从索引的根节点开始进行搜索，根节点存放了指向子节点的指针,存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点,这些指针实际上定义了的上限和下限。最终存储引擎要么是找到对应的值,要么该记录不存在。

特征3：叶子节点比较特别,它们的指针指向的是被索引的数据,而不是节点页(ps:不同引擎的“指针”类型不同),树的深度和表的大小直接相关。

B+树对索引列是顺序组织存储的,所以很适合查找范围数据。例如,在一个基于文本域的索引树上,按字母顺序传递连续的值进行查找是非常合适的,所以像“找出所有以I到K开头的名字”这样的查找效率会非常高。

请注意,索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。例如，用户表中，两个人的姓和名都一样,则根据他们的出生日期来排列顺序。

可以使用B-Tree索引的查询类型。 B-Tree索引适用于全键值查找、键值范围查找、键前缀查找。其中键前缀查找只适用于根据最左前缀的查找,前面所述的索引对如下类型的查询有效。

全键值查找
全值匹配指的是和索引中的所有列进行匹配,例如前面提到的索引可用干查找姓名为Cuba Allen、出生于1960-01-01的人。

键值范围查找
例如前面提到的索引可用于查找姓在Aen和Barrymore之间的人,这里也只使用了索引的第一列。

匹配最左前缀
前面提到的索引可用于查找所有姓为Alen的人,即只使用索引的第一列。

匹配列前缀
也可以只匹配某一列的值的开头部分,例如前面提到的索引可用于查找所有以J开头的姓的人,这里也只使用了索引的第一列。

精确匹配某一列并范围匹配另外一列
前面提到的索引也可用于查找所有姓为Allen,并且名字是字母K开头(比如Kim、Karl等)的人,即第一列last_name全匹配,第二列first_nane范围匹配。

只访问索引的查询
B-Tree通常可以支持“只访问索引的查询”,即查询只需要访问索引,而无须访问数据行,后面我们将单独讨论这种“覆盖索引”的优化。

因为索引树中的节点是有序的。所以除了按值查找之外,索引还可以用于查询中的ORDER BY操作(按顺序查找),一般来说,如果B-Tree可以按照某种方式查找到值,那么也可以按照这种方式用于排序。所以,如果ORDER BY子句满足前面列出的几种查询类型,则这个索引也可以满足对应的排序需求。

附：一些关于 B-Tree索引的限制
（1）如果不是按照索引的最左列开始查找,则无法使用索引。例如上面例子中的索引无法用于查找名字为Bill的人,也无法查找某个特定生日的人,因为这两列都不是最左数据列。类似地,也无法查找姓氏以某个字母结尾的人；
（2）不能跳过索引中的列,也就是说,前面所述的索引无法用于查找姓为 Smith并且在某个特定日期出生的人,如果不指定名(first_name),则 MySQL只能使用索引的第一列；
（3）如果查询中有某个列的范围查询,则其右边所有列都无法使用索引优化查找。例如有查询
WHERE last name=‘Smith’ AND first_name LIKE ‘J%’ AND dob=1976-12-23,
这个查询只能使用索引的前两列,因为这里LIKE是一个范围条件(但是服务器可以把其余列用于其他目的)。如果范围查询列值的数量有限,那么可以通过使用多个等于条件来代替范围条件。

到这里读者应该可以明白,前面提到的索引列的顺序是多么的重要：这些限制都和索引列的题序有关。

B+树索引四个特征（重点003）

第一，降低树高：
（1）N叉树：B+树是以 N 叉树的形式存在的，树变胖，降低树高；
（2）平衡树：B+树使用平衡二叉树原理，最长程度上降低树高；
（3）B树：B+树一个节点存放多个数据，降低树高。
（4）B+树：从B树到B+树没有降低树高，但是树变胖了，原因在于B+树中的非叶子节点会冗余一份在叶子节点中，并且叶子节点之间用指针相连。
第二，有序：查找数据也不需要全表扫描了，顺着根节点层层往下查找能很快地找到我们的目标数据；
第三，一个节点就是一个磁盘块大小，程序局部性原理的磁盘预读：每个节点的大小即一个磁盘块的大小，一次 IO 会将一个页（每页包含多个磁盘块）的数据都读入（即磁盘预读，程序局部性原理:读到了某个值，很大可能这个值周围的数据也会被用到，干脆一起读入内存）；
第四，叶子节点指针链表连接，将随机IO变成顺序IO，不会再在内存中形成临时表：叶子节点通过指针的相互指向连接，能有效减少顺序遍历时的随机 IO，而且我们也可以看到，叶子节点都是按索引的顺序排序好的，这也意味着根据索引查找或排序都是排序好了的，不会再在内存中形成临时表。

2.3 索引：B+树索引的应用（原理层面：MySQL B+树索引，聚集索引+非聚集索引(二级索引+复合索引)，为什么可以加快检索速度？）（重点002）

1、聚簇索引（where id = 5；主键或唯一键 id）

执行建表语句：

CREATE TABLE `student` (
  `id` BIGINT UNSIGNED AUTO_INCREMENT NOT NULL COMMENT '主键id',
  `student_no` VARCHAR(64) COMMENT '学号',
  `name` VARCHAR(64) COMMENT '学生姓名',
  `age` INT COMMENT '学生年龄',
  PRIMARY KEY (`id`)      // 主键id,无逻辑意义字段
) ENGINE=InnoDB CHARSET=utf8mb4 COMMENT='学生信息表';
复制代码

插入 5 条数据：

insert into student(student_no,name,age) values(101,"Alice",18);  
insert into student(student_no,name,age) values(102,"Bob",19);
insert into student(student_no,name,age) values(104,"Brandt",15);
insert into student(student_no,name,age) values(105,"David",19);
insert into student(student_no,name,age) values(109,"David",18);
复制代码

在插入的过程中，MySQL 会用你指定的主键，在这里是递增主键，维护起一棵 B+树，我用了旧金山大学做的 BPlusTree Visualization 来模拟这棵树的样子，主键从 1 开始递增，插入五条，所以是 1 到 5：

在这里插入图片描述

注意：在你还没有执行 create index 语句的时候，MySQL 就已经创建索引了。

B+树在插入的过程中是怎么维护它的几个特性的：
1、B+树插入时保证有序（有序保证范围查找）：左边节点比右边小；
2、B+树插入时保证自平衡（降低树高四措施之一）：左右两边数量趋于相等；
3、B+树插入时保证节点分裂：节点在遇到元素数量超过节点容量时，是如何分裂成两个的，这个也是 MySQL 页分裂的原理。

注意，MySQL 里绝大多数索引都是 B+树，另外有少数情况会使用 Hash索引、R-tree等等，今天只讨论 B+树。

B+树的叶子节点是带有行的全部数据的，如图：
在这里插入图片描述

对于B+树，非叶子节点起到检索作用，叶子节点存放表数据。
非叶子节点的检索中，保证三特性：
左边节点比右边小、
左右两边数量趋于相等、
节点中存放元素数量超过节点容量时，分裂成来给你个节点，因为一个节点大小一个也，所以这也是 MySQL 页分裂的原理
上图中，第一层非叶子节点为3，表示左边小于3，右边大于等于3；
第二层第一个非叶子节点为2，表示左边小于2，右边大于等于2；
第二层第二个非叶子节点为4，表示左边小于4，右边大于等于4

如果没有这棵 B+树，你要根据主键查询，比如

select * from student where id = 5;
复制代码

对不起，数据是无序的，你只能全表扫描，犹如大浪淘沙。

问题：主键不是递增的吗，那不就可以用二分法来查找？
回答：不是的，主键虽然是递增的，但是如果你写入磁盘时，没有去维护有序数组这样一个数据结构（比如你删掉了 4，怎么把 5 往前面挪），那数据在磁盘里依旧是无序的，查找时只能随机查找，而如果你维护了有序数组这样的数据结构，其实也是建了索引，只是建了不一样的数据结构的索引罢了。
1、这颗B+树就是索引，就是索引数据结构，对于B+树，非叶子节点起到检索作用，叶子节点存放表数据。非叶子节点的检索中，保证左边节点比右边小、左右两边数量趋于相等、节点在遇到元素数量超过节点容量时，是如何分裂成两个的，这个也是 MySQL 页分裂的原理
上图中，第一层非叶子节点为3，表示左边小于3，右边大于等于3；
第二层第一个非叶子节点为2，表示左边小于2，右边大于等于2；
第二层第二个非叶子节点为4，表示左边小于4，右边大于等于4
2、使用B+树索引数据结构就直接在B+树上找，不用到整个磁盘上扫描，所以加快了检索效率。
为什么使用索引可以加快检索效率？
3、在create table新建表和insert into插入数据的时候，这颗B+树就已经出来了，B+树索引就已经好了。为什么说在你还没有执行 create index 语句的时候，MySQL 就已经创建了索引（这里指的是创建了聚集索引）？
一句话小结：对于聚集索引，作用于主键/唯一键，新建表和插入数据的时候就创建了，但是其他的，如二级索引，作用于非唯一键，一定要等到使用create index才被创建

现在有了这棵 B+树，数据被有规律的存储起来，查找 id=5，也不再大浪淘沙，而是变得很有章法：

1、从上到下，先找到 3，5 比它大，找右节点

2、接着找到 4，发现 5 还是比它大，继续找右节点

3、这次到达叶子节点了，叶子节点是一个递增的数组，那就用二分法，找到 id=5 的数据

小结：B+树检索+二分法检索递增数组，先用B+树检索直到叶子节点（一定要到叶子节点，因为具体表数据一定存放在叶子节点，非叶子节点只是检索之用），然后叶子节点是一个递增的数组，那就用二分法。
所以，你要访问磁盘的次数，是由这棵树的层数决定的，每一次具体检索访问磁盘的次数，就是叶子节点所在层数。

如果你没有指定主键呢？没关系，唯一键也可以。

连唯一键也没有？也没关系，mysql会给你建一个rowid字段，用它来组织这棵 B+树.

反正 MySQL 就一个目的，数据要有规律的存储起来，就像之前在数据库是什么里说的，数据是否被规律的管理起来，是数据库和文件系统区分开来的重要因素。

小结：关于聚集索引
1、如果创建表的时候指定一个列为primarykey，就用这个列做聚集索引；
2、如果创建表的时候没有使用primarykey指定主键，表中有唯一键unique key也可以做聚集索引；
3、如果表没有主键primary key和唯一键unique key，mysql会给你建一个rowid字段做聚集索引，用它来组织这棵 B+树.
所以，mysql中任何一个表中有且仅有一个聚集索引（MySQL中任何一个表都一定存在一个聚集索引，也一个表也仅仅只有一个聚集索引，底层就是有且仅有一个聚集索引树，叶子节点是一个存储有完整行数据的索引）。

聚集索引局限：
聚集索引只能加快主键检索/唯一键检索，对于非唯一键，无能为力，比如姓名。

2、二级索引（where name = “David”；非唯一键 name）

聚簇索引只能帮你加快主键查询，但是如果你想根据姓名查询呢？

对不起，看看上面这棵树你就知道，数据并没有按照姓名进行组织，所以，你还是只能全表扫描。

不想全表扫描，怎么办？那就给姓名字段也加个索引，让数据按照姓名有规律的进行组织：

create index idx_name on student(name);   // 执行create index这一句的时候，就创建一个在student表的name字段上的B+树索引，索引被命名为 idx_name 。
复制代码

这时候 MySQL 又会建一棵新的 B+树（注意，和上面聚集索引的B+树不是同一个）：

在这里插入图片描述

你会发现这棵树的叶子节点，只有姓名和主键ID两个字段，没有行的完整数据，这时候你执行：

select * from student where name = "David";
复制代码

MySQL 到你刚刚创建的这棵 B+树查询，快速查到有两条姓名是“David”的记录，并且拿到它们的主键，分别是 4 和 5，但是你要的是select *呀，怎么办？

别忘了，MySQL 在一开始就给你建了一棵 B+树了，把这两棵树，放在一起，拿着从这棵树上查到的两个主键ID，去聚簇索引找，事情不就解决了？

在这里插入图片描述

小结，这种叶子节点不带行数据完整信息的索引，就叫二级索引（secondary index），也叫辅助索引。

key：判断聚集索引的和二级索引的依据：
1、聚集索引是根据唯一键/主键找到完整行信息，二级索引是根据非唯一键找到唯一键/主键。
2、聚集索引叶子节点存放完整行信息，二级索引叶子节点存放非完整行信息，即唯一键/主键。
3、聚集索引非叶子节点存放主键/唯一键作为检索，比较法则是int比较；二级索引非叶子节点存放非唯一键作为检索，比较法则是字母序，一般是字符串类型。
4、联系：聚集索引在where id=xxx;的时候单独使用，二级索引在where name = “David”;的时候先根据非唯一键找到唯一键/主键，然后根据唯一键/主键找到完整行信息。

3、复合索引（where name = “David” and age = 18；非唯一键name + 非唯一键age）

需求：根据姓名和年龄同时查询呢？

select * from student where name = "David" and age = 18;
复制代码

还是那个道理，数据虽然按照 name 有规律的组织了，但是没有按照 age 有规律组织，所以我们要给 name 和 age 同时建索引：

create index idx_name_age on student(name,age);   //创建一个同时在student表中的name字段和age字段上的索引，命名为idx_name_age，因为同时在两个字段上，所以被称为复合索引，其实就是一种两字段的二级索引，还是二级索引，所以还是要使用create index创建，还是一颗B+树。
复制代码

只要是非聚集索引，就都要使用create index创建，二级索引和复合索引（不仅仅在一个字段上）都要使用create index创建。

金手指：聚集索引和二级索引的联系？
因为同时在两个字段上，所以被称为复合索引，其实就是一种两字段的二级索引，还是二级索引，所以还是要使用create index创建，还是一颗B+树。

这时候 MySQL 又会建一棵 B+树，这下 B+树的节点里面，不只有 name，还有 age 了：

在这里插入图片描述

金手指：聚集索引和二级索引的联系？
上面说了，复合索引，其实就是一种两字段的二级索引，还是二级索引，所以还是先根据非唯一键找到唯一键/主键，然后根据唯一键/主键找到完整行信息。

注意观察我用红色虚线框出来的那两个节点，这是这棵树和上面那棵只给 name 建索引的树的唯一区别，两个元素换了个位，因为排序时，是先用 name 比较大小，如果 name 相同，则用 age 比较。

还是那句话，这里举的例子数据量很少，你可以想象下有一万个叫“David”的学生，年龄随机分布在 13 到 20 之间，这时候如果没有按照 age 进行有规律的存储，你还是得扫描一万行数据。

三、其他索引：哈希索引、全文索引

3.1 哈希索引

3.1.1 哈希索引

哈希索引( hash index)基于哈希表实现,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码( hash code),哈希码是个较小的值,并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在素引中,同时在哈希表中保存指向每个数据行的指针。

在 MySQL中,只有 Memory引擎显式支持哈希索引,这也是 Memory引擎表的默认索引类型, Memory引擎同时也支持 B-Tree索引,值得一提的是, Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。
下面来看一个例子。假设有如下表

create table testhash (
   fname varchar(50)  NOT NULL,
   lname varchar(50)  NOT NULL,
   key using hash(fname)
)engine = memory;
复制代码

注意，在MySQL中，只有Memory引擎显示支持哈希索引，也是默认索引类型。所以我们这里将testhash表的engine设置为Memory，就是使用了哈希索引。

在这里插入图片描述
假设索引使用假想的哈希函数f(),它返回下面的值(都是示例数据,非真实数据)：

f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458
复制代码

则哈希索引的数据结构如下：

注意每个槽的编号是顺序的,但是数据行不是。现在,来看如下查询：

MySQL先计算’Peter’的哈希值,并使用该值寻找对应的记录指针,因为f(‘Peter’)= 8784,所以 MySQL在索引中查找8784,可以找到指向第3行的指针,最后一步是比较第三行的值是否为 ‘Peter’,以确保就是要查找的行。

因为索引自身只需存储对应的哈希值,所以索引的结构十分紧凑,这也让哈希索引查找的速度非常快。然而,哈希索引也有它的限制。

附：哈希散列的限制 ·
（1）哈希索引只包含哈希值和行指针,而不存储字段值,所以不能使用索引中的值来避免读取行。不过,访问内存中的行的速度很快,所以大部分情况下这一点对性能的影响并不明显。
（2）哈希索引数据并不是按照索引值顺序存储的,所以也就无法用于排序。
（3）哈希索引也不支持部分索引列匹配查询，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列(A,B)上建立哈希索引，如果查询只有数据列A，则无法使用该索引。
（4）哈希索引只支持等值比较查询,包括=、IN()、<=>，也不支持任何范围查询,例如 WHERE price>100。
（5）访问哈希索引的数据非常快,除非有很多哈希冲突(不同的索引列值却有相同的哈希值)，当出现哈希冲突的时候,存储引擎必须遍历链表中所有的行指针,逐行进行比较,直到找到所有符合条件的行。
（6）如果哈希冲突很多的话,一些索引维护操作的代价也会很高。例如,如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引,那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行,找到并删除对应行的引用，冲突越多，代价越大。

因为这些限制,哈希索引只适用于某些特定的场合。而一旦适合哈希索引,则它带来的性能提升将非常显著,举个例子,在数据仓库应用中有一种经典的“星型” schema,需要关联很多查找表,哈希索引就非常适合查找表的需求。

自适应哈希索引
InnoDB引擎有一个特殊的功能叫做“自适应哈希索引( adaptive hash index)”,当 InnoDB注意到某些索引值被使用得非常频繁时,它会在内存中基于B-Tree索引之上再创建一个哈希索引,这样就让B-Tree索引也具有哈希索引的一些优点,比如快速的哈希查找。这是一个完全自动的,内部的行为,用户无法控制或者配置,不过如果有必要,完全可以关闭该功能。

创建自定义哈希索引：如果存储引擎不支持哈希索引,则可以模拟像InnoDB一样创建哈希索引,这可以享受一些哈希索引的便利,例如只需要很小的索引就可以为超长的键创建索引。

思路很简单：在B-Tree基础上创建一个伪哈希索引,这和真正的哈希索引不是一回事, 因为还是使用B-Tree进行查找,但是它使用哈希值而不是键本身进行索引查找,你需要做的就是在查询的WHERE子句中手动指定使用哈希函数。

下面是一个实例,例如需要存储大量的URL,井需要根据URL进行搜索查找,如果使用B-Tree来存储URL,存储的内容就会很大,因为URL本身都很长,正常情况下会有如下查询:

mysql> select id FROM url WHERE url="http://www.baidu.com";
复制代码

若删除原来URL列上的索引,而新增一个被索引的url_crc列,使用CRC32做哈希,就可以使用下面的方式查询:

mysql> select id FROM url WHERE url="http://www.baidu.com" AND url_crc=CRC32("http://www.baidu.com");
复制代码

这样做的性能会非常高,因为 MySQL优化器会使用这个选择性很高而体积很小的基于
url_crc列的索引来完成查找(在上面的案例中,索引值为xxxxxx)。即使有多个记录有相同的索引值,查找仍然很快,只需要根据哈希值做快速的整数比数就能找到索引条目,然后一一比较返回对应的行。另外一种方式就是对完整的URL字符串做索引,那样会比较慢。

这样实现的缺陷是需要维护哈希值。可以手动维护,也可以使用触发器实现,下面的案例演示了触发器如何在插入和更新时维护url_crc列,首先创建如下表：

create table pseudohash (
id int unsigned not null auto_increment,
url varchar(255) not null,
url_crc int unsigned not null default 0,
primary key(id)
);
复制代码

然后创建触发器,先临时修改一下语句分隔符,这样就可以在触发器定义中使用分号

create trigger pseudohash_crc_ins before insert on pseudohash 
for each row  begin  set  new.url_crc=crc32(new.url);
end;
复制代码

create trigger pseudohash_crc_upd before update on pseudohash 
for each row begin set new.url_crc=crc32(new.url);
end;
复制代码

剩下的工作就是验证一下触发器如何维护哈希索引

insert into pseudohash (url)  values("http://www.mysql.com");
select * from pseudohash;
复制代码

update pseudohash set url = 'http://www.mysql.com/' where id = 1;
select * from pseudohash;
复制代码

如果采用这种方式,记住不要使用SHA1()和MD5()作为哈希函数,因为这两个函数计算出来的哈希值是非常长的字符串,会浪费大量空间,比较时也会更慢。SHA1()和MD5()是强加密函数,设计目标是最大限度消除冲突,但这里并不需要这样高的要求。简单哈希函数的冲突在一个可以接受的范围,同时又能够提供更好的性能。

哈希冲突

如果数据表非常大,CRC32()会出现大量的哈希冲突,则可以考虑自己实现一个简单的64位哈希函数,这个自定义函数要返回整数,而不是字符串。一个简单的办法可以使用MD5()函数返回值的一部分来作为自定义哈希函数。这可能比自己写一个哈希算法的性能要差,不过这样实现最简单：

select conv (right(md5('http://www.mysql.com/'),16),16,10) as HASH64;
复制代码

处理哈希冲突,当使用哈希索引进行查询的时候,必须在WHERE子句中包含常量值：

select id from url where url_crc=CRC32("http://www.mysql.com") and url="http://www.mysql.com";
复制代码

一旦出现哈希冲突,另一个字符串的哈希值也恰好是1560514994,则下面的查询是无法正确工作的。

select id from url where url_crc=CRC32("http://www.mysql.com");
复制代码

因为会出现”生日悖论”，出现哈看冲突的概率的增长速度可能比想象的要快得多.CRC32()返回的是32位的整数,当索引有93000条记录时出现冲突的概率是1%,例如我们将/usr/share/dict/words中的词导入数据表并进行CRC32()计算,最后会有98569行。这就已经出现一次哈希冲突了,冲突让下面的查询返国了多条记录：

select word,crc from words where crc=CRC32('gnu');
复制代码

正确的写法应该如下：

select word,crc from words where crc=CRC32('gnu') and word='gnu';
复制代码

要避免冲突问题,必须在WHERE条件中带入哈希值和对应列值。如果不是想查询具体值,例如只是统计记录数(不精确的),则可以不带入列值,直接使用CRC32()的哈希值查询即可。还可以使用如FMV64()函数作为哈希函数,这是移植自Percona Server的函数,可以以插件的方式在任何MySQL版本中使用,哈希值为64位,速度快,且冲突比CRC32()要少很多。

3.1.2 哈希索引

底层数据结构
B+树索引：使用的数据结构是B+树。
哈希索引：使用的数据结构是哈希表。

哈希索引基本散列表实现，散列表（也称哈希表）是根据关键码值(Key value)而直接进行访问的数据结构，它让码值经过哈希函数的转换映射到散列表对应的位置上，查找效率非常高。假设我们对名字建立了哈希索引，则查找过程如下图所示：

在这里插入图片描述

对于上图的解释：
从上图左边看，对于Mysql中每一行数据，存储引擎都会对所有的索引列（上图左边中的 name 列，值为“张三”、“李四”、“王五”），经过哈希算法（即上图中间的矩形），计算一个哈希码（上图散列表的位置），散列表里的每个元素指向数据行的指针（再次反映了逻辑相邻不是物理存储相邻，B+树索引和哈希索引都是这样）。

哈希索引的优点：

由于索引自身只存储对应的哈希值，所以索引的结构十分紧凑，这让哈希索引查找速度非常快！

哈希表的劣势：

不支持区间查找，不支持排序，

哈希索引的应用：Innodb内存中的自适应哈希索引

由于哈希表不适合范围查找，更多的时候，哈希表是与 B Tree等一起使用的，B+树范围查找 + 哈希表精准查找。在 InnoDB 引擎中就有一种名为「自适应哈希索引」的特殊索引（在Innodb架构的博客中阐述过）。这种自适应哈希索引，当 innoDB 注意到某些索引值使用非常频繁时，就会内存中基于 B-Tree 索引之上再创建哈希索引，这样也就让 B+ 树索引也有了哈希索引的快速查找等优点，这是完全自动，内部的行为，用户无法控制或配置，不过如果有必要，可以关闭该功能。

小结：自适应哈希索引将原来的 “B+树范围查找+叶子节点内二分法查找” 变为 “B+树范围查找+叶子节点内哈希查找”。

伪哈希索引(把基于 url 的字符串索引改成了基于 url_crc 的整型索引)

InnoDB 引擎本身是不支持显式创建哈希索引的，我们可以在 B+ 树的基础上创建一个伪哈希索引，它与真正的哈希索引不是一回事，伪哈希索引是以哈希值而非键本身来进行索引查找的，这种伪哈希索引的使用场景是怎样的呢，假设我们在 db 某张表中有个 url 字段，我们知道每个 url 的长度都很长，如果以 url 这个字段创建索引，无疑要占用很大的存储空间，如果能通过哈希（比如CRC32）把此 url 映射成 4 个字节，再以此哈希值作索引，索引占用无疑大大缩短！不过在查询的时候要记得同时带上 url 和 url_crc,主要是为了避免哈希冲突，导致 url_crc 的值可能一样

SELECT id FROM url WHERE url = "http://www.baidu.com"  AND url_crc = CRC32("http://www.baidu.com")
复制代码

这样做把基于 url 的字符串索引改成了基于 url_crc 的整型索引，效率更高，同时索引占用的空间也大大减少，一举两得，当然人可能会说需要手动维护索引太麻烦了，那可以改进触发器实现。

除了上文说的两个索引，还有空间索引（R-Tree），全文索引等，由生产中不是很常用，这里不作过多阐述

3.2 全文索引

全文索引是一种特殊类型的索引,它查找的是文本中的关键词,而不是直接比较索引中的值。

全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节,如停用词、词干和复数、布尔搜索等,全文索引更类似于搜索引擎做的事情,而不是简单的WHERE条件匹配。

在相同的列上同时创建全文索引和基于值的B-Tree索引不会有冲突,全文索引适用于 MATCH AGAINST操作,而不是普通的WHERE条件操作。

四、面试金手指（重点003）

4.1 使用索引代替全表扫描 + 复合索引列顺序 + 索引在存储引擎层（重点003.1）

金手指：使用索引代替全表扫描
例如：

如果在Dep_id列上建有自定义的二级索引（因为不是主键，不能是聚集索引，只能是二级索引/辅助索引），则 MySQL将使用该索引找到Dep_id为5的行，具体地， **MySQL先在索引上按Dep_id值进行查找,找到主键Emp_id,然后回表,使用聚集索引，找到整个行记录信息。**如果是复合索引，索引包含多个列,那么列的顺序也十分重要,因为MySQL只能高效地使用索引的最左前缀列。其次，创建一个包含两个列的索引,和创建两个只包含一列的索引是大不相间的,下面将详细介绍。

问题：复合索引 对于复合索引，复合索引中的列的顺序重要？
回答：一句话解释，索引的最左前缀匹配原则。

问题ORM：如果使用的是ORM,是否还需要关心索引?
回答:是的,仍然需要关心索引,即使是使用对象美系映射(ORM)工具也要关心索引。
ORM工具能够生产符合逻辑的,合法的查询(多数时候),除非只是生成非常基本的查询(例如仅是根据主键查询),否则它很难生成适合索引的查询。无论是多么复杂的ORM工具,在精妙和复杂的索引面前都是”浮云”。很多时候,即使是查询优化技术专家也很难兼顾到各种情况,更别说ORM了。

架构方面，拉高逼格：在 MySQL中,索引是在存储引擎层而不是服务层实现的
在 MySQL中,索引是在存储引擎层而不是服务层实现的（mysql架构分为两层：mysql服务层和存储引擎层）。
第一，因为索引依赖存储引擎层的，所以不同从存储引擎提供不同的索引标准，并没有统一的索引标准:不同存储引擎的索引的工作方式并不一样,也不是所有的存储引擎都支持所有类型的索引。
第二，即使多个存储引擎支持同一种类型的索引,其底层数据结构的实现也可能不同。常用的索引有三种：B+树索引、哈希索引、全文索引。
即使是使用B+树索引，不同存储引擎的实现方式也有所不同：
（1）MyISAM 使用前缀压缩技术使得索引更小,但 InnoDB则按照原数据格式进行存储；
（2）MyISAM 索引通过数据的物理位置引用被索引的行,而 InnoDB则根据主键引用被索引的行。

4.2 索引，逻辑相邻不一定物理相邻（重点003.2）

因为索引，所以逻辑上相邻的记录在磁盘上也并不是一定物理相邻的
数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用 B 树及其变种 B+树。
在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。

上图展示了一种可能的索引方式。左边是数据表，一共有两列七条记录，最左边的是数据记录的物理地址（金手指：注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的）。为了加快 Col2 的查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针，这样就可以运用二叉查找在 O(log2n)的复杂度内获取到相应数据。

附加：MySQL中的聚集索引为什么一个表只允许有一个？

MySQL中的聚集索引为什么只允许有一个？
MySQL中的InnoDB引擎中，设计的时候聚集索引为什么只允许有一个。多个聚集索引，除了内存占有会多以外，还有更新会有异常外，还有什么影响吗？
书中写到，数据页只能按照一颗B+数进行排序，所以只能有一个B+树？这个怎么去理解？
回答：
聚集索引结构：聚集索引就是一个B+树，非叶子节点用户检索，叶子节点中存放索引和数据，所以，聚集索引是索引和数据的组合体（这就是聚集索引的结构） 。
聚集索引两个功能：1、非叶子节点快速检索，决定了数据的顺序；2、叶子节点中存储数据行
第一，从索引上说，非叶子节点快速检索，决定了数据的顺序：聚集索引cluster index 底层表示的是一个表的实际存储顺序，必然只有一个（即全班同学要集合排队了，不能同时按照个子高低和考试成绩排序，总得选一样，主键和唯一键都可以做聚集索引）。（2）如果你复制该表的数据再次按照另一种顺序（即另一个cluster index）存储一遍，那就是另一个表了。
第二，从数据行上说，叶节点中存放数据行：如果有两个或者多个聚集索引，数据行会重复存储，浪费磁盘空间，也没那个必要。
在实际中，聚集索引的主键与业务无关，目的是便于顺序读写，减少随机读写的io开销。

4.3 五个问题一套：索引优点、索引缺点、什么列上设置索引、什么列上不设置索引、根据表的大小选择索引还是全表扫描（重点003.3）

第一，索引的五个优点
第一，检索，可以大大加快数据的检索速度，这也是创建索引的最主要的原因(金手指：加快检索速度是创建索引的最大原因，是索引的最大优势)。
第二，聚集索引，将随机IO变为顺序IO；
第三，排序和分组，帮助服务器避免排序和临时表，使用分组group by和排序子句order by进行数据检索时，同样可以显著减少查询中分组和排序的时间。
第四，唯一性索引，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
第五，表与表连接，数据完整性：可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。

解释索引三重要的优点（即上面索引的前三个优点）：
索引三个作用
1、索引可以减少扫描行数，加快检索速度。
2、索引可以帮助服务器避免排序和临时表，sql语句中使用orderby，优化排序。
3、索引可以将随机 IO 变成顺序 IO，从而加快检索速度。
第一作用，索引可以减少扫描行数
当我们要在新华字典里查某个字（如「先」）具体含义的时候，通常都会拿起一本新华字典来查，你可以先从头到尾查询每一页是否有「先」这个字，这样做（对应数据库中的全表扫描）确实能找到，但效率无疑是非常低下的，更高效的方相信大家也都知道，就是在首页的索引里先查找「先」对应的页数，然后直接跳到相应的页面查找，这样查询时候大大减少了，可以为是 O(1)。
数据库中的索引也是类似的，通过索引定位到要读取的页，大大减少了需要扫描的行数，将全表扫描变为页扫描，B+树中一个节点就是一个页，B+树叶子节点中是递增的，使用二分法就可以找到，能极大的提升效率。
总问题：索引第一个优点：MySQL B+树索引，聚集索引+非聚集索引(二级索引+复合索引)，为什么可以加快检索速度？
回答：不建立索引，数据是无序的，要全表扫描，就是全磁盘扫描，建立索引，你要访问磁盘的次数，是由这棵树的层数决定的，每一次具体检索访问磁盘的次数，就是叶子节点所在层数（步骤：B+树检索+二分法检索递增数组，先用B+树检索直到叶子节点（一定要到叶子节点，因为具体表数据一定存放在叶子节点，非叶子节点只是检索之用），然后叶子节点是一个递增的数组，那就用二分法）
小问题：为什么不建立索引要全表扫描，全磁盘扫描，主键有序啊？
一句话小结：逻辑有序不是物理存储有序。
解释：主键虽然是递增的，但是如果你写入磁盘时，没有去维护有序数组这样一个数据结构（比如你删掉了 4，怎么把 5 往前面挪），那数据在磁盘里依旧是无序的，查找时只能随机查找，而如果你维护了有序数组这样的数据结构，其实也是建了索引，只是建了不一样的数据结构的索引罢了。
第二作用，索引优化order by，避免再次排序生成临时表
假设我们不用索引，试想运行如下语句
SELECT * FROM user order by age desc; // 这个sql语句中使用到了orderby，可以使用索引优化
（1）在不是使用索引的情况下，则 MySQL 的流程是这样的，扫描所有行，把所有行加载到内存后，再按 age 排序生成一张临时表，再把这表排序后将相应行返回给客户端，更糟的，如果这张临时表的大小大于 tmp_table_size 的值（默认为 16 M），内存临时表会转为磁盘临时表，性能会更差。
（2）在使用索引的情况下，如果在age字段上加了索引，索引本身是有序的，所以从磁盘读的行数本身就是按 age 排序好的，也就不会生成临时表，就不用再额外排序，无疑提升了性能。
关于避免排序生成临时表？
不使用索引，age是没有排序的，只有id排序了，需要按 age 排序生成一张临时表；
在age字段上加上二级索引，create index idx_age on user(age)，会得到一个age的B+树，是排序好的，即避免排列了。
第三作用，索引可以将随机 IO 变成顺序 IO
再来看随机 IO 和顺序 IO。先来解释下这两个概念。
相信不少人应该吃过旋转火锅，服务员把一盘盘的菜放在旋转传输带上，然后等到这些菜转到我们面前，我们就可以拿到菜了，假设装一圈需要 4 分钟，则最短等待时间是 0（即菜就在你跟前），最长等待时间是 4 分钟（菜刚好在你跟前错过），那么平均等待时间即为 2 分钟，假设我们现在要拿四盘菜，这四盘菜随机分配在传输带上，则可知拿到这四盘菜的平均等待时间是 8 分钟（随机 IO），如果这四盘菜刚好紧邻着排在一起，则等待时间只需 2 分钟（顺序 IO）。
随机IO:到磁盘上拿四个页面，平均来看，拿一个页面需要2分钟，拿四个页面需要8分钟。
顺序IO:到磁盘上拿四个页面，平均来看，拿一个页面需要2分钟，但是四个页面顺序放在一起，找到第一个页面两分钟后，剩余三个就在后面，直接拿下来就好了。
上述中传输带就类比磁道，磁道上的菜就类比扇区（sector）中的信息，磁盘块（block）是由多个相邻的扇区组成的，扇区是操作系统读取的最小单元，如果信息能以 block 的形式聚集在一起（程序的局部性原理），就能极大减少磁盘 IO 时间,这就是顺序 IO 带来的性能提升，下文中我们将会看到 B+ 树索引就起到这样的作用。

如上图示：多个扇区sectors组成了一个块block，如果要读的信息都在这个块 block 中，则只需一次 IO 读
而如果信息在一个磁道中分散地分布在各个扇区中，或者分布在不同磁道的扇区上（寻道时间是随机IO主要瓶颈所在），将会造成随机 IO，影响性能。
我们来看一下一个随机 IO 的时间分布：

seek Time: 寻道时间，磁头移动到扇区所在的磁道，注意，磁道是从内到外，一圈一圈的在磁盘上。
Rotational Latency：完成步骤 1 后，磁头移动到同一磁道扇区对应的位置所需求时间
Transfer Time 从磁盘读取信息传入内存时间
这其中寻道时间占据了绝大多数的时间（大概占据随机 IO 时间的占 40%），所以我们的突破口就在减少寻道时间。
随机 IO 和顺序 IO 大概相差百倍 (随机 IO：10 ms/ page, 顺序 IO 0.1ms / page)，可见顺序 IO 性能之高，索引带来的性能提升显而易见！

第二，索引的三个缺点
第一，创建索引和维护索引要耗费时间，这种时间随着数据量的增加而增加。
第二，因为索引的存在，增加了数据库的存储空间，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
第三，当对表中的数据进行增加、删除和修改的时候，要花费较多的时间，因为索引也要随之变动，也要动态的维护，这样就降低了数据的维护速度。
小结：
索引加快了检索，但是减慢了增加、删除和修改（但是这三个操作的检索过程是加快的了）；
对于已经添加了索引的字段，从之前的“数据”变为“数据+索引”，占用了额外的物理空间。

第三，六个列上应该创建索引
索引是建立在数据库表中的某些列的上面。在创建索引的时候，应该考虑在哪些列上可以创建索引，在哪些列上不能创建索引。一般来说，应该在这些列上创建索引：
1、搜索where having（第一作用，检索速度+聚集索引顺序IO） ：在经常需要搜索的列上，可以加快搜索的速度；where having
2、等值条件判断where having （检索速度） ：在经常使用在 WHERE 子句中的列上面创建索引，加快条件的判断速度。
3、范围查找where having （检索速度） ：在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；
4、静态：唯一性列和排列规则（第三四作用，排序分组临时表、唯一性） ：在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；
5、动态：排序order by（检索速度） ：在经常需要排序的列上创建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；order by
6、连接join on（第五作用，表连接，数据完整性） ：在经常用在连接的列上，这些列主要是一些外键，可以加快连接的速度；join on

第四，有些列不应该创建索引
一般来说，不应该创建索引的的这些列具有下列特点：
第一，静态：数据量少，数据行少：对于那些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。金手指：加索引，最大优点加快检索速度无法覆盖增加的物理空间。
第二，静态：blob text image bit：对于那些定义为blob text, image 和 bit 数据类型的列不应该增加索引。这是因为，这些列的单个数据量要么相当大，要么取值很少。
第三，动态：查询少：对于那些在查询中很少使用或者参考的列不应该创建索引。
这是因为，既然这些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。金手指：这些列查询的少，索引的优化效率无法覆盖增加的物理空间。
第四，动态：修改多，当修改性能远远大于检索性能时，不应该创建索引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因此，当修改性能远远大于检索性能时，不应该创建索引。金手指：加索引，最大优点加快检索速度无法覆盖增加删除修改的减慢。

小结，第三第四就是索引列的应用法则：（就是索引的最大优点和两个缺点的取舍，最大优先是加快检索速度，两个缺点是增加物理空间 + 添加修改删除操作变慢）

第六，金手指：应用方案：根据表的大小选择索引还是全表扫描
对于非常小的表,大部分情况下简单的全表扫描更高效。
对于中到大型的表,索引就非常有效。
**对于特大型的表,建立和使用索引的代价将随之增长。**则需要一种技术可以直接区分出查询需要的一组数据,而不是一条记录一条记录地匹配,例如可以便用分区战术。
**对于表的数量种多,可以建立一个元数据信息表,用来查询需要用到的某些特性。**例如执行那些需要聚合多个应用分布在多个表的数据的查询,则需要记录“哪个用户的信息存储在哪个表中”的元数据,这样在查询时就可以直接忽略那些不包含指定用户信息的表。对于大型系统,这是一个常用的技巧,对于TB级别的数据,定位单条记录的意义不大,所以经常会使块级别元数据技术来替代索引。

4.4 实践：高效索引设计法则(避免索引失效 4点 +设计好的索引 6点)（重点003.4）

4.4.1 避免索引失效 4点

公式、数据类型转换、编码类型转换、select *

避免索引失效
加了索引却不生效可能会有以下几种原因
1、公式，索引列是表示式的一部分，或是函数的一部分，导致索引失效
如下 SQL：
SELECT book_id FROM BOOK WHERE book_id + 1 = 5;
或者
SELECT book_id FROM BOOK WHERE TO_DAYS(CURRENT_DATE) – TO_DAYS(gmt_create) <= 10
上述两个 SQL 虽然在列 book_id 和 gmt_create 设置了索引，但由于它们是表达式或函数的一部分，导致索引无法生效，最终导致全表扫描。
2、数据类型转换，隐式类型转换，导致索引失效
假设有以下表:
CREATE TABLE tradelog (
id int(11) NOT NULL,
tradeid varchar(32) DEFAULT NULL,
operator int(11) DEFAULT NULL,
t_modified datetime DEFAULT NULL,
PRIMARY KEY (id),
KEY tradeid (tradeid),
KEY t_modified (t_modified)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;
执行 SQL 语句
SELECT * FROM tradelog WHERE tradeid=110717;
交易编号 tradeid 上有索引，但用 EXPLAIN 执行却发现使用了全表扫描，为啥呢，tradeId 的类型是 varchar(32), 而此 SQL 用 tradeid 一个数字类型进行比较，发生了隐形转换，会隐式地将字符串转成整型，如下:
mysql> SELECT * FROM tradelog WHERE CAST(tradid AS signed int) = 110717;
这样也就触发了上文中第一条的规则，即：索引列不能是函数的一部分。
3、数据编码转换，隐式编码转换，导致索引失效
这种情况非常隐蔽，来看下这个例子
CREATE TABLE tradelog (
id int(11) NOT NULL,
tradeid varchar(32) DEFAULT NULL,
operator int(11) DEFAULT NULL,
t_modified datetime DEFAULT NULL,
PRIMARY KEY (id),
KEY tradeid (tradeid),
KEY t_modified (t_modified)
) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4; // utf8mb4
CREATE TABLE trade_detail (
id int(11) NOT NULL,
tradeid varchar(32) DEFAULT NULL,
trade_step int(11) DEFAULT NULL, /操作步骤/
step_info varchar(32) DEFAULT NULL, /步骤信息/
PRIMARY KEY (id), KEY tradeid (tradeid)
) ENGINE=InnoDB DEFAULT CHARSET=utf8; // utf8
trade_defail 是交易详情， tradelog 是操作此交易详情的记录，现在要查询 id=2 的交易的所有操作步骤信息，则我们会采用如下方式
SELECT d.* FROM tradelog l, trade_detail d WHERE d.tradeid=l.tradeid AND l.id=2;
由于 tradelog 与 trade_detail 这两个表的字符集不同，且 tradelog 的字符集是 utf8mb4，而 trade_detail 字符集是 utf8, utf8mb4 是 utf8 的超集，所以会自动将 utf8 转成 utf8mb4。即上述语句会发生如下转换:
SELECT d.* FROM tradelog l, trade_detail d WHERE (CONVERT(d.traideid USING utf8mb4)))=l.tradeid AND l.id=2;
自然也就触发了「索引列不能是函数的一部分」这条规则。
两种解决方式
第一种方案当然是把两个表的字符集改成一样，如果业务量比较大，生产上不方便改的话，还有一种方案是把 utf8mb4 转成 utf8，如下
mysql> SELECT d.* FROM tradelog l , trade_detail d WHERE d.tradeid=CONVERT(l.tradeid USING utf8) AND l.id=2;
这样索引列就生效了。
4、select * ，使用 select * 造成的全表扫描
SELECT * FROM user ORDER BY age DESC
上述语句在 age 上加了索引，但依然造成了全表扫描，这是因为我们使用了 SELECT *,导致回表查询，MySQL 认为回表的代价比全表扫描更大，所以不选择使用索引，如果想使用到 age 的索引，我们可以用覆盖索引来代替:
SELECT age FROM user ORDER BY age DESC
或者加上 limit 的条件（数据比较小）
SELECT * FROM user ORDER BY age DESC limit 10
这样就能利用到索引。

问题：无法避免对索引列使用函数，怎么使用索引
上面说了，索引列是表示式的一部分，或是函数的一部分，索引不会生效。
但是，有时候我们无法避免对索引列使用函数，但这样做会导致全表索引，是否有更好的方式呢。
比如我现在就是想记录 2016 ~ 2018 所有年份 7月份的交易记录总数
mysql> SELECT count( ) FROM tradelog WHERE month(t_modified)=7;
由于索引列 t_modified是函数的参数，所以显然无法用到索引，我们可以将它改造成基本字段区间的查找如下
SELECT count( ) FROM tradelog WHERE
-> (t_modified >= ‘2016-7-1’ AND t_modified<‘2016-8-1’) or
-> (t_modified >= ‘2017-7-1’ AND t_modified<‘2017-8-1’) or
-> (t_modified >= ‘2018-7-1’ AND t_modified<‘2018-8-1’);

4.4.2 设计好的索引 6点

第五，金手指：如何在需要索引的列上设置索引（常见索引原则）
1. 静态：索引列选择 2条。尽量使用数据量少的索引；尽量选择区分度高的列作为索引，区分度的公式是 COUNT(DISTINCT col)/COUNT(*)，区分度表示字段不重复的比率，比率越大我们扫描的记录数就越少。
2. 动态：重要的字段才索引 3条。做法：为经常作为查询条件的字段建立索引；为经常需要排序、分组和联合操作的字段建立索引；避免带函数的查询参与索引（索引列不能参与计算，保持列“干净”，比如，带函数的查询不参与索引。FROM_UNIXTIME(create_time)=‘2016-06-06’ 就不能使用索引，原因很简单，B+树中存储的都是数据表中的字段值，但是进行检索时，需要把所有元素都应用函数才能比较，显然这样的代价太大。所以语句要写成：create_time=UNIX_TIMESTAMP(‘2016-06-06’)）。
3. 选择唯一性索引 1条。做法：唯一性索引的值是唯一的，可以更快速的通过该索引来确定某条记录。
4. 限制索引的数目 2条。理由：越多的索引，会使更新表变得很浪费时间。做法：删除不再使用或者很少使用的索引；尽量的扩展索引，不要新建索引（比如表中已经有了a的索引，现在要加（a,b）的索引，那么只需要修改原来的索引即可）。
5. 限制索引长度 1条。理由：如果索引的值很长，那么查询的速度会受到影响。做法：尽量使用前缀来索引，如果索引字段的值很长，最好使用值的前缀来索引；最左前缀匹配原则，非常重要的原则【（1）适用于二级索引和复合索引；（2）MySQL会一直向右匹配直到遇到范围查询（>,<,BETWEEN,LIKE）就停止匹配。】。
6.最后一点，不要依赖合并索引机制：单个多列组合索引和多个单列索引的检索查询效果不同，虽然存在合并索引（金手指：“合并索引”就是使用多个单列索引，然后将这些结果用“union或者and”来合并起来），但是最好还是不要依赖mysql内部的合并索引机制，还是应该建立起比较好的索引。

4.5 底层：三类索引(唯一索引、主键索引、聚集索引) + InnoDB架构，changebuffer与唯一索引（重点003.5）

三种索引：唯一索引、主键索引和聚集索引
根据数据库的功能，可以在数据库设计器中创建三种索引：唯一索引、主键索引和聚集索引。
第一，唯一索引
唯一索引是不允许其中任何两行具有相同索引值的索引。
当现有数据中存在重复的键值时，大多数数据库不允许将新创建的唯一索引与表一起保存。数据库还可能防止添加将在表中创建重复键值的新数据。例如，如果在 employee 表中职员的姓(lname)上创建了唯一索引，则任何两个员工都不能同姓，这是荒唐的。
第二，主键索引
数据库表经常有一列或列组合，其值唯一标识表中的每一行。该列称为表的主键。在数据库关系图中为表定义主键将自动创建主键索引，主键索引是唯一索引的特定类型。该索引要求主键中的每个值都唯一。当在查询中使用主键索引时，它还允许对数据的快速访问。
第三，聚集索引
在聚集索引中，表中行的物理顺序与键值的逻辑（索引）顺序相同。一个表只能包含一个聚集索引。如果某索引不是聚集索引，则表中行的物理顺序与键值的逻辑顺序不匹配。与非聚集索引相比，聚集索引通常提供更快的数据访问速度。
局部性原理与磁盘预读
由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘 I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。
由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此
对于具有局部性的程序来说，预读可以提高 I/O 效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为 4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
B+树索引的性能分析
上文说过一般使用磁盘 I/O 次数评价索引结构的优劣。先从 B-Tree 分析，根据B-Tree 的定义，可知检索一次最多需要访问 h 个节点。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次 I/O 就可以完全载入。为了达到这个目的，在实际实现 B-Tree 还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个 node 只需一次I/O。
B-Tree 中一次检索最多需要 h-1 次 I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度 d 是非常大的数字，通常超过 100，因此 h 非常小（通常不超过 3）。
而红黑树这种结构，h 明显要深的多。由于逻辑上很近的节点（父子）物理上可能很远，无法利用局部性，所以红黑树的 I/O 渐进复杂度也为 O(h)，效率明显比B-Tree 差很多。
综上所述，用 B-Tree 作为索引结构效率是非常高的。

change buffer与唯一索引（changebuffer减少磁盘IO + merge + changebuffer局限）
change buffer：减少磁盘IO
更新一个数据页时，如果数据页在内存中就直接更新，而如果这个数据页还没有在内存中的话，在不影响数据一致性的前提下，InooDB会将这些更新SQL缓存在change buffer中，这样就不需要从磁盘中读入这个数据页了。在下次查询需要访问这个数据页的时候，将数据页读入内存，然后执行change buffer中与这个页有关的操作，通过这种方式就能保证这个数据逻辑的正确性。
ps：change buffer在内存中有拷贝，也会被写入到磁盘上
merge
将change buffer中的操作应用到原数据页，得到最新结果的过程称为merge。除了访问这个数据页会触发merge外，系统有后台线程会定期merge
changebuffer局限
唯一索引不能使用change buffer：唯一索引来说，所有的更新操作都要先判断这个操作是否违反唯一性约束，要判断表中是否存在这个数据，而这必须要将数据页读入内存才能判断，如果都已经读入到内存了，那直接更新内存会更快，就没必要使用change buffer了。

【索引】你怎么看到为表格定义的所有索引？
索引是通过以下方式为表格定义的：
SHOW INDEX FROM

【索引】可以使用多少列创建索引？
任何标准表最多可以创建 16 个索引列。

4.6 复合索引：回表、覆盖索引、索引下推(程序员能够控制的是覆盖索引)（重点003.6）

问题：回表和覆盖索引是什么关系？（要记忆的东西）
回表是一个二级索引存在的问题，先找到主键，然后找到记录行信息。
覆盖索引是解决回表，怎么解决的，
对于二级索引idx_name，select id from student where idx_name = ?，就不回表了；
对于联合索引idx_name_age，select id,age from student where idx_name = ?，就不回表了。看上面的图二级索引和复合索引的图就知道。所以说，很多联合索引的建立，就是为了支持覆盖索引，避免回表，毕竟，mysql可能因为回表，不选择某一个索引，查看explain。

4.6.1 存在的问题：回表

回表的概念？
回表大概就是我们有个主键为ID的索引，和一个普通name字段的索引，我们在普通字段上搜索：
sql select * from table where name = ‘csdn’
执行的流程：
第一，先查询到name索引上的“csdn”，然后找到他的id是2；
第二，去主键索引，找到id为2对应的值。
其中，第二个过程，回到主键索引树搜索的过程，就是回表。不过也有方法避免回表，那就是覆盖索引。

4.6.2 回表的解决1：覆盖索引

覆盖索引？覆盖索引如何避免回表？
这个其实比较好理解，刚才我们是 select * ，查询所有的，如果只查询ID列，其实在Name字段的索引上就已经有了，那就不需要回表了。所以，好的覆盖索引设计出来就是为了减少回表，毕竟，mysql可能因为回表，不选择某一个索引，查看explain。
覆盖索引可以减少树的搜索次数，提升性能，他也是我们在实际开发过程中经常用来优化查询效率的手段。
很多联合索引的建立，就是为了支持覆盖索引，特定的业务能极大的提升效率。

4.6.3 回表的解决2：索引下推

索引下推减少回表次数
假设有联合索引(a,b,c)。有以下SQL语句：
select * from itemcenter where a like ‘aa%’ and b=22 and c = 20;
根据左侧匹配规则，只能用到”a”检索数据，bc两个字段无法用到，在MySQL 5.6之前，只能一个个回表，到主键索引上找出数据行，再对比b、c字段值。
而MySQL 5.6 引入的索引下推优化（index condition pushdown)，可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

4.7 复合索引：最左匹配和前缀匹配

问题1：最左匹配和前缀匹配是什么关系？
回答1：最左匹配是数据库底层已经存在的，无法改变的匹配原则，前缀匹配是对于长字符串字段的匹配方式，利用了最左匹配的原理。
问题2：为什么最左匹配适用于二级索引和复合索引，前缀匹配也适用于二级索引和复合索引？
回答2：最左匹配是数据库底层既有的匹配原则，所以自然适用于二级索引和复合索引，而前缀匹配是一个调优方式，利用了最左匹配原则，所以自然也适用于二级索引和复合索引。

4.7.1 底层原理：最左匹配(适用：二级索引+复合索引)

索引的最左匹配原则知道么？
最左匹配原则：
1、适用范围：二级索引和联合索引（集聚索引直接用主键/唯一键，不需要最左匹配了）。
索引可以简单如一个列 (a)，也可以复杂如多个列 (a,b,c,d)，无论是二级索引和联合索引，即无论是单列索引还是多列索引，最左匹配原则都适用。
2、如果是联合索引，那么key也由多个列组成，同时，索引只能用于查找key是否存在（相等），遇到范围查询 (>、<、between、like左匹配)等就不能进一步匹配了，后续退化为线性查找。因此，联合索引中，列的排列顺序决定了可命中索引的列数。
例子（解释遇到范围查询就不能进一步匹配了，后续退化为线性查找）：
如有索引 (a,b,c,d)，查询条件 a=1 and b=2 and c>3 and d=4，则会在每个节点依次命中a、b、c，无法命中d。(c已经是范围查询了，d肯定是排不了序了)
问题：为什么复合索引中的列的顺序重要？
回答：一句话解释，索引的最左前缀匹配原则。
金手指：最左匹配在复合索引中的应用
只给 student 表建 idx_name_age 这个复合索引，这两个 sql 语句，会走索引吗？
select * from student where name = “David”; 走idx_name_age复合索引
select * from student where age = 18; 不走idx_name_age复合索引，走全表扫描

4.7.2 实践调优：前缀索引(适用：二级索引+复合索引)

长字符串字段的hash？
因为存在一个磁盘占用的问题，索引选取的越长，占用的磁盘空间就越大，相同的数据页能放下的索引值就越少，搜索的效率也就会越低。
方案是：hash，把字段hash为另外一个字段存起来，使用hash后的字段作为索引，每次校验hash就好了，hash的索引也不大

前缀索引
数据库索引的最左匹配原则才是最底层的
1、二级索引长字符串：因为有了最左匹配原则，所以对于长字符串字段，既需要有好的检索效率，又需要小的存放空间，这两者的平衡点就是索引选择性，所以产生了前缀索引；
2、二级索引长字符串前缀相同：在长字符串字段的中，前缀相同怎么办（实际：身份证号码、学号、工号、邮箱等），前面三个，数据库中倒序存储这些前缀相同的号码，邮箱，去掉www开始检索；
3、联合索引联合索引中哪个索引放前面，索引选择性说了算，根本依据还是最左匹配原则（联合索引表示不仅仅一个字段，是二级索引的扩展）
1、前缀索引基本使用：长字符串字段的克星，索引选择性
之前我们说过，如于长字符串的字段（如 url），我们可以用伪哈希索引的形式来创建索引，以避免索引变得既大又慢，除此之外其实还可以用前缀索引（字符串的部分字符）的形式来达到我们的目的，那么这个前缀索引应该如何选取呢，这叫涉及到一个叫索引选择性的概念
索引选择性定义：不重复的索引值（也称为基数，cardinality）和数据表的记录总数的比值，比值越高，代表索引的选择性越好，唯一索引的选择性是最好的，比值是 1。
画外音：我们可以通过 SHOW INDEXES FROM table 来查看每个索引 cardinality 的值以评估索引设计的合理性
怎么选择这个比例呢，我们可以分别取前 3，4，5，6，7 的前缀索引，然后再比较下选择这几个前缀索引的选择性，执行以下语句
SELECT
COUNT(DISTINCT LEFT(city,3))/COUNT( ) as sel3,
COUNT(DISTINCT LEFT(city,4))/COUNT( ) as sel4,
COUNT(DISTINCT LEFT(city,5))/COUNT( ) as sel5,
COUNT(DISTINCT LEFT(city,6))/COUNT( ) as sel6,
COUNT(DISTINCT LEFT(city,7))/COUNT( ) as sel7
FROM city_demo
得结果如下
sel3 sel4 sel5 sel6 sel7
0.0239 0.0293 0.0305 0.0309 0.0310
可以看到当前缀长度为 7 时，索引选择性提升的比例已经很小了，也就是说应该选择 city 的前六个字符作为前缀索引，如下
ALTER TABLE city_demo ADD KEY(city(6)) // 为city_demo表添加一个索引，用city前6个字段做索引
我们当前是以平均选择性为指标的，有时候这样是不够的，还得考虑最坏情况下的选择性，以这个 demo 为例，可能一些人看到选择 4，5 的前缀索引与选择 6，7 的选择性相差不大，那就得看下选择 4，5 的前缀索引分布是否均匀了
SELECT COUNT( ) AS cnt, LEFT(city, 4) AS pref FROM city_demo
GROUP BY pref
ORDER BY cnt DESC LIMIT 5
可能会出现以下结果
cnt pref
305 Sant
200 Toul
90 Chic
20 Chan
可以看到分布极不均匀，以 Sant，Toul 为前缀索引的数量极多，这两者的选择性都不是很理想，所以要选择前缀索引时也要考虑最差的选择性的情况。
前缀索引虽然能实现索引占用空间小且快的效果，但它也有明显的弱点，MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY ，而且也无法使用前缀索引做覆盖扫描，前缀索引也有可能增加扫描行数。
解释，假设有以下表数据及要执行的 SQL
id email
1 zhangssxyz@163.com
2 zhangs1@163.com
3 zhangs1@163.com
4 zhangs1@163.com
SELECT id,email FROM user WHERE email=’ zhangssxyz@xxx.com’;
如果我们针对 email 设置的是整个字段的索引，则上表中根据「 zhangssxyz@163.com」查询到相关记记录后,再查询此记录的下一条记录，发现没有，停止扫描，此时可知只扫描一行记录，如果我们以前六个字符（即 email(6)）作为前缀索引，则显然要扫描四行记录，并且获得行记录后不得不回到主键索引再判断 email 字段的值，所以使用前缀索引要评估它带来的这些开销。
2、问题：索引设计，前缀索引进阶使用：前缀相同怎么办（实际：身份证号码、学号、工号、邮箱等），前面三个，数据库中倒序存储这些前缀相同的号码，邮箱，去掉www开始检索
如果前缀基本都是相同的该怎么办，比如现在我们为某市的市民建立一个人口信息表，则这个市人口的身份证虽然不同，但身份证前面的几位数都是相同的，这种情况该怎么建立前缀索引呢。
一种方式就是我们上文说的，针对身份证建立哈希索引，另一种方式比较巧妙，将身份证倒序存储，查的时候可以按如下方式查询:
SELECT field_list FROM t WHERE id_card = reverse(‘input_id_card_string’);
mysql中倒序存储身份证号码到t表中的id_card字段，所以，输入值input_id_card_string需要倒序，然后和数据库表中的id_card字段比较
这样就可以用身份证的后六位作前缀索引了，是不是很巧妙
小结：相同前缀如何处理？
提高区分度，比如身份证号，倒序存储在数据库中，邮箱账号，所有人都是www开头，可以截取后再存到数据库。
3、问题：联合索引，联合索引中哪个索引放前面，索引选择性说了算，根本依据还是最左匹配原则（联合索引表示不仅仅一个字段，是二级索引的扩展）
索引选择性同样适用于联合索引的设计，如果没有特殊情况，我们一般建议在建立联合索引时，把选择性最高的列放在最前面，比如，对于以下语句：
SELECT * FROM payment WHERE staff_id = xxx AND customer_id = xxx;
单就这个语句而言， (staff_id，customer_id) 和 (customer_id, staff_id) 这两个联合索引我们应该建哪一个呢，可以统计下这两者的选择性。
SELECT
COUNT(DISTINCT staff_id)/COUNT( ) as staff_id_selectivity,
COUNT(DISTINCT customer_id)/COUNT( ) as customer_id_selectivity,
COUNT( )
FROM payment
结果为: ;
staff_id_selectivity: 0.0001
customer_id_selectivity: 0.0373
COUNT( ): 16049
从中可以看出 customer_id 的选择性更高，所以应该选择 customer_id 作为第一列。
create index idx_customer_staff on student(customer_id,staff_id);

4.8 索引设计准则：经验法则和三星索引(重点：彻底理解三星索引，能够设计出尽量满足三星的好的索引，面试重点，考察索引设计能力)

上文我们得出了一个索引列顺序的经验法则：将选择性最高的列放在索引的最前列，这种建立在某些场景可能有用，但通常不如避免随机 IO 和排序那么重要，这里引入索引设计中非常著名的一个准则：三星索引。

如果一个查询满足三星索引中三颗星的所有索引条件，理论上可以认为我们设计的索引是最好的索引。

什么是三星索引
第一颗星：where子句，WHERE子句后面参与查询的列可以组成了单列索引或联合索引
第二颗星：order by 避免排序，即如果 SQL 语句中出现 order by colulmn，那么取出的结果集就已经是按照 column 排序好的，不需要再生成临时表
第三颗星：select 避免回表查询，SELECT 对应的列应该尽量是索引列，即尽量避免回表查询（上面就出现过，因为回表查询，mysql没有选择索引而是走全表扫描，避免回表两操作：新建覆盖索引和索引下推，程序员能控制的就是新建覆盖索引）。

所以对于如下语句:

SELECT age, name, city where age = xxx and name = xxx order by age
复制代码

设计的索引应该是 (age, name,city) 或者 (name, age,city)

设计的索引应该是 (age, name,city) 或者 (name, age,city) 复合索引要有顺序，最左匹配，where和order by city没用，放在最后面
where 子句：where后面的 age name 放到索引里面
order by 子句：age 放到索引里面
select 子句，避免回表：age name city 要都在复合索引里面，这样就不用回表到聚集索引中找了

当然了三星索引是一个比较理想化的标准，实际操作往往只能满足期望中的一颗或两颗星，考虑如下语句:

SELECT age, name, city where age >= 10 AND age <= 20 and city = xxx order by name desc
复制代码

假设我们分别为这三列建了联合索引，则显然它符合第三颗星（使用了覆盖索引），如果索引是（city, age, name)，则虽然满足了第一颗星，但排序无法用到索引，不满足第二颗星，如果索引是 (city, name, age)，则第二颗星满足了，但此时 age 在 WHERE 中的搜索条件又无法满足第一星，

另外第三颗星（尽量使用覆盖索引）也无法完全满足，试想我要 SELECT 多列，要把这多列都设置为联合索引吗，这对索引的维护是个问题，因为每一次表的 CURD 都伴随着索引的更新，很可能频繁伴随着页分裂与页合并。

综上所述，三星索引只是给我们构建索引提供了一个参考，索引设计应该尽量靠近三星索引的标准，但实际场景我们一般无法同时满足三星索引，一般我们会优先选择满足第三颗星（因为回表代价较大）至于第一，二颗星就要依赖于实际的成本及实际的业务场景考虑。

where 子句：where后面的 age city 放到索引里面
order by 子句：name 放到索引里面
select 子句，避免回表：age name city 要都在复合索引里面，这样就不用回表到聚集索引中找了
三星索引设计：
如果索引是（city, age, name)，则虽然满足了第一颗星age city，但排序name无法用到索引，不满足第二颗星；
如果索引是（city, name, age)，则第二颗星name满足了，但此时 age 在 WHERE 中的搜索条件又无法满足第一星，