MySQL学习（七）：Innodb存储引擎索引的实现原理

Dear 丶 2022-02-23 10:16 298阅读 0赞

### 概述 ###

*  在数据库当中，索引就跟书的目录一样用来加快数据的查找速度，对于一个SQL查询操作，根据索引快速过滤掉不符合要求的数据并定位到符合要求的数据，从而不需要扫描整个表来获取所需的数据。
 *  在innodb存储引擎中，主要是基于B+树来实现索引，在非叶子节点存放索引关键字（**所以如果建了多个独立索引，则对应多棵B+树，这样对于非主键索引，则叶子节点存放的是主键索引的主键值，需要通过二次查找主键索引所在的B+树获取对应的数据行，这也叫回表查询**），在叶子节点存放数据记录（此时为主键索引或者说是聚簇索引，即数据行和索引存放在一起的索引）或者主键索引中的主键值（此时为非聚簇索引），所有的数据记录都在同一层，叶子节点，即数据记录直接之间通过指针相连，构成一个双向链表，从而可以方便地遍历到所有的或者某一范围的数据记录。

### B树，B+树 ###

*  B树和B+树都是多路平衡搜索树，通过在每个节点存放更多的关键字和通过旋转、分裂操作来保持树的平衡来降低树的高度，从而减少数据检索的磁盘访问量。
 *  B+树相对于B树的一个主要的不同点是B+的叶子节点通过指针前后相连，具体为通过双向链表来前后相连，所以非常适合执行范围查找。具体可以参考：  
    [数据结构-树（三）：多路搜索树B树、B+树  
    ][-_B_B_]
 *  innodb存储引擎的聚簇和非聚簇索引都是基于B+树实现的。

### 主键索引 ###

*  innodb存储引擎使用主键索引作为表的聚簇索引，聚簇索引的特点是非叶子节点存放主键作为查找关键字，叶子节点存放实际的数据记录本身（也称为数据页），从左到右以关键字的顺序，存放数据记录，故聚簇索引其实就是数据存放的方式，所以每个表只能存在一个聚簇索引，innodb存储引擎的数据表也称为索引组织表。结构如下：（图片引自《MySQL技术内幕：Innodb存储引擎》）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]
 *  在查询当中，如果是通过主键来查找数据，即使用explain分析SQL的key显示PRIMARY时，查找效率是最高的，因为叶子节点存放的就是数据记录本身，所有可以直接返回，而不需要像非聚簇索引一样需要通过额外回表查询（在主键索引中）获取数据记录。
 *  其次是对于ORDER BY排序操作，不管是正序ASC还是逆序DESC，如果ORDER BY的列是主键，则由于主键索引对应的B+树本身是有序的， 故存储引擎返回的数据就是已经根据主键有序的，不需要在MySQL服务器层再进行排序，提高了性能，如果通过explain分析SQL时，extra显示Using filesort，则说明需要在MySQL服务器层进行排序，此时可能需要使用临时表或者外部文件排序，这种情况一般需要想办法优化。
 *  对于基于主键的范围查找，由于聚簇索引的叶子节点已经根据主键的顺序，使用双向链表进行了相连，故可以快速找到某一范围的数据记录。

### 辅助索引 ###

*  辅助索引也称为二级索引，是一种非聚簇索引，一般是为了提高某些查询的效率而设计的，即使用该索引列查询时，通过辅助索引来避免全表扫描。由于辅助索引不是聚簇索引，每个表可以存在多个辅助索引，结构如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]
 *  辅助索引的非叶子节存放索引列的关键字，叶子节点存放对应聚簇索引（或者说是主键索引）的主键值。即通过辅助索引定位到需要的数据后，如果不能通过索引覆盖所需列，即通过该辅助索引列来获取该次查询所需的所有数据列，则需要通过该对应聚簇索引的主键值定位到在聚簇索引中的主键，然后再通过该主键值在聚簇索引中找到对应的叶子页，从而获取到对应的数据记录，所以整个过程涉及到先在辅助索引中查找，再在聚簇索引（即主键索引）中查找（回表查询）两个过程。
 *  举个例子：
    
    1.  辅助索引对应的B+树的高度为3，则需要3次磁盘IO来定位到叶子节点，其中叶子节点包含对应聚簇索引的某个主键值；
    2.  然后通过叶子节点的对应聚簇索引的主键值，在聚簇索引中找到对应的数据记录，即如果聚簇索引对应的B+树高度也是3，则也需要3次磁盘IO来定位到聚簇索引的叶子页，从而在该叶子页中获取实际的数据记录。
 *  以上过程总共需要进行6次磁盘IO。故如果需要回表查询的数据行较多，则所需的磁盘IO将会成倍增加，查询性能会下降。所以需要在过滤程度高，即重复数据少的列来建立辅助索引。

##### Cardinality：索引列的数据重复度 #####

##### 覆盖索引 #####

*  由于回表查询开销较大，故为了减少回表查询的次数，可以在辅助索引中增加查询所需要的所有列，如使用联合索引，这样可以从辅助索引中获取查询所需的所有数据（由于辅助索引的叶子页包含主键值，即使索引没有该主键值，如果只需返回主键值和索引列，则也会使用覆盖索引），不需要回表查询完整的数据行，从而提高性能，这种机制称为覆盖索引。
 *  当使用explain分析查询SQL时，如果extra显示 using index 则说明使用了覆盖索引返回数据，该查询性能较高。
 *  由于索引的存在会增加更新数据的开销，即更新数据时，如增加和删除数据行，需要通过更新对应的辅助索引，故在具体设计时，需要在两者之间取个折中。

##### 联合索引与最左前戳匹配 #####

*  联合索引是使用多个列作为索引，如（a,b,c)，表示使用a，b，c三个列来作为索引，由B+树的特征可知，索引都是需要符合最左前戳匹配的，故其实相当于建立a，（a,b），(a,b,c)三个索引。
 *  所以在设计联合索引时，除了需要考虑是否可以优化为覆盖索引外，还需要考虑多个列的顺序，一般的经验是：查询频率最高，过滤性最好（重复值较少)的列在前，即左边。

###### 联合索引优化排序order by ######

[-_B_B_]: https://blog.csdn.net/u010013573/article/details/88930632
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70]: /images/20220223/0ab62ee2873a4d9facb54dfb9dcca287.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTAwMTM1NzM_size_16_color_FFFFFF_t_70 1]: /images/20220223/73b8bfac59894f57946759c1150cab17.png