MySQL——页和索引

生产上为了高效地查询数据库中的数据，我们常常会给表中的字段添加索引，大家是否有考虑过如何添加索引才能使索引更高效，考虑如下问题

• 添加的索引越多越好吗？
• 为什么有时候用了索引但是查询速度并没有提高？
• 索引有哪些类型？
• 如何评价一个索引设计的好坏？

InnoDB页存储结构

数据被划分为若干个页，以页作为磁盘和内存之间交互的基本单位，一般为16KB，且页内的物理地址是连续的。最小记录、最大记录和用户记录，三者为主要数据，其中理论上存储了各个行信息，但实际上是多个行信息组合成的一条连续的数据。

数据存储过程

行

sql语句

# 创建语法
CREATE TABLE 表名(
    列的信息
) ROW_FORMAT = 行格式名称
# 修改语法
ALTER TABLE 表名 ROW_FORMAT = 行格式名称

行结构图

剖析图

1. 变长字段长度列表，根据列表长度决定占用字节，如：01 03 04；
2. NULL 标志位，如：00；
3. 记录头信息，固定5个字节，如：00 00 00 10 00；
4. 行ID，固定6个字节，如：00 00 00 00 05 00；
5. 事务ID(transaction_id)，固定6个字节，如：00 00 00 01 43 11（redo log使用）；
6. 回滚指针(roll_pointer)，固定7个字节，如：8e 00 00 01 a3 01 10（undo log使用）；
7. 列的数据，根据列数据长度决定占用字节。如：61 61 61 61 62 62 62 63 63 20 20 20 20 20 20 20 20 64；

页目录

• 页目录里存放的单位是槽
• 每个槽代表1组记录
• 定位到某个页后，需要二分查找其中的行时，就需要用到目录。
• 针对数据行而产生的的。

将所有正常的记录（包括最大最小记录，不包括标记为删除的记录）划分为几个组。

每个组的最后一条记录的头信息中的 n_owned 属性表示该组内共有几条记录。

将每个组的最后一条记录的地址偏移量按顺序存储起来，每个地址偏移量也被称为一个槽（每个槽会保存到页目录中）。这些地址偏移量都会被存储到靠近页的尾部的地方，页中存储地址偏移量的部分也被称为 Page Directory。我们查询数据的时候，其实就是查询槽里面存储的主键，然后再根据得到的主键去查询对应的数据行。

1）初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
2）之后每插入一条记录都把这条记录放到最大记录所在的组，直到最大记录所在的组中的记录数等于8个。
3）在最大记录所在组中的记录数等于8个（为什么是8个？）的时候再插入一条记录时，将最大记录所在组平均分裂成2个组，然后最大记录所在的组就剩下4条记录了，然后就可以把即将插入的那条记录放到相应的组中了。
4）页目录中的各个槽代表的记录的主键值都是从小到大排序的，所以可以使用二分法来进行快速查找。
5）通过记录的 next_record 属性组成的链表遍历查找该槽中的各个记录。

页小结

1. InnoDB 数据页由7个部分组成，各个数据页可以组成一个双向链表（prev指向上一页，next指向下一页），而每个数据页中的记录又可以组成一个单向链表（这样就可以对每一页的数据全遍历），每个数据页都会为存储在它里面的记录生成一个页目录。在通过主键查找某条记录时，可以在页目录中使用二分法快速定位到相应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
2. 下一个数据页中的主键值必须大于上一个页中的主键值。

索引

当我们要在新华字典里查某个字（如「先」）具体含义的时候，通常都会拿起一本新华字典来查，你可以先从头到尾查询每一页是否有「先」这个字，这样做（对应数据库中的全表扫描）确实能找到，但效率无疑是非常低下的（每次查询都是全表扫描），更高效的方相信大家也都知道，就是在首页的索引里先查找「先」对应的页数，然后直接跳到相应的页面查找，这样查询时候大大减少了，可以为是 O(1)。

数据库的索引其实和查字典的目录的作用十分相似，我们通过索引查找到对应的页，然后再从页的槽里面找到对应的分组记录。最后遍历分组记录返回我们需要的数据。

• 在一个页中的查找

  • 索引搜索
    • 在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录，最后需要回表则回表。
  • 非索引搜索
    • 在数据页中没有对非主键列建立页目录，所以无法通过二分法快速定位相应的槽。只能从最小记录依次遍历单链表中的每条记录，然后对比每条记录是否符合搜索条件。

• 在多个页中的查找

  • 索引搜索
    • 1）二分法定位页目录
    • 2）二分法定位页
    • 3）二分法定位数据行（最后需要回表则回表）
  • 非索引搜索
    • 1）遍历所有的列
    • 2）定位到记录所在的页
    • 3）在所在的页中查找相应的记录。

但是这时候会有一个问题——因为这些16KB的页在物理存储上并不连续，所以如果想从这么多页中根据主键快速定位某些记录所在的页，我们需要给他们做个目录，就像为页中的记录建立一个页目录一样，引擎会为所有的页建立一个目录。每个页对应一个目录项。

下面两张图其实就是数据库根据索引查询数据的流程图，我们其实可以看出来,这其实就是一个
B+树！


那么我们已经知道了索引可以大大提高数据的查询效率，那么除此之外加索引还有什么别的好处吗？

1.索引能极大地减少扫描行数
2.索引可以帮助服务器避免排序和临时表
3.索引可以将随机 IO 变成顺序 IO

第一点我们已经知道了，那么我们来详述一下索引如何帮助服务器避免排序和临时表

select * from table order by age desc;

看上述查询语句，如果我们不适应索引的话，MySQL的查询流程就是扫描所有行，把所有行加载到内存后，再按 age 排序生成一张临时表，再把这表排序后将相应行返回给客户端，更糟的，如果这张临时表的大小大于 tmp_table_size 的值（默认为 16 M），内存临时表会转为磁盘临时表，性能会更差，如果加了索引，由于索引本身就是有序的，磁盘读到的数据就是根据age排序好的，所以无需生成临时表，大大提高了性能

随机IO和顺序IO
这个问题我们可以用旋转火锅来举例，服务员把一盘盘的菜放在旋转传输带上，然后等到这些菜转到我们面前，我们就可以拿到菜了，假设装一圈需要 4 分钟，则最短等待时间是 0（即菜就在你跟前），最长等待时间是 4 分钟（菜刚好在你跟前错过），那么平均等待时间即为 2 分钟，假设我们现在要拿四盘菜，这四盘菜随机分配在传输带上，则可知拿到这四盘菜的平均等待时间是 8 分钟（随机 IO），如果这四盘菜刚好紧邻着排在一起，则等待时间只需 2 分钟（顺序 IO）。

上述中传输带就类比磁道，磁道上的菜就类比扇区（sector）中的信息，磁盘块（block）是由多个相邻的扇区组成的，是操作系统读取的最小单元，这样如果信息能以 block 的形式聚集在一起，就能极大减少磁盘 IO 时间,这就是顺序 IO 带来的性能提升， B+ 树索引就起到这样的作用。

多个扇区组成了一个block，如果要读取的信息都在一个磁盘块里，那么我们只需要一次IO读就可以了

而如果信息在一个磁道中分散地分布在各个扇区中，或者分布在不同磁道的扇区上（寻道时间是随机IO主要瓶颈所在），将会造成随机 IO，影响性能。

随机IO的时间分布

1.seek Time: 寻道时间，磁头移动到扇区所在的磁道（找菜品所在的位置）
2.Rotational Latency：完成步骤 1 后，磁头移动到同一磁道扇区对应的位置所需求时间
3.Transfer Time 从磁盘读取信息传入内存时间
这其中寻道时间占据了绝大多数的时间（大概占据随机 IO 时间的占 40%）。

随机 IO 和顺序 IO 大概相差百倍 (随机 IO：10 ms/ page, 顺序 IO 0.1ms / page)，可见顺序 IO 性能之高，索引带来的性能提升显而易见！

索引的种类

MySQL中的索引主要有两类：

1. Hash索引
2. B+树索引

对于B+树索引上文已经提到过，就不赘述了

B+ 树是以 N 叉树的形式存在的，这样有效降低了树的高度，查找数据也不需要全表扫描了，顺着根节点层层往下查找能很快地找到我们的目标数据，每个节点的大小即一个磁盘块的大小，一次 IO 会将一个页（每页包含多个磁盘块）的数据都读入（即磁盘预读，程序局部性原理:读到了某个值，很大可能这个值周围的数据也会被用到，干脆一起读入内存），叶子节点通过指针的相互指向连接，能有效减少顺序遍历时的随机 IO，而且我们也可以看到，叶子节点都是按索引的顺序排序好的，这也意味着根据索引查找或排序都是排序好了的，不会再在内存中形成临时表。

B+树是以N叉树形式存在，那么这个N可以随意设定吗？

答案是不行的，我们已经提到过页的默认大小是16KB，所以N值的选取应该以页面大小接近16KB为基准。

哈希索引

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

对于每一行数据，存储引擎都会对所有的索引列（上图中的 name 列）计算一个哈希码（上图散列表的位置），散列表里的每个元素指向数据行的指针，由于索引自身只存储对应的哈希值，所以索引的结构十分紧凑，这让哈希索引查找速度非常快！

当然了哈希表的劣势也是比较明显的，不支持区间查找，不支持排序，所以更多的时候哈希表是与 B Tree等一起使用的，在 InnoDB 引擎中就有一种名为「自适应哈希索引」的特殊索引，当 innoDB 注意到某些索引值使用非常频繁时，就会内存中基于 B-Tree 索引之上再创建哈希索引，这样也就让 B+ 树索引也有了哈希索引的快速查找等优点，这是完全自动，内部的行为，用户无法控制或配置，不过如果有必要，可以关闭该功能。

高性能索引策略

聚簇索引（叶子节点存储形式）

聚簇索引的主键值应尽量是连续增长的值，不要随机值或UUID，否则会造成大量的页分裂（新增数据）与页合并（删除数据）。

• 使用记录主键值大小进行记录和页的排序。
  1）页内的记录是按照主键的大小顺序排成一个单向链表（存放索引的页）。
  2）各个存放用户记录的页是根据页中记录的主键大小顺序排成一个双向链表
  3）各个存放目录项的页是根据页中记录的主键大小顺序排成一个双向链表
• B+树的叶子节点存储的是完整的用户记录。
• 不需要显式创建，引擎自动创建。
• 聚簇索引就是数据的存储方式（所有的用户记录都存在叶子节点，索引即数据）。

二级索引（非聚簇索引）——非叶子节点存储形式

聚簇索引的B+树使用主键进行排序，而自定义的B+树可以采用其他的排序规则。

特性

• 使用记录 c 列的大小进行记录和页的排序
  1）页内的记录是按照 c 列值的大小顺序排成一个单向链表（聚簇是根据主键）。
  2）各个存放用户记录的页是根据页中的记录的 c 列大小顺序排成一个双向链表。
  3）存放页目录项记录的页也是根据页中记录的c列大小顺序排成一个双向链表。

• B+树的叶子节点存储的并不是完整的用户记录，而是 c 列 + 主键。

• 目录项记录中不再是 主键 + 页号，而是 c 列 + 页号。

是否需要回表

1.不需要回表（索引覆盖）
如果一个索引包含（或覆盖）所有需要查询的字段值，则成为 『覆盖索引』，无需回表。

• 不用回表，减少二次查询，减少随机IO；
• 减少遍历页的数量

如：直接通过 c 列的值查到某些记录的话，则使用二级索引的B+树即可

//我可以根据name=1的列直接返回name
select name from user where name = 1;

需要回表
当二级索引的B+树不包含需要的数据时，需要根据查到的主键值，再去聚簇索引中查找完整的用户记录：

//我不可以根据c=1的列直接返回name和age，
//所以再去聚簇索引中查询c=1的列中name和age的用户记录
select name, age from user where c = 1;

组合索引

特性
只生成1颗B+树，却同时以多个列的大小作为排序规则，例如让B+树按照 name 和 age 的大小进行排序：

• 先把各个记录和页按照 name 进行排序（最左优先）。
• 在记录的 name 列相同的情况下，采用 age 进行排序。

举例
假设当前索引结构为联合索引：(c2, c3, c4)

• 对于 (c2, c3, c4) 这样的数据检索时，B+树按照从左到右的顺序来搜索。

• 如果没有 c2，按照 (c3, c4) 这样检索时，B+树会因为找不到 c2，而无法使用索引。

• 如果没有 c3，按照 (c2, c4) 这样检索时，B+树会先使用 c2 来指定搜索方向，但由于 c3 的缺失，所以只能等 c2 都找到，最后遍历匹配 c4。

Tips:前导列是不可缺失的，如果缺失，联合索引会失效

示例

• 从左向右匹配，直到遇到范围查询（>、<、between、like）就停止匹配。

where a = 1 and b = 2 and c > 3 and d = 4

1.当联合索引为{a,b,c,d}时，那么d=4这个条件其实是没有用到的，因为在执行c>3时就已经停止匹配了
2.当联合索引为{a,b,d,c}时，那么上述语句会全部执行。

• = 和 in 是可以乱序的，优化器会自动识别优化。

where a=1 and b=2 and c=3;
where b=2 and a=1 and c=3;

上述语句都可以使用联合索引{a,b,c}
使用原则以及索引选择性

• 联合索引的总体选择性越高越好（可以看作是区分度最高的索引，比如说每个人的手机号码）
• 分组及排序时，让排序沿着某个索引顺序，防止二次排序。
• 在不考虑分组及排序时，尽量选择区分度高的列作为联合索引的前导列。B+树是按照前导列进行排序的，将选择性高的列放到前面能够最快地过滤出需要的记录。
• 联合索引长度不宜过长，可利用前缀索引降低索引条目长度。

前缀索引和索引选择性

那么实际开发场景中，我们应该如何选择前缀索引呢？

索引选择性：不重复的索引值（也称为基数，cardinality）和数据表的记录总数的比值，比值越高，代表索引的选择性越好，唯一索引的选择性是最好的，比值是 1。
Tips:我们可以通过 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

可以看到当前缀长度为 7 时，索引选择性提升的比例已经很小了，也就是说应该选择 city 的前六个字符作为前缀索引，如下

ALTER TABLE city_demo ADD KEY(city(6));

当然有人会觉得长度为4和5的提升比例也很小，那么是否可以使用长度为4作为前缀索引呢？还是用上面的例子

SELECT 
    COUNT(*) AS  cnt, 
    LEFT(city, 4) AS pref
  FROM city_demo GROUP BY pref ORDER BY cnt DESC LIMIT 5

结果为

可以看到分布极不均匀，以 Sant，Toul 为前缀索引的数量极多，这两者的选择性都不是很理想（我们选择前缀索引要尽量选择区分度高的，比如说用每个人的身份证号都不同，但是前6位相同的概率还是很高的），所以要选择前缀索引时也要考虑最差的选择性的情况。

前缀索引虽然能实现索引占用空间小且快的效果，但它也有明显的弱点，MySQL 无法使用前缀索引做 ORDER BY 和 GROUP BY ，而且也无法使用前缀索引做覆盖扫描，前缀索引也有可能增加扫描行数（要回表，还要查询聚簇索引）。

实例

假设数据库有一个表如上图所示，我们执行sql语句

SELECT id,email FROM user WHERE email='zhangssxyz@xxx.com';

如果我们针对 email 设置的是整个字段的索引，则上表中根据 「zhangssxyz@163.com」查询到相关记记录后,再查询此记录的下一条记录，发现没有，停止扫描，此时可知只扫描一行记录，如果我们以前六个字符（即 email(6)）作为前缀索引，则显然要扫描四行记录，并且获得行记录后不得不回到主键索引再判断 email 字段的值，所以使用前缀索引要评估它带来的这些开销。

还有另外一种情况，就是如果前缀基本都是相同的该怎么办，比如说做人口信息统计表时，每个人的身份证号不同，但是前6位可能是一样的，使用前缀索引重合度会很高，怎么解决？

一种方式是针对身份证建立哈希索引（可以将身份证字符串哈希映射成一个整数，避免身份证字段长度过长，占用的存储空间过多），另一种方式比较巧妙，将身份证倒序存储，查的时候可以按如下方式查询:

SELECT field_list FROM t WHERE id_card = reverse('input_id_card_string');

这样就可以用身份证的后六位作前缀索引了。

索引设计准则——三星索引

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

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

第一颗星：WHERE 后面参与查询的列可以组成单列索引或联合索引

第二颗星：避免排序，即如果 SQL 语句中出现 order by colulmn，那么取出的结果集就已经是按照 column 排序好的，不需要再生成临时表。

第三颗星：SELECT 对应的列应该尽量是索引列，即尽量避免回表查询。

所以对于下面的sql语句：

SELECT age, name, city where age = xxx and name = xxx order by age

联合索引应该设计成（age,name,city）(避免order by age再建立一个临时表)

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

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 都伴随着索引的更新，很可能频繁伴随着页分裂与页合并。

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

索引如何加速查询

我们上文已经提到了索引主要分hash索引和B+树索引，而且会使用聚簇索引、辅助索引、联合索引、前缀索引等帮助我们提高数据的查询速度，但是我们都知道索引可以加速查询,但是是如何加速的又有谁知道呢？所以这个章节我们来深挖一下索引的加速底层原理。

1、聚簇索引

我们先建立一个数据表：

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`)
) 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+树，主键从 1 开始递增，插入五条，所以是 1 到 5，那么这棵B+树的样子如下图所示，我们可以看到果然只有叶子节点才存储有数据：

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

select * from student where id=5;

虽然我们使用了主键查询，但是如果没有使用B+树存储数据，数据在磁盘中还是分散存储的，你只能全表扫描，犹如大浪淘沙。（这也是为什么很少使用hash索引）

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

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

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

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

你要访问磁盘的次数，是由这棵树的深度决定的。尤其是在大数据量的时候，B+树的优势更是展露无遗。

假设没有指定主键呢？没关系，唯一键也可以。

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

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

2、二级索引

聚簇索引只能帮你加快主键查询，但是如果你想根据姓名查询呢？
对不起，看看上面这棵树你就知道，数据并没有按照姓名进行组织，所以，你还是只能全表扫描。

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

create index index_name on student(name);

这时候 MySQL 又会建一棵新的 B+树：

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

select * from student where name = "David";

MySQL 到你刚刚创建的这棵 B+树 查询，快速查到有两条姓名是“David”的记录，并且拿到它们的主键，分别是 4 和 5，但是你要的是select *呀，怎么办？
别忘了，MySQL 在一开始就给你建了一棵 B+树 了，把这两棵树，放在一起，拿着从这棵树上查到的两个主键ID，去聚簇索引找，事情不就解决了？
(这其实就是一个回表的过程，如果我们select name，那么不需要回表，如果select *，由于索引 name只存储了name 和主键id，我们只能根据查询到的主键id再回表取聚簇索引里查找对应数据)

流程图如下：

这个不带行数据完整信息的索引，就叫二级索引（secondary index），也叫辅助索引。

3、复合索引

如果我还想根据姓名和年龄同时查询呢？

select name,age from student where name = "David" and age = 18;

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

create index idx_name_age on student(name,age);

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

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

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

Reference

公众号——码海
公众号——柳树的絮叨叨