InnoDB索引原理

阅读本文章前，需要先熟悉InnoDB的页结构

众所周知：
InnoDB的索引是B+树；
聚簇索引的叶子节点存的是真实的数据行；
二级索引（也叫辅助索引）的叶子节点存放的是索引列+主键值；
聚簇索引和二级索引的非叶子节点，存的都是索引列的值+页号（实际上二级索引的非叶子节点也会存主键值，下面会解释）

那么这些节点的结构具体是什么样子呢？

实际上，B+树上的每一个节点（叶子节点或非叶子节点），就是一个索引页（默认大小16k）。

不同页之间，需要满足上一个页的索引列值全都不大于下一个页的索引列值，为了维持这个条件始终成立，如果有增删改查操作，更新B+树的时候，可能需要跨页移动一些记录，这个过程称为页分裂。

假设现在表里有1000行记录，主键id从1到1000，假设每个页可以存100行记录，那么总共会有10个叶子节点（也就是10个页），假设这10个页编号1到10（实际上B+树的页编号不会这么有序，因此逻辑上相邻的页在磁盘上不一定相邻，这里为了方便理解做了简化）。

对于非叶子节点，里面同样是若干行记录，这些记录分若干组，每组有一个槽。与叶子节点不同的是，非叶子节点的每一行记录，对应了下一层的一个页，这行记录存了该页的最小索引列值，以及页号。

假设每个非叶子节点最多存5行记录，10个叶子节点需要2个非叶子节点（第二层）。
第2层的2个非叶子节点需要一个根节点来做索引。

image.png

假设现在要查找id = 160的记录，首先会到根节点的页目录做二分查找，由于501 > 160，因此id = 160在页11，这一页的最小索引列值分别为1、101、201、301、401，分别对应1、2、3、4、5这5个页号，因此id = 300在页号为2的页。

页号为2的页，即第2个叶子节点，存了id为101到200这100行记录，这100行记录同样会分组，每组对应一个槽。

在第2个叶子节点的页目录对槽做二分查找，找到对应分组，然后遍历单向链表，就可以找到id = 160的记录。

假设建了二级索引，那么非叶子节点上的每一行记录，会存所有索引列的值+主键以及页号，但是为什么要存主键值呢？

假设现在对“姓名”列建了索引，有相当多的人都叫张三，第一个叶子节点所有姓名都是张三，第二个叶子节点的最小姓名，也是张三，也就是说，第一个、第二个叶子节点的最小索引列值，都是张三。

假设有一个非叶子节点，其中有两行记录，分别指向第一、第二个叶子节点，现在又插入一行姓名为张三的记录，更新索引的时候，这一行记录是要插到第一个、还是第二个叶子节点呢？无法判断。

因此，需要保证B+树的同一层非叶子节点，除了页号以外，其他信息唯一，因此二级索引的非叶子节点，都会存索引列值+主键+页号，联合索引同理。

因此，假如建了c1列的二级索引，实际上跟建(c1, id)的联合索引是一样的，假如建了(c1, c2)的联合索引，跟建(c1, c2, id)的联合索引是一样的。

即使对某个UNIQUE列建了索引，非叶子节点的记录还是会存主键值，一是UNIQUE属性的列可能有多个NULL值，二是因为MVCC。