MySQL索引

什么是索引

目录

什么是索引

索引类型

主键索引

单列索引

唯一索引

复合索引

索引的数据结构

Hash表

二叉查找树

平衡二叉树

B树：改造二叉树

B+树：改造B树

索引的底层原理

聚簇索引

二级索引

复合索引

索引优化

索引实现

MyIsam索引

InnoDB索引

• 官方定义: 一种帮助mysql提高查询效率的数据结构

• 更通俗的说，数据库索引好比是一本书前面的目录，能加快数据库的查询速度。

• 一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往是存储在磁盘上的文件中的（可能存储在单独的索引文件中，也可能和数据一起存储在数据文件中）。

• 我们通常所说的索引，包括聚集索引、覆盖索引、组合索引、前缀索引、唯一索引等，没有特别说明，默认都是使用B+树结构组织（多路搜索树，并不一定是二叉的）的索引。

索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。

优势：

• 可以提高数据检索的效率，降低数据库的IO成本，类似于书的目录。

• 通过索引列对数据进行排序，降低数据排序的成本，降低了CPU的消耗。

• 被索引的列会自动进行排序，包括【单列索引】和【组合索引】，只是组合索引的排序要复杂一些。
• 如果按照索引列的顺序进行排序，对应order by语句来说，效率就会提高很多。

劣势：

• 索引会占据磁盘空间

• 索引虽然会提高查询效率，但是会降低更新表的效率。比如每次对表进行增删改操作，MySQL不仅要保存数据，还有保存或者更新对应的索引文件

索引类型

主键索引 索引列中的值必须是唯一的，不允许有空值。设定为主键后数据库会自动建立索引，innodb为聚簇索引

单列索引 即一个索引只包含单个列，一个表可以有多个单列索引，没有什么限制，允许在定义索引的列中插入重复值和空值。

唯一索引 索引列的值必须唯一，但允许有空值

复合索引 即一个索引包含多个列，组合索引的使用，需要遵循最左前缀匹配原则（最左匹配原则）。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。

Full Text 全文索引 (My5.7版本之前 只能由于MYISAM引擎)

只能在文本类型CHAR,VARCHAR,TEXT类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行like模糊查询时效率比较低，这时可以创建全文索引。MyISAM和InnoDB中都可以使用全文索引。

空间索引 MySQL在5.7之后的版本支持了空间索引，而且支持OpenGIS几何数据模型。MySQL在空间索引这方面遵循OpenGIS几何数据模型规则。

前缀索引 在文本类型如CHAR,VARCHAR,TEXT类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

主键索引

自动创建

--建表 主键自动创建主键索引
create table t_user(id varchar(20) primary key,name varchar(20));
--查看索引
show index from t_user;

单列索引

--建表时创建
create table t_user(id varchar(20) primary key,name varchar(20),key(name)); 
	'注意:随表一起建立的索引索引名同列名一致'
	  
--建表后创建
create index nameindex on t_user(name);

--删除索引
drop index 索引名 on 表名

唯一索引

--建表时创建
 create table t_user(id varchar(20) primary key,name varchar(20),unique(name));
 
--建表后创建
 create unique index nameindex on t_user(name);

复合索引

---建表时创建
 create table t_user(id varchar(20) primary key,name varchar(20),age int,key(name,age));
 
--建表后创建
 create index nameageindex on t_user(name,age);

索引的数据结构

Hash表

Hash表，在Java中的HashMap，TreeMap就是Hash表结构，以键值对的方式存储数据。我们使用Hash表存储表数据Key可以存储索引列，Value可以存储行记录或者行磁盘地址。Hash表在等值查询时效率很高，时间复杂度为O(1)；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

哈希索引能以 O(1) 时间进行查找，但是失去了有序性：

• 无法用于排序与分组；

• 只支持精确查找，无法用于部分查找和范围查找。

InnoDB 存储引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

二叉查找树

二叉树特点：每个节点最多有2个分叉，左子树和右子树数据顺序左小右大。

这个特点就是为了保证每次查找都可以这折半而减少IO次数，但是二叉树就很考验第一个根节点的取值，因为很容易在这个特点下出现我们并发想发生的情况“树不分叉了”，这就很难受很不稳定。

 显然这种情况不稳定的我们再选择设计上必然会避免这种情况的

平衡二叉树

平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 O(log2n)。查询id=6，只需要两次IO。

就这个特点来看，可能各位会觉得这就很好，可以达到二叉树的理想的情况了。然而依然存在一些问题：

1. 时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为10ms，在表数据量大时，查询性能就会很差。（1百万的数据量，log2n约等于20次磁盘IO，时间20*10=0.2s）

2. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

B树：改造二叉树

MySQL的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次IO，如果想要减少磁盘IO操作，就需要尽量降低树的高度。那如何降低树的高度呢？

假如key为bigint=8字节，每个节点有两个指针，每个指针为4个字节，一个节点占用的空间16个字节（8+4*2=16）。

因为在MySQL的InnoDB存储引擎一次IO会读取的一页（默认一页16K）的数据量，而二叉树一次IO有效数据量只有16字节，空间利用率极低。为了最大化利用一次IO空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储1000个索引（16k/16=1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建1百万条数据，树的高度只需要2层就可以（1000*1000=1百万），也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了，查询数据的效率也就提高了。

这种数据结构我们称为B树，B树是一种多叉平衡查找树，如下图主要特点：

1. B树的节点中存储着多个元素，每个内节点有多个分叉。

2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据。

3. 父节点当中的元素不会出现在子节点中。

4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接。

举个例子，在b树中查询数据的情况：

假如我们查询值等于10的数据。查询路径磁盘块1->磁盘块2->磁盘块5。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，10<15，走左路，到磁盘寻址磁盘块2。

第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<10，到磁盘中寻址定位到磁盘块5。

第三次磁盘IO：将磁盘块5加载到内存中，在内存中从头遍历比较，10=10，找到10，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。

相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘IO次数会大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B树的高度一般2至3层就能满足大部分的应用场景，所以使用B树构建索引可以很好的提升查询的效率。

过程如图：

B树索引查询过程

看到这里一定觉得B树就很理想了，但是前辈们会告诉你依然存在可以优化的地方：

1. B树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找10和35之间的数据，查找到15之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

2. 如果data存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘IO次数就会变大。

B+树：改造B树

B+Tree由三部分组成：根root、枝branch以及Leaf叶子，其中root和branch不存储数据，只存储指针地址，数据全部存储在Leaf Node，同时Leaf Node之间用双向链表链接，结构如下：

从上面可以看到，每个Leaf Node是三部分组成的，即前驱指针p_prev，数据data以及后继指针p_next，同时数据data是有序的，默认是升序ASC，分布在B+tree右边的键值总是大于左边的，同时从root到每个Leaf的距离是相等的，也就是访问任何一个Leaf Node需要的IO是一样的，即索引树的高度Level + 1次IO操作。

B+树，作为B树的升级版，在B树基础上，MySQL在B树的基础上继续改造，使用B+树构建索引。B+树和B树最主要的区别在于非叶子节点是否存储数据的问题

• B树：非叶子节点和叶子节点都会存储数据。

• B+树：只有叶子节点才会存储数据，非叶子节点至存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

• InnoDB 的 B+Tree 索引分为主索引和辅助索引。主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

• 辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找，这个过程也被称作回表。

B+树数据结构

B+树的最底层叶子节点包含了所有的索引项。从图上可以看到，B+树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。

所以在需要查询数据的情况下每次的磁盘的IO跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，放索引的磁盘块锁存放的索引数量是会跟这增加的，相对于B树来说，B+树的树高理论上情况下是比B树要矮的。

也存在索引覆盖查询的情况，在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。

举个例子：等值查询

假如我们查询值等于9的数据。查询路径磁盘块1->磁盘块2->磁盘块6。

第一次磁盘IO：将磁盘块1加载到内存中，在内存中从头遍历比较，9<15，走左路，到磁盘寻址磁盘块2。

第二次磁盘IO：将磁盘块2加载到内存中，在内存中从头遍历比较，7<9<12，到磁盘中寻址定位到磁盘块6。

第三次磁盘IO：将磁盘块6加载到内存中，在内存中从头遍历比较，在第三个索引中找到9，取出data，如果data存储的行记录，取出data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。（这里需要区分的是在InnoDB中Data存储的为行数据，而MyIsam中存储的是磁盘地址。）

过程如图：

B+树根据索引等值查询过程

范围查询：

假如我们想要查找9和26之间的数据。查找路径是磁盘块1->磁盘块2->磁盘块6->磁盘块7。

首先查找值等于9的数据，将值等于9的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘IO。

查找到15之后，底层的叶子节点是一个有序列表，我们从磁盘块6，键值9开始向后遍历筛选所有符合筛选条件的数据。

第四次磁盘IO：根据磁盘6后继指针到磁盘中寻址定位到磁盘块7，将磁盘7加载到内存中，在内存中从头遍历比较，9<25<26，9<26<=26，将data缓存到结果集。

主键具备唯一性（后面不会有<=26的数据），不需再向后查找，查询终止。将结果集返回给用户。

可以看到B+树可以保证等值和范围查询的快速查找，MySQL的索引就采用了B+树的数据结构。

索引的底层原理

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

聚簇索引

 ---建表
 create table t_emp(id int primary key,name varchar(20),age int);
 ​
 --插入数据
 insert into t_emp values(5,'d',22);
 insert into t_emp values(6,'d',22);
 insert into t_emp values(7,'e',21);
 insert into t_emp values(1,'a',23);
 insert into t_emp values(2,'b',26);
 insert into t_emp values(3,'c',27);
 insert into t_emp values(4,'a',32);
 insert into t_emp values(8,'f',53);
 insert into t_emp values(9,'v',13);
 ​
 --查询
 select * from t_emp;

在插入的过程中，MySQL 会用你指定的主键，在这里是递增主键，维护起一棵 B+树

B+数的几个特点

• 有序：左边节点比右边小

• 自平衡：左右两边数量趋于相等

• 节点分裂：节点在遇到元素数量超过节点容量时，是如何分裂成两个的，这个也是 MySQL 页分裂的原理

为什么上面数据明明没有按顺序插入,为什么查询时却是有顺序呢?  

– 原因是:mysql底层为主键自动创建索引,一定创建索引会进行排序

 – 也就是mysql底层真正存储是这样的  

– 为什么要排序呢?因为排序之后在查询就相对比较快了 如查询 id=3的我只需要按照顺序找到3就行啦(如果没有排序大海捞针,全靠运气😸!)

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

 select * from student where id = 5;

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

有人会说主键不是递增的吗?  那不就可以用二分法来查找？不是的，主键虽然是递增的，但是如果你写入磁盘时，没有去维护有序数组这样一个数据结构（比如你删掉了 4，怎么把 5 往前面挪），那数据在磁盘里依旧是无序的，查找时只能随机查找，而如果你维护了有序数组这样的数据结构，其实也是建了索引，只是建了不一样的数据结构的索引罢了。

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

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

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

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

你要访问磁盘的次数，是由这棵树的层数决定的。为了方便说明，我在文章里举的例子的数据量不会太大，所以用不用索引，性能提升的效果不明显，但是你可以脑补下大数据量的画面。

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

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

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

这个 MySQL 无论如何都会建起来，并且存储有完整行数据的索引，就叫聚簇索引（clustered index）。

二级索引

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

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

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

 create index idx_name on student(name);

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

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

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

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

复合索引

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

 select * 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 进行有规律的存储，你还是得扫描一万行数据。

索引优化

为了进一步提高效率mysql索引又进行了优化  
- 就是基于页的形式进行管理索引  
- 如 查询id=4的 直接先比较页 先去页目录中找,再去 数据目录中找

Mysql的基本存储结构是页(记录都存在页里边)

• 各个数据页可以组成一个双向链表

• 而每个数据页中的记录又可以组成一个单向链表

• – 每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录

• 以其他列(非主键)作为搜索条件：只能从最小记录开始依次遍历单链表中的每条记录。

所以说，如果我们写 select * from user where username=’丙丙’这样没有进行任何优化的sql语句，默认会这样做：

• 定位到记录所在的页

• – 需要遍历双向链表，找到所在的页

• 从所在的页内中查找相应的记录

• – 由于不是根据主键查询，只能遍历所在页的单链表了

很明显，在数据量很大的情况下这样查找会很慢！看起来跟回表有点点像。

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

从上一节中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

1. 非叶子节点只存储键值信息。

2. 所有叶子节点之间都有一个链指针。

3. 数据记录都存放在叶子节点中。

• InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗3）。也就是说一个深度为3的B+Tree索引可以维护103 * 10^3 * 10^3 = 10亿 条记录。

• 实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在24层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要13次磁盘I/O操作。

索引实现

MyIsam索引

以一个简单的user表为例。user表存在两个索引，id列为主键索引，age列为普通索引

CREATE TABLE `user`
(
  `id`       int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) DEFAULT NULL,
  `age`      int(11)     DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE,
  KEY `idx_age` (`age`) USING BTREE
) ENGINE = MyISAM
  AUTO_INCREMENT = 1
  DEFAULT CHARSET = utf8;

MyISAM的数据文件和索引文件是分开存储的。MyISAM使用B+树构建索引树时，叶子节点中存储的键值为索引列的值，数据为索引所在行的磁盘地址。

主键索引

表user的索引存储在索引文件user.MYI中，数据文件存储在数据文件 user.MYD中。

简单分析下查询时的磁盘IO情况：

根据主键等值查询数据：

 select * from user where id = 28;

1. 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）

2. 将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）

3. 检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于30的索引项。（1次磁盘IO）

4. 从索引项中获取磁盘地址，然后到数据文件user.MYD中获取对应整行记录。（1次磁盘IO）

5. 将记录返给客户端。

磁盘IO次数：3次索引检索+记录数据检索。

根据主键范围查询数据：

 select * from user where id between 28 and 47;

1. 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）

2. 将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）

3. 检索到叶节点，将节点加载到内存中遍历比较16<28，18<28，28=28<47。查找到值等于28的索引项。

   根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）

   我们的查询语句时范围查找，需要向后遍历底层叶子链表，直至到达最后一个不满足筛选条件。

4. 向后遍历底层叶子链表，将下一个节点加载到内存中，遍历比较，28<47=47，根据磁盘地址从数据文件中获取行记录缓存到结果集中。（1次磁盘IO）

5. 最后得到两条符合筛选条件，将查询结果集返给客户端。

磁盘IO次数：4次索引检索+记录数据检索。

备注：以上分析仅供参考，MyISAM在查询时，会将索引节点缓存在MySQL缓存中，而数据缓存依赖于操作系统自身的缓存，所以并不是每次都是走的磁盘，这里只是为了分析索引的使用过程。

辅助索引

在 MyISAM 中,辅助索引和主键索引的结构是一样的，没有任何区别，叶子节点的数据存储的都是行记录的磁盘地址。只是主键索引的键值是唯一的，而辅助索引的键值可以重复。

查询数据时，由于辅助索引的键值不唯一，可能存在多个拥有相同的记录，所以即使是等值查询，也需要按照范围查询的方式在辅助索引树中检索数据。

InnoDB索引

主键索引（聚簇索引）

每个InnoDB表都有一个聚簇索引 ，聚簇索引使用B+树构建，叶子节点存储的数据是整行记录。一般情况下，聚簇索引等同于主键索引，当一个表没有创建主键索引时，InnoDB会自动创建一个ROWID字段来构建聚簇索引。InnoDB创建索引的具体规则如下：

1. 在表上定义主键PRIMARY KEY，InnoDB将主键索引用作聚簇索引。

2. 如果表没有定义主键，InnoDB会选择第一个不为NULL的唯一索引列用作聚簇索引。

3. 如果以上两个都没有，InnoDB 会使用一个6 字节长整型的隐式字段 ROWID字段构建聚簇索引。该ROWID字段会在插入新行时自动递增。

除聚簇索引之外的所有索引都称为辅助索引。在中InnoDB，辅助索引中的叶子节点存储的数据是该行的主键值都。在检索时，InnoDB使用此主键值在聚簇索引中搜索行记录。

这里以user_innodb为例，user_innodb的id列为主键，age列为普通索引。

 CREATE TABLE `user_innodb`
 (
   `id`       int(11) NOT NULL AUTO_INCREMENT,
   `username` varchar(20) DEFAULT NULL,
   `age`      int(11)     DEFAULT NULL,
   PRIMARY KEY (`id`) USING BTREE,
   KEY `idx_age` (`age`) USING BTREE
 ) ENGINE = InnoDB;

InnoDB的数据和索引存储在一个文件t_user_innodb.ibd中。InnoDB的数据组织方式，是聚簇索引。

主键索引的叶子节点会存储数据行，辅助索引只会存储主键值。

等值查询数据：

 select * from user_innodb where id = 28;

1. 先在主键树中从根节点开始检索，将根节点加载到内存，比较28<75，走左路。（1次磁盘IO）

   将左子树节点加载到内存中，比较16<28<47，向下检索。（1次磁盘IO）

   检索到叶节点，将节点加载到内存中遍历，比较16<28，18<28，28=28。查找到值等于28的索引项，直接可以获取整行数据。将改记录返回给客户端。（1次磁盘IO）

   磁盘IO数量：3次。

   

辅助索引

辅助索引也称为二级索引，索引中除了存储索引列外，还存储了主键id，MySQL会自动在辅助索引的最后添加上主键id

除聚簇索引之外的所有索引都称为辅助索引，InnoDB的辅助索引只会存储主键值而非磁盘地址。

以表user_innodb的age列为例，age索引的索引结果如下图。

底层叶子节点的按照（age，id）的顺序排序，先按照age列从小到大排序，age列相同时按照id列从小到大排序。

使用辅助索引需要检索两遍索引：首先检索辅助索引获得主键，然后使用主键到主索引中检索获得记录。

画图分析等值查询的情况：

 select * from t_user_innodb where age=19;

根据在辅助索引树中获取的主键id，到主键索引树检索数据的过程称为回表查询。

回表大概就是我们有个主键为ID的索引，和一个普通name字段的索引，我们在普通字段上搜索：

sql select * from table where name = ‘丙丙’

执行的流程是先查询到name索引上的“丙丙”，然后找到他的id是2，最后去主键索引，找到id为2对应的值。

回到主键索引树搜索的过程，就是回表。不过也有方法避免回表，那就是覆盖索引。

磁盘IO数：辅助索引3次+获取记录回表3次

组合索引

还是以自己创建的一个表为例：表 abc_innodb，id为主键索引，创建了一个联合索引idx_abc(a,b,c)。

 CREATE TABLE `abc_innodb`
 (
   `id` int(11) NOT NULL AUTO_INCREMENT,
   `a`  int(11)     DEFAULT NULL,
   `b`  int(11)     DEFAULT NULL,
   `c`  varchar(10) DEFAULT NULL,
   `d`  varchar(10) DEFAULT NULL,
   PRIMARY KEY (`id`) USING BTREE,
   KEY `idx_abc` (`a`, `b`, `c`)
 ) ENGINE = InnoDB;

select * from abc_innodb order by a, b, c, id;

组合索引的数据结构：

组合索引的查询过程：

 select * from abc_innodb where a = 13 and b = 16 and c = 4;

最左匹配原则：

最左前缀匹配原则和联合索引的索引存储结构和检索方式是有关系的。

在组合索引树中，最底层的叶子节点按照第一列a列从左到右递增排列，但是b列和c列是无序的，b列只有在a列值相等的情况下小范围内递增有序，而c列只能在a，b两列相等的情况下小范围内递增有序。

就像上面的查询，B+树会先比较a列来确定下一步应该搜索的方向，往左还是往右。如果a列相同再比较b列。但是如果查询条件没有a列，B+树就不知道第一步应该从哪个节点查起。

可以说创建的idx_abc(a,b,c)索引，相当于创建了(a)、（a,b）（a,b,c）三个索引。、

组合索引的最左前缀匹配原则：使用组合索引查询时，mysql会一直向右匹配直至遇到范围查询(>、<、between、like)就停止匹配。

覆盖索引并不是说是索引结构，覆盖索引是一种很常用的优化手段。*因为在使用辅助索引的时候，我们只可以拿到主键值，相当于获取数据还需要再根据主键查询主键索引再获取到数据。但是试想下这么一种情况，在上面abc_innodb表中的组合索引查询时，如果我只需要abc字段的，那是不是意味着我们查询到组合索引的叶子节点就可以直接返回了，而不需要回表。这种情况就是*覆盖索引。

刚才我们是 select * ，查询所有的，我们如果只查询ID那，其实在Name字段的索引上就已经有了，那就不需要回表了。

覆盖索引可以减少树的搜索次数，提升性能，他也是我们在实际开发过程中经常用来优化查询效率的手段。

很多联合索引的建立，就是为了支持覆盖索引，特定的业务能极大的提升效率。

可以看一下执行计划：

覆盖索引的情况：

使用到覆盖索引

未使用到覆盖索引：