GoGoCoder底层原理分析--聚集索引和辅助索引查询过程
经典问题
Q：说一下聚集索引和辅助索引
A：聚集索引和辅助索引都是InnoDB存储引擎索引组织表的实现形式。
-
聚集索引：
索引键为单一主键
叶子节点存储：记录的所有列信息，包含整张表的行记录数据
相当于按照表的主键构造一棵B+树。
-
辅助索引：
索引键为非单一主键（除了聚集索引外，都是辅助索引）
叶子节点存储：索引键值+主键值，不包含整张表的全部数据。
查询辅助索引，在叶子节点获取索引键值+主键值后，判断是否满足查询所需列信息，不满足则需用刚获取的主键值，再查询聚集索引，获取该记录的全部信息，所以辅助索引又名为二级索引。
追根溯源
一、InnoDB逻辑存储结构
-
表空间：
InnoDB存储引擎的最高层，所有的数据都存放在表空间中。默认所有数据均存放在ibdata1共享表空间。如果启用了参数innodb_file_per_table,则每张表内的数据单独存放到一个表空间。
-
段：
表空间由数据段组成，常见的段有数据段、索引段、回滚段等。InnoDB 对段的管理都是由引擎自身完成的，对DBA来说是透明的。因此，不需对其过多关心。
-
区：
区是由连续页组成的，且区大小一般固定为1MB。InnoDB存储引擎默认页大小为16KB，也即一个区为连续的64个页。由于压缩页的引入，页大小可以设置为2KB、4KB、8KB，但是区大小还是固定1MB，只是区内对应的页大小不同。
-
页：
页是InnoDB磁盘管理的最小单位。而且InnoDB存储引擎表是索引组织的，索引数据结构采用B+ 树，实际存储过程中，无论叶子节点还是非叶子节点都是对应磁盘中的一个页。（注：表如果没有设置主键索引，InnoDB会自动给表建立一个隐式主键，并为其添加聚集索引。）
叶子节点（Level=0）
聚集索引中存储行记录所有列值
辅助索引中存储索引列值+主键值
非叶子节点（Level>=1）
聚集索引中存储主键值+(Level-1)索引所在页偏移地址
辅助索引中存储索引列值+(Level-1)索引所在页偏移地址
补充说明页结构中的Page Directory（页目录）：
页中的Page Directory（页目录），存放了记录的相对位置，这些指向记录的指针称为Slot槽，槽倒序排列，同时一个槽中可能包含多条记录，所以这些槽构成稀疏目录。
如上图，要在页内查询索引值为"c"的记录，首先在Page Directory 中进行二分查找定位c所在的粗略位置，然后在槽内进行顺序查找访问到索引值“c”的内容。
注：页内还存在其他File Header、Page Header、Infimum、Supremum Records 等，详细请参考《MySql技术内幕》第二版4.4节。
行：
1. 首先会获取索引ID，然后根据索引ID，遍历表空间中的索引页，先找到该索引Level最高的非叶子节点(页)
2. 在索引页中查询定位到下一级(Level-1)非叶子节点所在页地址，循环1,2步骤，最后到达Level=0的数据页。
3. 在Level=0的数据页中，聚集索引存储行记录的所有列值，选择查询语句相关的列返回结果即可。而辅助索引存储当前索引列值+主键值，如果存储的信息无法覆盖查询语句相关信息列，则需根据新得到的主键值，再通过聚集索引树重新查询。
二、聚集索引与非聚集索引查询过程详细分析
1. 表信息如下：CREATE TABLE t ( id INT NOT NULL, name VARCHAR(7000), age INT, PRIMARY KEY (ID),/*主键索引（聚集索引）*/ KEY idx_name(NAME)/*辅助索引*/ )ENGINE=INNODB;
2. 聚集索引查询过程
从聚簇索引树查询ID = 4 的记录(select * from t where id = 4)：
1、InnoDB首先会获取到聚集索引的ID,此处假设为idx;
2、然后去磁盘查询page_index_id = idx且level最高的索引页(此处Level=2，Page Offset：00 03)
3、在该索引页内结合Page Directory中的slots进行二分查找，然后在Slot内顺序查找后，获得ID=4所需查询的下一级索引页(Level = 1)的页偏移Page Offset : 00 05
4、同样到Level=1的索引页，同样通过二分+顺序查找的方法，获得ID=4所需查询的数据页(Level = 0)偏移地址 Page Offset ：00 0C
5、在Level = 0 的数据页中，继续二分+顺序查找，定位ID=4的行记录，读取出来ID= 4 name = "d"
总的来说，相当于对聚集索引树进行了三次页级的遍历查找。
3. 辅助索引查询过程
从idx_name辅助索引树查name = “d” 记录(select * from t where name = "d"):
1、InnoDB首先会获取到辅助索引idx_name的ID。
2、然后去磁盘查询page_index_id = idx_name且level最高的索引页(此处Level=2，Page Offset：00 04)
3、在该索引页内，二分+顺序查找，获得name = “d” 所需查询的下一级索引页(Level = 1)的页偏移Page Offset : 00 07
4、同样在Level=1的索引页内，二分+顺序查找，获得ID=4所需查询的数据页(Level = 0)偏移地址 Page Offset ：00 0A
5、在Level = 0 的数据页中，二分+顺序查找，定位name = “d” 的行记录，获取主键值ID= 4，此时发现 select * 为获取记录的所有列，当前索引中只有ID 与 name 信息，不满足，因此，开始所谓的“回表”查的阶段，通过ID = 4 去聚簇索引位置去查询，最终拿到name = “d”,ID=4的所有列值。
总的来说，相当于对首先对索引树进行了三次页级查找，再对聚集索引树进行了三次页级查找，共计6次查找。
总结：
带索引的查询可以通过查询索引树，快速定位到记录所在磁盘位置，进而减少查询到结果记录的时间。
带索引查询分为：聚集索引查询与辅助索引查询
聚集索引：直接从聚集索引的Level最高索引节点开始查询，最终即可在Level=0的数据页直接获取到所有的行记录结果。
非聚集索引：根据非聚集索引的索引ID，去查询辅助索引的Level最高层根节点，然后在非聚集索引的Level = 0数据页，最多只能获取到索引列+主键列信息，如果能够覆盖查询语句所需的查询结果，则直接返回即可，如果不能满足，则需要拿着主键值，去聚簇索引表再次查询，最终获取到记录所有列信息，从而返回结果集。
三、思考延伸:
针对上述InnoDB逻辑存储结构，以及聚簇索引与非聚簇索引的查找规则，在建立、选择索引方面梳理了以下注意点：
1. 主键避免使用很长字段
主键尽量避免使用很长字段。因为聚集索引中的非叶子节点主要为主键值，如果主键字段很大，节点(索引页)容纳主键个数会变少，增加树深，增加查询所需磁盘IO次数。 同样，也会使非聚簇索引的叶子节点数变多，间接增加辅助索引的树深，增加辅助索引查询的开销。3、注意索引区分度
1、2均说明应当避免使用长字段，但是也不能盲目的缩小索引字段的长度，还要注意索引的区分度（0,1]，越趋近于1，该列做索引越有价值。如果区分度为0，查询退化为顺序查询，索引便成了累赘，而且还额外添加了查询索引表的过程，降低增删改的效率。 感兴趣可以了解InnoDB中的cardinality,代表区分度，但是该值并不是代表实时的区分度，具体规则可自行百度。4、尽量减少回表次数（查完辅助索引，再查聚集索引） 通过借助联合索引，增加索引列数，实现索引覆盖（索引列能够满足业务常用查询需求），进而尽量避免回表查询。5、不要建立太多的索引
增删改过程中也会更新索引表，因此，不必要的索引将会降低这些操作的执行时间，降低增删改的效率。小问题：
如果索引叶子节点，内容为ID: 1,2,3,4,5,6,7 进行分裂，则会分裂为 123 和 4567 两个节点。如果主键是自增主键，则继续插入数据，ID为123所在的索引页，另外一半的内存一直是空闲的，后续 4567 所在索引页也会继续分裂，进而造成更大的内存浪费，请问InnoDB是如何处理的？
注：该问题会在回复中进行解答。
投递哔哩哔哩等公司10个岗位 >
