【MySQL】第十一篇：MySQL索引原理

Myth丶恋晨 2022-11-25 10:20 112阅读 0赞

工具类网站：[数据结构模拟][Link 1]

# 一、索引是什么 #

索引是帮助MySQL、Kafka、ES等组件高效获取数据的数据结构。本文针对的是MySQL的索引

# 二、索引能干什么 #

提高数据查询、排序的效率。

索引：排好序的快速查找数据结构！索引会影响 where 后面的查找，和 order by 后面的排序。

# 三、索引的分类 #

*  从数据结构上来划分：Hash索引，BTree索引（B-Tree或B+Tree索引）
    
     *  描述的是索引存储时保存的形式
 *  从应用层次来分：普通索引，唯一索引，复合索引。
    
     *  普通索引：即一个索引只包含单个列，一个表可以有多个单列索引
     *  唯一索引：索引列的值必须唯一，但允许有空值
     *  复合索引：即一个索引包含多个列
 *  根据中数据的物理顺序与键值的逻辑（索引）顺序关系：聚集索引，非聚集索引。
    
     *  聚簇索引(聚集索引)：并不是一种单独的索引类型，而是一种数据存储方式。具体细节取决于不同的实现，InnoDB的聚簇索引其实就是在同一个结构中保存了B-Tree索引(技术上来说是B+Tree)和数据行。
     *  非聚簇索引：不是聚簇索引，就是非聚簇索引（认真脸）。

# 四、索引数据结构演进 #

索引是一种支持快速查找的数据结构，在运用中往往还要求能够支持顺序查询，而常见的数据结构有很多，比如数组，链表，二叉树，散列表，二叉搜索树，平衡搜索二叉树，红黑树，跳表等。仅仅从数据结构那么为什么选择B+Tree呢？  
首先对于数组，链表这种线性表来说，适合存储数据，而不是查找数据；

## 4.1、哈希索引 ##

哈希（Hash）是一种非常快的查找方法，在一般情况下这种查找的时间复杂度为O（1），即一般仅需要一次查找就能定位到数据。在各种编程语言和数据库中应用广泛，如Java，Python，Redis中都有使用。  
![在这里插入图片描述][20200808101748304.gif]

哈希结构在单条数据的等值查询是性能非常优秀，但是只能用来搜索等值的查询， 对于范围查询，模糊查询（最左前缀原则）都不支持，所以不能很好的支持业务需求； 所以MySQL并没有显式支持Hash索引，而是根据数据的访问频次和模式自动的为热点数据页建立哈希索引，称之为自适应哈希索引。  
并且由于哈希函数的随机性，Hash索引通常都是随机的内存访问，对于缓存不友好，会造成频繁的磁盘IO

## 4.2、二叉查找树(BST)：不平衡 ##

二叉查找树(BST，Binary Search Tree)，也叫二叉排序树，在二叉树的基础上需要满足：任意节点的左子树上所有节点值不大于根节点的值，任意节点的右子树上所有节点值不小于根节点的值。如下是一棵BST：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70]  
当需要快速查找时，将数据存储在BST是一种常见的选择，因为此时查询时间取决于树高，平均时间复杂度是O(logn)。然而，BST可能长歪而变得不平衡，如下图所示，此时BST退化为链表，时间复杂度退化为O(n)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 1]

为了解决这个问题，引入了平衡二叉树。

## 4.3、平衡二叉树(AVL)：旋转耗时 ##

AVL树是严格的平衡二叉树，所有节点的左右子树高度差不能超过1；AVL树查找、插入和删除在平均和最坏情况下都是O(logn)。

AVL实现平衡的关键在于旋转操作：插入和删除可能破坏二叉树的平衡，此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时，最多只需要1次旋转(单旋转或双旋转)；但是当删除数据时，会导致树失衡，AVL需要维护从被删除节点到根节点这条路径上所有节点的平衡，旋转的量级为O(logn)。

![在这里插入图片描述][20200808091924200.gif]  
由于旋转的耗时，AVL树在删除数据时效率很低；在删除操作较多时，维护平衡所需的代价可能高于其带来的好处，因此AVL实际使用并不广泛。

## 4.4、红黑树：树太高 ##

与AVL树相比，红黑树并不追求严格的平衡，而是大致的平衡：只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看，红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一，且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][2020080809273820.gif]  
与AVL树相比，红黑树的查询效率会有所下降，这是因为树的平衡性变差，高度更高。但红黑树的删除效率大大提高了，因为红黑树同时引入了颜色，当插入或删除数据时，只需要进行O(1)次数的旋转以及变色就能保证基本的平衡，不需要像AVL树进行O(lgn)次数的旋转。总的来说，红黑树的统计性能高于AVL。

因此，在实际应用中，AVL树的使用相对较少，而红黑树的使用非常广泛。例如，Java中的TreeMap使用红黑树存储排序键值对；Java8中的HashMap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时，使用链表，当冲突节点较多时，使用红黑树)。

对于数据在内存中的情况（如上述的TreeMap和HashMap），红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况（如MySQL等数据库），红黑树并不擅长，因为红黑树长得还是太高了。当数据在磁盘中时，磁盘IO会成为最大的性能瓶颈，设计的目标应该是尽量减少IO次数；而树的高度越高，增删改查所需要的IO次数也越多，会严重影响性能。

## 4.5、B树：为磁盘而生 ##

B树也称B-树(其中-不是减号)，是为磁盘等辅存设备设计的多路平衡查找树，与二叉树相比，B树的每个非叶节点可以有多个子树。因此，当总节点数量相同时，B树的高度远远小于AVL树和红黑树(B树是一颗“矮胖子”)，磁盘IO次数大大减少。

定义B树最重要的概念是阶数(Order)，对于一颗m阶B树，需要满足以下条件：

*  每个节点最多包含 m 个子节点。
 *  如果根节点包含子节点，则至少包含 2 个子节点；除根节点外，每个非叶节点至少包含 m/2 个子节点。
 *  拥有 k 个子节点的非叶节点将包含 k - 1 条记录。
 *  所有叶节点都在同一层中。  
    可以看出，B树的定义，主要是对非叶结点的子节点数量和记录数量的限制。

下图是一个B树的例子（图片来源）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 3]  
B树的优势除了树高小，还有对访问局部性原理的利用。所谓局部性原理，是指当一个数据被使用时，其附近的数据有较大概率在短时间内被使用。B树将键相近的数据存储在同一个节点，当访问其中某个数据时，数据库会将该整个节点读到缓存中；当它临近的数据紧接着被访问时，可以直接在缓存中读取，无需进行磁盘IO；换句话说，B树的缓存命中率更高。

B树在数据库中有一些应用，如mongodb的索引使用了B树结构。但是在很多数据库应用中，使用的是B树的变种B+树，主要有回下两个原因：

*  由于MySQL索引一般都存储在内存中，如果使用B-Tree作为索引的话，索引和数据存储在一块，分布在各个节点中；而内存资源往往比较宝贵，一定内存的情况下可以存储的索引数量相对有限，毕竟每条数据的大小一般远大于索引列的大小，导致内存使用率不高。
 *  数据查询过程中往往会有顺序查询，而B-Tree和红黑树对于顺序查询并不友好。
 *  B树对范围查询不友好

## 4.6、B+树 ##

B+树也是多路平衡查找树，其与B树的区别主要在于：

*  B树中每个节点（包括叶节点和非叶节点）都存储真实的数据，B+树中只有叶子节点存储真实的数据，非叶节点只存储键。在MySQL中，这里所说的真实数据，可能是行的全部数据（如Innodb的聚簇索引），也可能只是行的主键（如Innodb的辅助索引），或者是行所在的地址（如MyIsam的非聚簇索引）。
 *  B树中一条记录只会出现一次，不会重复出现，而B+树的键则可能重复重现：一定会在叶节点出现，也可能在非叶节点重复出现。
 *  B+树的叶节点之间通过双向链表链接。适合于范围查询
 *  B树中的非叶节点，记录数比子节点个数少1；而B+树中记录数与子节点个数相同。  
    由此，B+树与B树相比，有以下优势：
 *  更少的IO次数：B+树的非叶节点只包含键，而不包含真实数据，因此每个节点存储的记录个数比B数多很多（即阶m更大），因此B+树的高度更低，访问时所需要的IO次数更少。此外，由于每个节点存储的记录数更多，所以对访问局部性原理的利用更好，缓存命中率更高。
 *  更适于范围查询：在B树中进行范围查询时，首先找到要查找的下限，然后对B树进行中序遍历，直到找到查找的上限；而B+树的范围查询，只需要对链表进行遍历即可。
 *  更稳定的查询效率：B树的查询时间复杂度在1到树高之间(分别对应记录在根节点和叶节点)，而B+树的查询复杂度则稳定为树高，因为所有数据都在叶节点。

B+树也存在劣势：由于键会重复出现，因此会占用更多的空间。但是与带来的性能优势相比，空间劣势往往可以接受，因此B+树的在数据库中的使用比B树更加广泛。

图示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 4]

### 4.6.1、感受B+树的威力 ###

前面说到，B树/B+树与红黑树等二叉树相比，最大的优势在于树高更小。实际上，对于Innodb的B+索引来说，树的高度一般在2-4层。下面来进行一些具体的估算。

树的高度是由阶数决定的，阶数越大树越矮；而阶数的大小又取决于每个节点可以存储多少条记录。Innodb中每个节点使用一个页(page)，页的大小为16KB，其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等)，大多数空间都用来存储键或数据。

对于非叶子节点，记录只包含索引的键和指向下一层节点的指针。假设每个非叶节点页面存储1000条记录，则每条记录大约占用16字节；当索引是整型或较短的字符串时，这个假设是合理的。延伸一下，我们经常听到建议说索引列长度不应过大，原因就在这里：索引列太长，每个节点包含的记录数太少，会导致树太高，索引的效果会大打折扣，而且索引还会浪费更多的空间。  
对于叶子节点，记录包含了索引的键和值(值可能是行的主键、一行完整数据等，具体见前文)，数据量更大。这里假设每个叶节点页面存储100条记录(实际上，当索引为聚簇索引时，这个数字可能不足100；当索引为辅助索引时，这个数字可能远大于100；可以根据实际情况进行估算)。

对于一颗3层B+树，第一层(根节点)有1个页面，可以存储1000条记录；第二层有1000个页面，可以存储1000*1000条记录；第三层(叶子节点)有1000*1000个页面，每个页面可以存储100条记录，因此可以存储1000*1000*100条记录，即1亿条。而对于二叉树，存储1亿条记录则需要26层左右。

# 五、总结 #

最后，总结一下各种树解决的问题以及面临的新问题：

*  二叉查找树(BST)：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；
 *  平衡二叉树(AVL)：通过旋转解决了平衡的问题，但是旋转操作效率太低；
 *   *  红黑树：通过舍弃严格的平衡和引入红黑节点，解决了AVL旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO次数太多；
 *  B树：通过将二叉树改为多路平衡查找树，解决了树过高的问题；但是不适用于范围查询；
 *  B+树：在B树的基础上，将非叶节点改造为不存储数据的纯索引节点，进一步降低了树的高度；此外将叶节点使用指针连接成链表，范围查询更加高效。

# 六、面试常见题目 #

## 6.1、什么是聚簇索引和非聚簇索引？ ##

非聚簇索引：索引文件与数据文件分开存储，MyISAM 使用的是非聚簇索引；  
聚簇索引：索引与数据文件存储在一起，InnoDB 使用的是聚簇索引；  
可以在mysql的data目录中查看索引文件与数据文件是否分开。

除了InnoDB的主键索引，在 MySQL 中的其他索引形式都是非聚集索引。

非聚簇索引示例：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 5]  
聚簇索引示例  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 6]

## 6.2、为什么InnoDB表必须要有主键，并且推荐使用整型的自增主键？ ##

### 6.2.1、为什么必须要有主键？ ###

需要一个字段，来组织所有的数据；

如果定义了主键，Innodb会选择主键作为聚集索引；如果没有定义主键，Innodb会选择不包含NULL值的唯一索引作为聚集索引；如果也没有这样的唯一索引列，Innodb会选择内置6字节长的rowID作为隐含的聚集索引，这里的RowId会随着记录的写入而主键自增，但是它是不可引用和查看的，是数据库引擎内部的使用。

### 6.2.2、为什么要使用整型、自增主键？ ###

1、为什么使用整型？

*  使用整型可以减少存储空间，存放更多的索引数据；

2、为什么使用自增？总之就是减少分裂和移动的频率。

*  如果我们使用自增主键，那么每次插入的新纪录都在原先记录的尾部按照顺序，添加到当前节点的索引后面，当一页快写满的时候，就会开辟一个新的页。数据记录本身就存与索引的叶子节点上，B+tree的树。这就要求每一个叶子节点内的各条数据记录按主键顺序存放，因此每当有一条新的记录插入的时候，MYSQL会根据其主键将其插入到合适的节点和位置上，如果页面达到装载因子（INNODB默认为15/16），则开辟新的页面（节点）；同时，有利于子节点的指针执行下一个节点，有利于范围查询
 *  如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置，此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

插入连续的数据：  
![在这里插入图片描述][20200808095820156.jpeg]  
插入非连续的数据：  
![在这里插入图片描述][20200808095909365.jpeg]

[Link 1]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[20200808101748304.gif]: /images/20221124/9335312658a9440f96fdce79fd05dbb2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70]: /images/20221124/53b72ad41d1b49c98a26c054a7eb6acc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 1]: /images/20221124/a9d8639f0578418793141ecc2e1a38fb.png
[20200808091924200.gif]: /images/20221124/6fd2e31f50e746a69d9010fa11b90aa3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 2]: /images/20221124/2eef681379ec4e2ca1103a47468a62c1.png
[2020080809273820.gif]: /images/20221124/c48e19518ec04de393a9a80955131fc4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 3]: /images/20221124/6d3a9f4a10df4819be0fda14355ee5ab.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 4]: /images/20221124/de2c991758704c63b04652f320e8d7ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 5]: /images/20221124/6fee75e4f3b04f2492b495b83385ea07.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMwNjgzNzc_size_16_color_FFFFFF_t_70 6]: /images/20221124/7260f61f0c5a470da8ae5e5be1af12db.png
[20200808095820156.jpeg]: /images/20221124/0118bd07ccb949d49809fdea444c66d3.png
[20200808095909365.jpeg]: /images/20221124/cfd52712c2274e63b04437eee4c37d62.png