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节。

行:

    InnoDB存储引擎是面向列的,数据是按照行进行存放的,除了用户插入的行记录相关列外,还会存放事务ID,回滚指针,这两个跟MVCC(多版本并发控制)相关联,具体MVCC后续会单独开专题介绍。

 根据InnoDB逻辑存储结构图中右半侧可以出,带索引的查询请求,根据查询条件是否为单一主键区分为聚集索引查询和辅助索引查询,每个索引都有自己的索引ID,查询过程如下:

    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次数。    同样,也会使非聚簇索引的叶子节点数变多,间接增加辅助索引的树深,增加辅助索引查询的开销。
    2、辅助索引列也尽量避免长字段    
        原因同1。但是,如不可避免使用长字段,则可以根据最左前缀原则,在保证很好区分度的情况下,截取前n字节,建立索引。

    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是如何处理的?

注:该问题会在回复中进行解答。



#学习路径#
全部评论
点赞 回复 分享
发布于 2021-09-11 14:05

相关推荐

不愿透露姓名的神秘牛友
11-27 10:28
点赞 评论 收藏
分享
11-11 14:21
西京学院 C++
无敌混子大王:首先一点,不管学校层次怎么样,教育经历放在第一页靠上位置,第一页看不到教育经历,hr基本直接扔掉了
点赞 评论 收藏
分享
10-28 14:42
门头沟学院 Java
watermelon1124:因为嵌入式炸了
点赞 评论 收藏
分享
评论
2
10
分享
牛客网
牛客企业服务