磁盘里的数据页结构

数据页组成双向链表，一页里面的数据行组成单向链表，根据主键id从小到大排序，每个数据页都对应一个页目录，页目录里面存储的主键id和槽位的关系。
一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值，否则会进行页分裂

给所有的页建立一个目录项

由于数据页的编号可能并不是连续的， 所以在表中插入许多条记录后， 可能是这样的效果

这些16KB的页在物理存储上可能并不挨着， 所以如果想从这么多页中根据主键值快速定位某些记录所在的页， 需要给它们做个目录， 每个页对应一个目录项，每个目录项包括下边两个部分：

1. 页的用户记录中最小的主键值， 用key来表示。
2. 页号， 用page_no表示。
   

上述方式就实现了简易版的索引方案

InnoDB中的索引方案

InnoDB复用了之前存储用户记录的数据页来存储目录项， 为了和用户记录做一下区分， 把这些用来表示目录项的记录称为目录项记录。在记录头信息(数据结构里的行格式)里的record_type属性， 它的各个取值代表的意思如下：
0： 普通的用户记录
1： 目录项记录
2： 最小记录
3： 最大记录
上述简易方案更改为:
分配了一个编号为30的页来专门存储目录项记录。 目录项记录的record_type值是1， 而普通用户记录的record_type值是0。
目录项记录只有主键值和页的编号两个列， 而普通的用户记录的列是用户自己定义的， 可能包含很多列， 另外还有InnoDB自己添加的隐藏列。

现在以查找主键为20的记录为例， 根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

1. 先到存储目录项记录的页， 也就是页30中通过二分法快速定位到对应目录项， 因为12 < 20 < 209， 所以定位到对应的记录所在的页就是页9。
2. 再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录

   B+树

   如果表中的数据非常多则会产生很多存储目录项记录的页， InnoDB会 为这些存储目录项记录的页再生成一个更高级的目录，这就是构成了一颗B+树， 就像是一个多级目录一样， 大目录里嵌套小目录， 小目录里才是实际的数据， 所以现在各个页的示意图就是这样子：
   规定最下边的那层， 也就是存放我们用户记录的那层为第0层， 之后依次往上加。
   
   
   如图， 生成了一个存储更高级目录项的页33， 这个页中的两条记录分别代表页30和页32， 如果用户记录的主键值在[1, 320)之间， 则到页30中查找更详细的目录项记录， 如果主键值不小于320的话， 就到页32中查找更详细的目录项记录。

不论是存放用户记录的数据页， 还是存放目录项记录的数据页， 都把它们存放到B+树这个数据结构中了， 所以也称这些数据页为节点。 从图中可以看出来， 实际用户记录其实都存放在B+树的最底层的节点上， 这些节点也被称为叶子节点或叶节点， 其余用来存放目录项的节点称为非叶子节点或者内节点， 其中B+树最上边的那个节点也称为根节点。

聚簇索引

B+树本身就是一个目录， 或者说本身就是一个索引。 它有两个特点：

1. 使用记录主键值的大小进行记录和页的排序， 这包括三个方面的含义：
   1. 页内的记录是按照主键的大小顺序排成一个单向链表。
   2. 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
   3. 存放目录项记录的页分为不同的层次， 在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
2. B+树的叶子节点存储的是完整的用户记录。所谓完整的用户记录， 就是指这个记录中存储了所有列的值（包括隐藏列） 。

把具有这两种特性的B+树称为聚簇索引， 所有完整的用户记录都存放在这个聚簇索引的叶子节点处。简而言之，如果一颗大的B+树索引数据结构里，叶子节点就是数据页自己本身，那么此时我们就可以称这颗B+树索引为聚簇索引，这种聚簇索引并不需要我们在MySQL语句中显式的使用INDEX语句去创建 ， InnoDB存储引擎会自动的创建聚簇索引。

二级索引

主键之外的索引都叫二级索引。
为了让新插入记录能找到自己在那个页里， 需要保证在B+树的同一层内节点的目录项记录除页号这个字段以外是唯一的。 所以对于二级索引的内节点的目录项记录的内容，实际上是由三个部分构成的：

• 索引列的值
• 主键值
• 页号

也就是把主键值也添加到二级索引内节点中的目录项记录了， 这样就能保证B+树每一层节点中各条目录项记录除页号这个字段外是唯一的，

单字段二级索引

二级索引和聚簇索引的原理是一样的，也是一颗b+树，区别是叶子节点虽然是数据页，但存放的是索引字段值+主键（目的是保证内节点中目录项记录的唯一性 ），即key是索引字段值+主键，value是数据页地址，查询数据的时候先根据索引字段二分法往下找，从数据页，找到了主键id，再回表（后面有)，根据主键id从主键的聚簇索引里面去找到这条数据

多字段二级索引

索引字段是两个或者多个也是一样的道理，数据页存储的是主键id+索引1+索引2
联合索引的运行原理也是一样的，只不过是建立一颗独立的B+树，叶子节点的数据页里放了id+字段1+字段2，然后默认按照字段1排序，字段1一样就按照字段2排序，不同数据页之间的字段1+字段2值的排序也如此。

总结

innodb存储引擎的索引的完整实现原理了，也没那么难，不过就是建立B+树，根据B+树一层一层二分查找罢了，然后不同的索引就是建立不同的B+树，然后你增删改的时候，一方面在数据页里更新数据，一方面就是维护你所有的索引

B+树的形成

每当为某个表创建一个B+树索引（聚簇索引不是人为创建的， 默认就有） 的时候， 都会为这个索引创建一个根节点页面。 最开始表中没有数据的时候， 每个B+树索引对应的根节点中既没有用户记录， 也没有目录项记录。

1. 随后向表中插入用户记录时， 先把用户记录存储到这个根节点中。
2. 当根节点中的可用空间用完时继续插入记录， 此时会将根节点中的所有记录复制到一个新分配的页， 比如页a中， 然后对这个新页进行页分裂的操作， 得到另一个新页， 比如页b。 这时新插入的记录根据键值（也就是聚簇索引中的主键值， 二级索引中对应的索引列的值） 的大小就会被分配到页a或者页b中， 而根节点便升级为存储目录项记录的页。
3. 这个过程需要大家特别注意的是： 一个B+树索引的根节点自诞生之日起， 便不会再移动。 这样只要对某个表建立一个索引， 那么它的根节点的页号便会被记录到某个地方， 然后凡是InnoDB存储引擎需要用到这个索引的时候， 都会从那个固定的地方取出根节点的页号， 从而来访问这个索引。(这个存储某个索引的根节点在哪个页面中的信息就是传说中的数据字典中的一项信息 )

   回表

   根据二级索引的值查找到完整的用户记录的话， 仍然需要到聚簇索引中再查一遍， 这个过程也被称为回表。

• 案例

CREATE TABLE index_demo( c1 INT PRIMARY KEY,, c2 INT,c3 CHAR(1),KEY(c2) ) ROW_FORMAT = Compact;
指定c2列为索引列，c1列为主键，MySQL会根据c2列创建一棵B+树

现在想通过c2列的值查找某些记录的话就可以使用刚刚建好的这个B+树了。 以查找c2列的值为4的记录为例， 查找过程如下：

1. 确定目录项记录页根据根页面， 也就是页44， 可以快速定位到目录项记录所在的页为页42（因为2 < 4 < 9） 。
2. 通过目录项记录页确定用户记录真实所在的页。在页42中可以快速定位到实际存储用户记录的页， 但是由于c2列并没有唯一性约束， 所以c2列值为4的记录可能分布在多个数据页中， 又因为2 < 4 ≤ 4， 所以确定实际存储用户记录的页在页34和页35中。
3. 在真实存储用户记录的页中定位到具体的记录。到页34和页35中定位到具体的记录。
4. 但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键） 两个列， 所以必须再根据主键值去聚簇索引中再查找一遍完整的用户记录（这就是回表）

   列的基数

   列的基数指的是某一列中不重复数据的个数， 比方说某个列包含值2, 5, 8, 2, 5, 8, 2, 5, 8， 虽然有9条记录， 但该列的基数却是3。 也就是说， 在记录行数一定的情况下， 列的基数越大， 该列中的值越分散， 列的基数越小， 该列中的值越集中。 这个列的基数指标非常重要， 直接影响我们是否能有效的利用索引。 假设某个列的基数为1， 也就是所有记录在该列中的值都一样， 那为该列建立索引是没有用的， 因为所有值都一样就无法排序， 无法进行快速查找了， 而且如果某个建立了二级索引的列的重复值特别多， 那么使用这个二级索引查出的记录还可能要做回表操作， 这样性能损耗就更大了。 所以结论就是： 最好为那些列的基数大的列建立索引， 为基数太小列的建立索引效果可能不好。

   数据字典

   实际上是为了更好的管理我们这些用户数据而不得已引入的一些额外数据， 这些数据也称为元数据。 InnoDB存储引擎特意定义了一些列的内部系
   统表（internal systemtable） 来记录这些这些元数据：

这些系统表也被称为数据字典， 它们都是以B+树的形式保存在系统表空间的某些页面中， 其中SYS_TABLES、 SYS_COLUMNS、 SYS_INDEXES、 SYS_FIELDS这四个表尤其重要， 称之为基本系统表（basic systemtables）

索引设计注意事项

1. 只为用于搜索、 排序或分组的列创建索引
2. 考虑列的基数，最好为那些列的基数大的列建立索引， 为基数太小列的建立索引效果可能不好
3. 索引列的类型尽量小

• 数据类型越小， 在查询时进行的比较操作越快
• 数据类型越小， 索引占用的存储空间就越少， 在一个数据页内就可以放下更多的记录， 从而减少磁盘I/O带来的性能损耗， 也就意味着可以把更多的数据页缓存在内存中， 从而加快读写效率。

1. 让主键具有AUTO_INCREMENT， 让存储引擎自己为表生成主键， 而不是我们手动插入
2. where条件里面不要函数和计算
3. where，order by，group by最左匹配联合索引
4. 避免冗余和重复索引
5. 只索引字符串值的前缀的策略

• 案例

一个字符串其实是由若干个字符组成， 如果我们在MySQL中使用utf8字符集去存储字符串的话， 编码一个字符需要占用1~3个字节。 假设我们的字符串很长，那存储一个字符串就需要占用很大的存储空间。 在我们需要为这个字符串列建立索引时， 那就意味着在对应的B+树中有这么两个问题：

1. B+树索引中的记录需要把该列的完整字符串存储起来， 而且字符串越长， 在索引中占用的存储空间越大。
2. 如果B+树索引中索引列存储的字符串很长， 那在做字符串比较时会占用更多的时间。

只对字符串的前几个字符进行索引也就是说在二级索引的记录中只保留字符串前几个字符。 这样在查找记录时虽然不能精确的定位到记录的位置， 但是能定位到相应前缀所在的位置， 然后根据前缀相同的记录的主键值回表查询完整的字符串值， 再对比就好了。
这样只在B+树中存储字符串的前几个字符的编码， 既节约空间， 又减少了字符串的比较时间， 还大概能解决排序的问题， 何乐而不为， 比方说
我们在建表语句中只对name列的前10个字符进行索引可以这么写：
CREATE TABLE person_info(name VARCHAR(100) NOT NULL,birthday DATE NOT NULL,phone_number CHAR(11) NOT NULL,country varchar(100) NOT NULL,KEY idx_name_birthday_phone_number (name(10), birthday, phone_number));
name(10)就表示在建立的B+树索引中只保留记录的前10个字符的编码， 这种只索引字符串值的前缀的策略是我们非常鼓励的， 尤其是在字符串类型能存储的字符比较多的时候。

常见问题

索引的好处

你可以直接根据某个字段的索引B+树来查找数据，不需要全表搜索，性能提升是很高的。

索引的不足

空间：
每个索引都是一棵b+树，每一棵b+树都要占用磁盘空间，索引太多，耗费磁盘空间。

时间：
需要维护各个索引的有序性，数据页内的有序性，索引页的有序性，不停的增删改，必然导致数据在页之间的移动，不停的增加索引页。如果索引太多，必然导致增删改的速度就下降了。查询速度是提高了，但是增删改的速度下降了，因此，不建议一个表里搞太多的索引。

联合索引的好处

设计系统的时候一般都是设计联合索引，很少用单个字段做索引，(每个索引都会建一个B+树)要尽可能的让索引数量少一些，避免磁盘占用太多，增删改性能太差。

联合索引全值匹配的原理

涉及到了一个索引使用的规则，那就是你发起的SQL语句里，where条件里的几个字段都是基于等值来查询，都是用的等于号！
而且where条件里的几个字段的名称和顺序也跟你的联合索引一模一样！此时就是等值匹配规则，上面的SQL语句是百分百可以用联合索引来查询的。

1. 首先到索引页里去找，索引页里有多个数据页的最小值记录，此时直接在索引页里基于二分查找法来找就可以了，直接可以定位到他所在的数据页
2. 然后在数据页内部用户记录本身也是一个单向链表，你也是直接就做二分查找就可以了(见数据结构数据页Page Directory)，先按第一个字段的值来找，你会发现几条数据都是一样的，此时就可以按照第二个字段来二分查找，此时会发现多条数据都是一样的，接着就按照第三个字段来二分查找。
3. 对于联合索引而言，在数据页里面就是依次按照各个字段来进行二分查找，先定位到第一个字段对应的值在哪个页里，然后如果第一个字段有多条数据值都一样，就根据第二个字段来找，以此类推，一定可以定位到某条或者某几条数据！

   索引使用规则

   等值匹配规则

   就是你where语句中的几个字段名称和联合索引的字段完全一样，而且都是基于等号的等值匹配，那百分百会用上我们的索引，这个大家是没有问题的，即使你where语句里写的字段的顺序和联合索引里的字段顺序不一致，也没关系，MySQL会自动优化为按联合索引的字段顺序去找。

   最左侧列匹配

   假设我们联合索引是KEY(class_name, student_name, subject_name)，那么不一定必须要在where语句里根据三个字段来查，其实只要根据最左侧的部分字段来查，也是可以的。
   比如你可以写select * from student_score where class_name='' and student_name=''，就查某个学生所有科目的成绩，这都是没有问题的。
   但是假设你写一个select * from student_score where subject_name=''，那就不行了，因为联合索引的B+树里，是必须先按class_name查，再按student_name查，不能跳过前面两个字段，直接按最后一个subject_name查的。
   另外，假设你写一个select * from student_score where class_name='' and subject_name=''，那么只有class_name的值可以在索引里搜索，剩下的subject_name是没法在索引里找的，道理同上。
   所以在建立索引的过程中，你必须考虑好联合索引字段的顺序，以及你平时写SQL的时候要按哪几个字段来查。

   最左前缀匹配原则

   如果你要用like语法来查，比如select * from student_score where class_name like '1%'，查找所有1打头的班级的分数，那么也是可以用到索引的。因为你的联合索引的B+树里，都是按照class_name排序的，所以你要是给出class_name的确定的最左前缀就是1，然后后面的给一个模糊匹配符号，那也是可以基于索引来查找的，这是没问题的。
   但是你如果写class_name like '%班'，在左侧用一个模糊匹配符，那他就没法用索引了，因为不知道你最左前缀是什么

   范围查找规则

   我们可以用select * from student_score where class_name>'1班' and class_name<'5班'这样的语句来范围查找某几个班级的分数。这个时候也是会用到索引的，因为我们的索引的最下层的数据页都是按顺序组成双向链表的，所以完全可以先找到’1班’对应的数据页，再找到’5班’对应的数据页，两个数据页中间的那些数据页，就全都是在你范围内的数据了！
   但是如果你要是写select * from student_score where class_name>'1班' and class_name<'5班' and student_name>''，这里只有class_name是可以基于索引来找的，student_name的范围查询是没法用到索引的！
   这也是一条规则，就是你的where语句里如果有范围查询，那只有对联合索引里最左侧的列进行范围查询才能用到索引！

   等值匹配+范围匹配的规则

   如果你要是用select * from student_score where class_name='1班' and student_name>'' and subject_name<''，那么此时你首先可以用class_name在索引里精准定位到一波数据，接着这波数据里的student_name都是按照顺序排列的，所以student_name>''也会基于索引来查找，但是接下来的subject_name<''是不能用索引的。
   所以综上所述，一般我们如果写SQL语句，都是用联合索引的最左侧的多个字段来进行等值匹配+范围搜索，或者是基于最左侧的部分字段来进行最左前缀模糊匹配，或者基于最左侧字段来进行范围搜索，这就要写符合规则的SQL语句，才能用上我们建立好的联合索引！

   排序的时候怎么样才能使用上索引

   为什么排序要使用索引

   排序不用索引的话，把一堆数据放到一个临时磁盘文件里，然后直接硬上各种排序算法在磁盘文件里搞一通排序，接着按照你指定的要求走limit语句拿到指定分页的数据，速度会非常的慢。

   怎么使用索引

   SQL语句里，应该尽量最好是按照联合索引的字段顺序去进行order by排序，这样就可以直接利用联合索引树里的数据有序性，到索引树里直接按照字段值的顺序去获取你需要的数据了。

• 案例：

按照xx1,xx2,xx3三个字段来进行排序，在联合索引的索引树里都排序好了，直接就按照索引树里的顺序，把xx1,xx2,xx3三个字段按照从小到大的值获取前面100条就可以了。然后拿到100条数据的主键再去聚簇索引里回表查询剩余所有的字段。
所以说，在你的SQL语句里，应该尽量最好是按照联合索引的字段顺序去进行order by排序，这样就可以直接利用联合索引树里的数据有序性，到索引树里直接按照字段值的顺序去获取你需要的数据了。

限定规则

1. 多字段的排序方向一致

因为联合索引里的字段值在索引树里都是从小到大依次排列的，所以你在order by里要不然就是每个字段后面什么都不加，直接就是order by xx1,xx2,xx3，要不然就都加DESC降序排列，就是order by xx1 DESC,xx2 DESC,xx3 DESC。如果都是升序排列，直接就从索引树里最小的开始读取一定条数就可以了，要是都是降序排列，就是从索引树里最大的数据开始读取一定的条数就可以了，但是不能order by语句里有的字段升序有的字段降序，那是不能用索引的，例如 SELECT * FROM person_info ORDER BY name, birthday DESC LIMIT 10;

1. orderby字段需要在索引，要是你order by语句里有的字段不在联合索引里，不能使用索引
2. 不能使用复杂函数order by语句里的字段用了复杂的函数，也不能使用索引

   回表查询对性能的损害

   大批量回表查询，性能也会降低

   不管是单列索引还是联合索引，其实一个索引就对应着一颗独立的索引B+树，索引B+树的节点仅仅包含了索引里的几个字段的值以及主键值。
   即使我们根据索引树按照条件找到了需要的数据，那也仅仅是索引里的几个字段的值和主键值，万一你搞了一个select 还需要很多其他的字段，那还得走一个回表操作，根据主键跑到主键的聚簇索引里去找，聚簇索引的叶子节点是数据页，找到数据页里才能把一行数据的所有字段值提取出来。
   类似`select from table order by xx1,xx2,xx3的语句，可能你就是得从联合索引的索引树里按照顺序取出来所有数据，接着对每一条数据都走一个主键的聚簇索引的查找，其实性能也是不高的。<br />有的时候MySQL的执行引擎甚至可能会认为，你要是类似select * from table order by xx1,xx2,xx3`的语句，相当于是得把联合索引和聚簇索引，两个索引的所有数据都扫描一遍了，那还不如就不走联合索引了，直接全表扫描得了，这样还就扫描一个索引而已。

   小量数据回表查询，性能高

   但是你如果要是select * from table order by xx1,xx2,xx3 limit 10这样的语句，那执行引擎就知道了，你先扫描联合索引的索引树拿到10条数据，接着对10条数据在聚簇索引里查找10次就可以了，那么就还是会走联合索引的。

   覆盖索引

   类似select xx1,xx2,xx3 from table order by xx1,xx2,xx3这样的语句，这种情况下，你仅仅需要联合索引里的几个字段的值，那么其实就只要扫描联合索引的索引树就可以了，不需要回表去聚簇索引里找其他字段了。所以这个时候，需要的字段值直接在索引树里就能提取出来，不需要回表到聚簇索引，这种查询方式就是覆盖索引。

   联合索引使用建议

   在写SQL语句的时候，
   一方面是你要注意一下也许你会用到联合索引，是否可能会导致大量的回表到聚簇索引，如果需要回表到聚簇索引的次数太多了，可能就直接给你做成全表扫描不走联合索引了；
   一方面是尽可能还是在SQL里指定你仅仅需要的几个字段，不要搞一个select *把所有字段都拿出来，甚至最好是直接走覆盖索引的方式，不要去回表到聚簇索引。
   即使真的要回表到聚簇索引，那你也尽可能用limit、where之类的语句限定一下回表到聚簇索引的次数，就从联合索引里筛选少数数据，然后再回表到聚簇索引里去，这样性能也会好一些。