经典问题

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. 表信息如下：
1
2
3
4
5
6
7
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、不要建立太多的索引

        增删改过程中也会更新索引表，因此，不必要的索引将会降低这些操作的执行时间，降低增删改的效率。