InnoDB存储引擎（五）索引与算法

绝地灬酷狼 2023-06-06 07:47 12阅读 0赞

**目录**

5.1 概述

5.2 数据结构与算法

5.2.1 二分查找法

5.2.2 二叉查找树和平衡二叉树

5.2.3 B+树

5.3 B+树索引

5.3.1 聚集索引和非聚集索引

5.3.2 B+树索引的使用

联合索引

覆盖索引

优化

5.4 B+树索引的分裂

5.5 Cardinality值

5.6 全文索引

--------------------

# 5.1 概述 #

InnoDB支持以下几种常见的索引：

*  B+树索引
 *  全文索引
 *  哈希索引，自适应的，不能人为干预是否在一张表中生成哈希索引

注意：

B+树索引并不能找到一个给定键值的具体行，能找到的只是被查找数据所在的页。然后数据库通过把页读入导内存，再在内存中进行查找，最后得到要查找的数据。

# 5.2 数据结构与算法 #

粗略的介绍一下，具体的请查看相关书籍。

## 5.2.1 二分查找法 ##

用来查找一组**有序的**记录数组中的某一记录。

如有5、10、19、21、31、37、42、48、50、52这10个数，现要从这10个数中查找48这条记录，其查找过程如下：

![20191010112513909.png][]

每页Page Directory中的槽是按照主键的顺序进行存放的，对应某一条具体记录的查询是通过对Page Directory进行二分查找得到的（槽前面的博客介绍过）。

## 5.2.2 二叉查找树和平衡二叉树 ##

B+树是通过二叉查找树，再由平衡二叉树，B树演化而来的。

二叉查找树的特点：左子树的键值总是小于根的键值，右子树的键值总是大于根的键值，如图5-2。同时，二叉树可以任意构造，所以它可能会按照5-3的方式建立二叉树，这时该二叉树几乎退化成链表，查询效率就降低了。

![20191010112544164.png][]![20191010112602726.png][]

为解决这种情况，引入了平衡二叉树，即：首先满足二叉查找树的定义，其次必须满足任何节点的两个子树的高度最大差为1。要满足这个条件，就必须对二叉树进行左旋或者右旋操作来使树保持平衡，有些时候可能需要旋转多次，如图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70][]

## 5.2.3 B+树 ##

首先来看一棵由数字1-7组成的B+树。

![20191010112644591.png][]

可以看到B+树有以下特点：

*  所有记录都在叶子节点上，并且是顺序存放的
 *  非叶子节点冗余了部分叶子节点的数据
 *  节点之间通过链表进行链接
 *  一个节点可以存储多个值

B+树的插入和删除操作是通过对B+树的**拆分或者合并**来保持树的平衡，由于篇幅有限，这里不进行详细说明，感兴趣的可以查看《MySQL技术内幕 InnoDB存储引擎 第2版》。

# 5.3 B+树索引 #

B+树索引的本质就是B+树在数据库中的实现，在数据库中，B+树的高度都一般在2~4层，也就是说查找某一键值的行记录最多只需要2到4次IO。当前一般机械磁盘每秒至少可以做100次IO，2~4次的IO意味这查询时间只需0.02~0.04秒。

数据库中的B+树索引可以分为聚集索引(clustered inex)和辅助索引(secondary index) ，但是不管是聚集还是辅助的索引，其内部都是B+树，即高度平衡的，叶子节点存放着所有的数据。聚集索引与辅助索引不同的是，叶子节点存放的是否是一整行的信息。

## 5.3.1 聚集索引和非聚集索引 ##

InnoDB存储引擎表是索引组织表，表中数据是按照主键顺序存放的。聚集索引就是按照每张表的主键构造一棵B+树，同时**叶子节点存放的即为整张表的行记录数据**，也将聚集索引的叶子节点称为数据页。每个数据页都通过一个双向链表来进行链接。

非聚集索引（也称辅助索引），其叶子节点并不包含行记录的全部数据，存放的仅是主键和索引键。创建的索引，如联合索引、唯一索引等，都属于非聚簇索引。

其关系如下图，图片来自于网络。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 1][]

当通过辅助索引来查找数据时，innodb存储引擎会通过辅助索引叶子节点获得主键索引的主键，然后再通过主键索引找到完整的行记录。

例如在一棵高度为3的辅助索引树中查找数据，那需要对这颗辅助索引树进行3次IO找到指定主键，如果聚集索引树的高度同样为3，那么还需要对聚集索引树进行3次查找，最终找到一个完整的行数据所在的页，因此一共需要6次IO访问来得到最终的数据页。

## 5.3.2 B+树索引的使用 ##

### 联合索引 ###

联合索引指对表上的多个列进行索引。

首先创建一张表，并且索引列为(a, b)

create table t (
    	a int,
    	b int,
    	primary key (a),
    	key idx_a_b (a, b)
    )engine=innodb;

向表中插入一些数据，先看一下联合索引内部的结构。可以看出数据按(a, b)的顺序进行了存放，a的顺序：1,1,2,2,3,3，b的顺序1,2,1,4,1,2，乍看是无序的，但当a值相同时，b是有序的。

![20191010112803696.png][]

查询的时候，就涉及到了一个非常重要的知识点：**最佳左前缀**

例如查询：

1.  `select * from t where a = 1 and b = 2`，a有序，b有序，显然可以使用(a, b)这个联合索引
2.  `select * from t where a=1`，a有序，也可以使用(a, b)索引
3.  `select * from t where b = 3`，b整体上是无序的，所以用不到(a, b)索引

注意：

因为我们查询的是所有字段，而辅助索引叶子节点仅存储了**索引值和主键值**，即`(primary key1， primary key2，..., key1, key2, ...)`，这个时候需要通过主键id回表查询，补充字段。在某些情况下可以使用**覆盖索引**来避免回表查询。

### 覆盖索引 ###

覆盖索引，即从辅助索引中就可以得到查询的记录，而不需要查询聚集索引中的记录。好处是覆盖索引不包含整行记录的所有信息，故其大小要远小于聚集索引，因此可以减少大量的IO操作。

覆盖索引叶子节点存放的数据为`(primary key1， primary key2，..., key1, key2, ...)`，因此，以下查询都可以仅使用一次辅助联合索引来完成查询。

select key2 from table where key1 = XXX;
    select primary key2, key2 from table where key1 = XXX;
    select primary key1, key2 from table where key1 = XXX;
    select primary key2, primary key2, key2 from table where key1 = XXX;

### 优化 ###

1.  索引提示
    
     *  **USE INDEX**，告诉优化器可以选择该索引，实际上优化器还是会根据自己的判断进行选择。如：`select * from t USE INDEX(a) where a = 1 and b = 2;`
     *  **FORCE INDEX**，强制指定某个索引来完成查询。如：`select * from t FORCE INDEX(a) where a = 1 and b = 2;`
2.  **Multi-Range Read（MRR）**，根据索引进行查询优化，减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，可适应于range，ref，eq\_ref类型的访问。在查询辅助索引时，首先根据得到的查询结果，按照主键进行排序，并按照主键排序的顺序进行书签查找。
3.  **Index Condition Pushdown（ICP）**，根据索引进行查询优化，当进行索引查询时，首先根据索引来查找记录，然后再根据where条件来过滤数据

# 5.4 B+树索引的分裂 #

B+树索引页的分裂并不总是从页的中间开始，若插入是顺序的，从中间记录分裂会导致页空间的浪费。若插入是随机的，则取中间记录作为分裂点的记录。

如下图，分裂点为插入记录本身，向右分裂后仅插入记录本身，这在自增插入时是普遍存在的一种情况。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 2][]

# 5.5 Cardinality值 #

还是之前的表t，通过`show index from t`来查看表中索引信息。

mysql> show index from t\G;
    *************************** 1. row ***************************
            Table: t
       Non_unique: 0
         Key_name: PRIMARY
     Seq_in_index: 1
      Column_name: a
        Collation: A
      Cardinality: 0
         Sub_part: NULL
           Packed: NULL
             Null: 
       Index_type: BTREE
          Comment: 
    Index_comment: 
    *************************** 2. row ***************************
            Table: t
       Non_unique: 1
         Key_name: idx_a_b
     Seq_in_index: 1
      Column_name: a
        Collation: A
      Cardinality: 0
         Sub_part: NULL
           Packed: NULL
             Null: 
       Index_type: BTREE
          Comment: 
    Index_comment: 
    *************************** 3. row ***************************
            Table: t
       Non_unique: 1
         Key_name: idx_a_b
     Seq_in_index: 2
      Column_name: b
        Collation: A
      Cardinality: 0
         Sub_part: NULL
           Packed: NULL
             Null: YES
       Index_type: BTREE
          Comment: 
    Index_comment: 
    3 rows in set (0.00 sec)

Cardinality表示选择性，建立索引的前提是列中的数据都是高选择性的，因此该值非常关键，表示索引中不重复记录数量的**预估值**，在实际应用中，该值应尽可能地接近1，如果非常小，那么用户需要考虑是否还有必要创建这个索引。

如何对Cardinality进行统计呢？

如果每次索引在发生操作时就对其进行Cardinality的统计，那么将会给数据库带来很大的负担。所以，数据库对于Cardinality的统计都是通过采样的方法来完成的。

**采样过程如下：**

1.  取得B+树索引中叶子节点的数量，记为A
2.  随机取得B+树索引中的8个叶子节点。统计每个页不同记录的个数，即为P1，P2，...，P8
3.  根据采样信息给出Cardinality的预估值：Cardinality=(P1+P2+...+P8)\*A/8

**Cardinality更新策略为：**

1.  表中1/16的数据已发生过变化
2.  某一行发生变化的次数大于2,000,000
3.  当执行SQL语句ANALYZE TABLE、SHOW TABLE STATUS、SHOW INDEX以及访问INFORMATION\_ SCHEMA架构下的表TABLES和STATISTICS时，会去更新Cardinality值。若表中的数据量非常大，并且表中存在多个辅助索引时，执行上述这些操作可能会非常慢。虽然用户可能并不希望去更新Cardinality值。

# 5.6 全文索引 #

全文检索(Full-Text Search)是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。

通过倒排索引来实现

[20191010112513909.png]: /images/20230601/04a48393f4e047858a99da0a85e02058.png
[20191010112544164.png]: https://img-blog.csdnimg.cn/20191010112544164.png
[20191010112602726.png]: /images/20230601/4d85e738f13d4f3dbfe585d725409f9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70]: /images/20230601/a15af1e779b84452bdd164f4787d3e06.png
[20191010112644591.png]: /images/20230601/105c6bdea765464394f902dd70c1bff2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 1]: /images/20230601/9e55f6f946364182a6856877d12a9b8f.png
[20191010112803696.png]: /images/20230601/471c8449cde841fab167a116e99d1c84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTQxNjE5_size_16_color_FFFFFF_t_70 2]: /images/20230601/e16c466e1c254cf3be1302e11f11ac18.png