MySQL索引底层结构

在索引优化之前，我们先要深入的了解一下索引底层的结构，理解索引的本质，方便我们后面优化索引。

1）索引本质

索引是帮助MySQL高效获取数据的 排好序的数据结构。

索引数据结构：

二叉树
红黑树
Hash表
B-Tree（主流）

如果没有索引的话，如何检索数据

select * from t1 where col2 = 22
执行以上的SQL，MySQL需要在数据库中一条一条数据从上往下去查询（每读取一次数据就会和磁盘做一次IO，读取还是随机读取磁盘），直到匹配到对应的数据，如果数据量多，过程极为耗费时间。

二叉树索引结构

一个节点只能有两个子节点
二叉树结构左子节点的值小于父亲节点值，右子节点的值大于父亲节点的值，采用二分折半查找，速度较快
key：索引，value：索引在磁盘上所在行的磁盘地址

索引插入过程：

当前要插入20，走了第一步发现20小于22，所以继续往左子节点走，到了第二步发现比5大比23小，到了第三步，发现比5大就插在了右子节点。

MySQL二叉树查询逻辑：

比如下图，我们查询的值是91。MySQL会从第一个值判断，34 ，91比34大，就找右下角的分支继续比对。
91比89大，继续往89右下角的分支去查询，直到匹配到数据或者结构树查询一遍。
1. 这样每次查询一次，都会和磁盘进行一次IO，但是比没有索引结构的效率明显高多了。

二叉树缺点

经典二叉树会出现一个极端例子，就是链表，节点数据越来越大。这种情况下，二叉树搜索性能就会降低

红黑树索引结构

红黑树又称二叉平衡树，是在二叉树上升级来的，当你一边比另外一边树结构比较大的时候，就会自动做一个优化平衡调整。

但，红黑树不是最理想的选择，因为当数据量太大的时候，索引树的高度就会不可控，树形就会变得特别的高，假设有500W条数据，那你查询下来的时候，是从根节点依次往下比对，造成的磁盘IO也是很可怕的。

它的左子树和右子树都是一颗平衡二叉树。
它的左子树和右子树的高度之差(平衡因子)的绝对值不超过 1

索引插入过程：

我们插入1和2后，在插入3，他会自动平衡。
插入4和5后，红黑树又自己做了平衡调整。

Hash 索引结构

大多情况下，Hash索引效率比B+Tree更快
Hash仅支持 ” = “、” IN “，不支持范围查询
哈希算法：除法散列，冲突机制采用链表方式

Hash结构如何插入索引

插入 Alice，会对Alice进行Hash运算（除法散列），假设结果是2，然后就把Alice 存放到Hash桶中 2 的位置
在2的后面按顺序插入一个索引，索引data 指向索引所在磁盘的文件地址

Hash结构如何查找数据

查找 ”Alice“，会对Alice进行Hash运算，假设结果是2
就去Hash桶 2的位置后，一一匹配索引，匹配到索引后根据 data的地址去硬盘中获取数据

B-Tree（B树）索引结构

所有的节点的数据索引都是从左到右递增排序。
所有索引数据都不重复。
所有的节点都会存放data磁盘地址。

B+Tree （B+树，B-Tree升级索引结构）

B+Tree分为2个块，叶子节点和非叶子节点，所有的节点的数据索引都是从左到右递增排序。
每一页左侧最小的索引都会作为冗余索引，放如非叶子节点作为备份。
不论是单值索引还是联合索引，每个索引都会建立一颗自己的B+Tree。

主键索引结构（聚簇索引，密集索引）

聚簇索引的叶子节点会存放主键ID的整行数据。
- 也就是说，只要在聚簇索引中找到索引的叶子节点，就可以直接找到该索引的整行数据。
叶子节点：
- 叶子节点拥有全部的索引字段。
- 叶子节点存放的data 其实是 磁盘地址，指向了该索引数据存放于磁盘的地址
  - 如果是二级索引，则存放的是聚簇索引里面的主键ID地址
- 指向左右两边索引节点的磁盘地址，该地址是为了快速找到相近的区间节点，这样做的目的是为了 提高区间访问的性能。
非叶子节点：
- 非叶子节点不存储data（磁盘地址）
- 只存储索引部分索引，它会从叶子节点的索引取出部分索引存于非叶子节点，目的是为了冗余备份索引，存放更多的索引

非主键索引结构

非主键索引结构又称为：二级索引，非聚集索引，稀疏索引
唯一索引，单值索引，联合索引，全文索引都属于非主键索引
- 唯一索引：索引列的值必须唯一
- 全文索引：主要用来查找文本中的关键字，不是直接与索引值相比较，在插入索引时会进行分词，MySQL分词器无法对中文分词且MySQL 全文索引性能一般，所以一般不用，如果需要全文检索建议使用elasticsearch
回表扫描和全表扫描的区别
- 回表扫描
  - 通过辅助索引树找到聚簇索引的地址后，回表（聚簇索引）继续查找主键索引。
- 全表扫描
  - 通过聚簇索引树一行一行逐个扫描，因为聚簇索引树包含了整个表的数据。
非主键索引结构和主键索引结构的区别
- 非主键结构的叶子节点 data存储的是聚簇索引的主键索引地址。
- 主键结构叶子节点data存放的是数据库表的整行详细数据。

目的：

避免数据的唯一性出问题
- 为了避免主键索引和非主键索引的data 数据出现数据不一致的情况
  - 通过辅助索引树找到结果后，根据data的聚簇索引的主键索引地址回表查询（回到聚簇索引树），读取整行数据。
节省存储空间

二级索引如何查找数据

二级索引查找数据图例

去IDB文件（存放索引和数据的数据库文件）中，存放二级索引的数据文件中，按照二分查找的方式去查找，定位具体的数据后，该数据保存的 data ，存放的是主键索引。
拿着主键索引的地址去IDB中，找到主键索引（聚集索引）的结构文件，在通过主键索引定位到具体的数据。
- 该行为也称为回表。

查询的结果集都有索引

如果查询的结果集（select 的条件）都有索引，那么MySQL会默认走二级索引（辅助索引），而不是走主键索引，因为主键索引是聚集索引，data里面放的是整行的数据，占用的空间大。
- explain select * from film;

MMR（多范围磁盘读取）

二级索引读取到一条记录后，都需要携带主键索引，回表去聚簇索引中查询。

二级索引存储的主键索引是无序的，每次回表的时候都要随机读取聚簇索引Page页，直到成功为止，带来的IO开销很大，于是就引出了MMR，多范围磁盘读取。

MMR

先读取部分二级索引，从小到大排好序后，在统一回表。
MMR触发条件较为苛刻，很少会使用到。

B+Tree如何查找数据

此时我们要查找数据30，MySQL会先从根节点开始查找，先把根节点所有元素拿到内存中（RAM），然后通过二分查找（折半查找）进行匹配，发现30比15大比56小，那30肯定就在这中间。
- 15和56之间存放的是这一块的叶子节点信息的磁盘地址。
MySQL拿到了这一块节点信息后，和第一步一样存入内存中，再次进行二分查找，后面轮到了20-30之间，在以此类推，直到找到30的索引，获取到该索引磁盘所在的磁盘地址，在通过该地址去磁盘中获取数据。

B+Tree节点存放大小

如图所示，在MySQL中一个节点也称为一页，Innodb数据库默认可存放16KB的索引（MySQL认可的最佳大小）。
- 该数字如果过大，数据都往内存丢，内存吃不消，过小的话会造成效率下降，所以默认16KB即可，不建议人为修改。
- 16KB大致能存放1170个索引，整颗B+Tree大致能放下几千万个索引。
show global status like 'innodb_page_size';

B-Tree和B+Tree的区别

核心概念：你的叶子结点横向能存放的索引越多，你的树高度就越小，检索数据就越快。

问题：为什么有B-Tree了为什么还要B+Tree？

区别一：节点索引存储空间问题

B树所有节点都存放了data，导致他每一页能存放的索引十分有限，B树的高度会变得很高，查询效率慢
- 假设每个索引占用1KB，那么一页只能存放16KB，那如果是千万级的数据，则他需要存放的树高度就有1250000，如果进行数据检索会耗费磁盘IO，还是很耗费时间的。
而如果把data存放在叶子节点，非叶子结点则存放索引，这样非叶子结点一页可以存放1170个索引，大大的缩小了树高度，数据进行检索的时候磁盘IO次数就变少了。

区别二：区间访问速度

B+Tree除了存放索引和磁盘地址外，还多了一个指向左右两边索引节点的磁盘地址，该地址是为了快速找到相近的区间节点，这样做的目的是为了 提高区间访问的性能。

2）MyISAM存储引擎索引实现（非聚集索引）

存储引擎模式是基于表的，和数据库无关
- 所以一个数据库里面可以同时存储多个不同存储引擎的表
MyISAM索引文件和数据文件是分开存储的，所以也叫 非聚集索引（非聚簇索引）

磁盘存储文件

MySQL的数据磁盘文件默认都是保存在在MySQL的安装目的底下，.frm 数据表结构信息文件，.MYD 数据文件， .MYI索引文件。

MyISAM如何进行数据查询

MyISAM

MyISAM索引文件和数据文件是分离的（非聚集），所以将导致查询效率相对底下。

数据查询流程

如上图所示，我们查询Col1 = 50的话，它会从根节点进行二分查找，最终锁定了50这个叶子节点。
获取到他的data，它的data存储的是索引文件磁盘地址，通过该地址去磁盘文件myisam.MYI（索引文件）中去查找，获取到索引存储数据的地址
通过索引存储数据的地址，去磁盘文件 myisam.MYD中获取到真正索引存储的数据文件，然后拿出来后再进行数据比对。

3）InnoDB存储引擎索引实现（聚集索引）

磁盘存储文件

MySQL的数据磁盘文件默认都是保存在在MySQL的安装目的底下，.frm 数据表结构信息文件，.idb 索引+数据库数据文件。

InnoDB索引实现

表数据文件（IBD）是按照B+Tree组织的一个索引结构文件，包含了叶子节点（只存索引）和非叶子节点（存储数据在磁盘的指针地址）
聚集索引，又称聚簇索引，密集索引，叶子节点包含了该索引整行的数据记录。
InnoDB表必须建立主键
- InnoDB表可以通过主键来按照B+Tree 组织索引。
- 如果不创建主键
  - MySQL会找到表中的唯一索引（唯一性的二级辅助索引）按照B+Tree 组织索引。
  - 没有唯一索引
    - 如果找不到的话，MySQL会自己创建一个 隐藏列（看不到的），来帮你维护一个唯一索引。
- 创建主键
  - 如果我们指定了主键，MySQL会通过该主键去按照B+Tree 组织索引。
推荐使用整型的自增主键
- 为什么推荐整型
  - 【效率问题】当MySQL从根节点开始查找数据时，索引是整型的明显比字符串（UUID等其他）比较的速度更快，效率更高
  - 【空间问题】数据库的硬盘空间非常宝贵且硬盘价格昂贵，索引占用越小，越能节约磁盘空间，一页可以存放的索引越多。
- 为什么推荐 自增主键
  - 区间访问速度、查找速度更快
    - 叶子节点除了索引和磁盘地址外，还存放了一个左右两边节点的地址，方便我们快速找到他相邻的节点。
    - 如果我们是自增主键，那么叶子节点的索引则是有顺序，从小到大的排序。那么我们在进行范围查找，如：a > 20 and a < 50 ，我们找到了20的节点后，可以根据他指向右边附近结点的地址，快速地定位到第三个节点（49,50）
  - 避免索引移位
    - 因为插入的时候是按顺序插入的，如果不是自增主键，插入其他类型的主键，很可能造成已有的索引进行移位，效率降低。

4）联合索引（复合索引）

多个字段共同组织成的索引。
生产环境中，一张表不建议添加多个单值索引，而是应当通过2-5个联合索引覆盖90%的SQL查询语句。

最左前缀原则

联合索引

创建索引是按照从左往右创建的，查询数据的时候，自然也要从左往右比较，且不可以跳过中间的字段。
每一页左侧最小的索引都会作为冗余索引，放如非叶子节点作为备份。

为什么要强制使用最左前缀原则

复合索引：mysql> KEY 'idx_name_age_position' (‘name’,'age','position') USING BTREE

走索引：mysql> explain select * from sys_order where name = 'Bill' and age = 30

不走索引：mysql> explain select * from sys_order where age = 30 and position = '2002-06-03'

如果查询的时候直接跳过了最左的索引（name），则直接使用后面的复合索引去查询（age），就会造成走不了索引，然后只能全表扫描。
- 因为MySQL的索引都是排好序的，排序的时候是按照 复合索引的最左边的索引 进行排序的。

联合索引失效

查询的时候，跳过了最左边第一个参数，违背了最左原则
查询的时候，跳过了中间的参数，如：
- (‘name’,’age’,’position’)
  - 查询的条件：where name = ‘aaa’ and position = ‘asdf’
    - 跳过了age，这样的话联合索引也会失效

5）自适应哈希索引

InnoDB会监控我们每颗索引树使用情况，如果发现某个索引经常被使用，那么就会在InnoDB内部创建一个 Hash 索引（自适应哈希索引），如果再次查询该索引，会通过Hash算法找到具体的记录，效率比去B+Tree查询更快。

自适应哈希索引特点

哈希算法：除法散列，冲突机制采用链表方式
自适应哈希，我们是无法去干预的，只能InnoDB自己通过算法控制
哈希索引只会存等值查询，如：where id = 1 ，非等值查询，如：范围查询是不会存入哈希索引

InnoDB引擎三大特性

双写缓冲区
自适应哈希索引
Buffer Pool

Hash结构如何插入索引

插入 Alice，会对Alice进行Hash运算，假设结果是2，然后就把Alice 存放到Hash桶中 2 的位置
在2的后面按顺序插入一个索引，索引data 指向索引所在磁盘的文件地址
默认情况下，自适应索引一共有8个分区（最大可设置512个），目的是为了避免高并发下的数据库锁导致事务串行，执行效率低

Hash结构如何查找数据

查找 ”Alice“，会对Alice进行Hash运算，假设结果是2
就去Hash桶 2的位置后，一一匹配索引，匹配到索引后根据 data的地址去硬盘中获取数据

覆盖索引 / 索引覆盖

覆盖索引并不是一种索引，而是一种索引的覆盖方式，可以直接从辅助索引中可以得到查询的记录，不需要回表到聚簇索引查询。
不要使用select * ，而是应该 只查询你要的数据，并且你查询的字段进行能走索引。

7）三星索引

三星索引并不是真正的索引，有些类似于覆盖索引一样，只是一种规范设计。
三星索引优先级最高，一次查询通常只需要一次磁盘随机读取，以及一次索引扫描。
值得注意的是，由于三星索引条件和约束较为苛刻，如果在生产环境中，无法满足三星索引，请尽量满足二星索引。

一星：索引中查询相关的索引行是相邻的，或者至少相距足够靠近

二星（排序星）：索引中数据列的顺序和查找中排序顺序相同

三星：索引中的列包含了查询中需要的全部列。索引包含查询所需要的数据列，不再进行全表查表，回表操作

下面举一个例子为大家介绍一下三星索引是什么样子的

现在有一张表，表结构如下

1	CREATE TABLE `user` ( `id` int(11) NOT NULL AUTO_INCREMENT, `name` varchar(10) NOT NULL, `age` int(10) DEFAULT NULL, PRIMARY KEY (`id`)) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4;

一星

我们现在给 age 加上索引

1	create index idx_age on user (age);

查询

1	select * from user where age in (10,20,35,43)

这条语句不一定符合一星，因为 age 是一个范围，数据可能比较分散

1	select * from user where age = 20;

这条语句是符合一星的，因为索引是按照 age 从小到大排序的，所以 age = 20 的数据肯定是在一起的

二星

1	select * from user where age = 20 order by name;

这条语句符合一星，但不符合二星，因为数据列的顺序是按照 age 排序的，如果现在改成 name 排序，可能导致索引顺序与 order by 排序结果不同，结果如下：

![img][image-9]

![img][image-10]

1	select * from user where age = 20 order by age

这条查询语句则符合一星和二星

三星

案例1：

1	select * from user where age = 20

这条语句不符合三星，因为索引列中只有 id 和 age，没有 name

1	select age from user where age = 20

这条语句则符合三星，因为只查询了 age，age 在索引中存在，不需要回表

案例2：满足三星索引

CREATE TABLE customer (
	cno INT,
	lname VARCHAR ( 10 ),
	fname VARCHAR ( 10 ),
	sex INT,
weight INT,
city VARCHAR ( 10 ));

-- 建立索引 
create index idx_cust on customer(city,lname,fname,cno);

查询SQL：

select cno,fname from customer where lname ='xx' and city ='yy' order by fname;

满足最左前缀原则，也没有从联合索引中间跳过
满足一星要求
1. 满足原因：lname 做第一个查询条件
- lname是大基数字段，重复率很低
满足二星要求
1. 满足原因：排序字段使用了索引，且当前顺序是正常（按联合索引最左匹配原则即可）
满足三星要求
1. 满足原因：select 提取的数据都可以直接从索引中获取，不需要回表

索引使用注意事项

有多少个索引就会创建多少颗B+Tree，索引是帮助MySQL高效获取数据的 排好序的数据结构。方便我们快速查询到对应数据。
一个select 查询语句在执行过程中一般最多只能使用一个索引，即便where条件存在多个索引。
1. 特殊情况：特殊情况的话，会进行索引合并，具体可以看我博客《MySQL索引合并详解》

索引产生的问题

空间上的代价：

索引并不是越多越好，需要我们权衡利弊
- 索引树是会占用存储空间的，创建一个索引就会创建一颗B+Tree，每一棵B+Tree的每一个节点都会占用16KB
- 一张表建议是创建2-5个索引，简直创建联合索引，少创建单值索引（利用率不高）

时间上的代价：

当我们对索引树进行增删改时，都可能会对节点和记录的排序造成破坏，存储引擎需要额外的时间来重新移位保证排序正常。

MySQL索引底层结构

1）索引本质

如果没有索引的话，如何检索数据

二叉树索引结构

二叉树缺点

红黑树索引结构

Hash 索引结构

Hash结构如何插入索引

Hash结构如何查找数据

B-Tree（B树）索引结构

B+Tree （B+树，B-Tree升级索引结构）

主键索引结构（聚簇索引，密集索引）

非主键索引结构

二级索引如何查找数据

查询的结果集都有索引

MMR（多范围磁盘读取）

B+Tree如何查找数据

B+Tree节点存放大小

B-Tree和B+Tree的区别

区别一：节点索引存储空间问题

区别二：区间访问速度

2）MyISAM存储引擎索引实现（非聚集索引）

磁盘存储文件

MyISAM如何进行数据查询

数据查询流程

3）InnoDB存储引擎索引实现（聚集索引）

磁盘存储文件

InnoDB索引实现

4）联合索引（复合索引）

最左前缀原则

为什么要强制使用 最左前缀原则

联合索引失效

5）自适应哈希索引

自适应哈希索引特点

Hash结构如何插入索引

Hash结构如何查找数据

覆盖索引 / 索引覆盖

7）三星索引

一星

二星

三星

索引使用注意事项

索引产生的问题

为什么要强制使用最左前缀原则