简介

简单介绍一下MySQL索引相关的一些原理知识。

转载自：https://juejin.im/post/6844903969160953864

索引概述

在关系数据库中，索引是一种单独的、物理的对数据库表中一列或多列的值进行排序的一种存储结构，它是某个表中一列或若干列值的集合和相应的指向表中物理标识这些值的数据页的逻辑指针清单。

就像字典中的A、B、C这种帮助使用者快速定位自己想要的内容一样，数据库索引是一样的考虑。

索引相关的数据结构

B-树

B-树的搜索，从根节点开始，对节点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子节点；重复，直到所对应的儿子指针为空，或已经是叶子节点

1. 定义任意非叶子节点最多只有M个儿子；且M>2；
2. 根节点的儿子数为[2, M]；
3. 除根节点以外的非叶子节点的儿子数为[M/2, M]；
4. 每个节点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
5. 非叶子节点的关键字个数=指向儿子的指针个数-1；
6. 非叶子节点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
7. 非叶子节点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
8. 所有叶子节点位于同一层；

B+树

B+的搜索与B-树也基本相同，区别是B+树只有达到叶子节点才命中（B-树可以在非叶子节点命中），而且在所有的叶子节点由一个链表串起来。

1. 其定义基本与B-树同，除了：
2. 非叶子节点的子树指针与关键字个数相同；
3. 非叶子节点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；
4. 为所有叶子节点增加一个链指针；
5. 所有关键字都在叶子节点出现

MySQL索引

MySQL索引要分为两种储存引擎来讲，也就是MyISAM和InnoDB，这两种储存引擎索引都使用B+树的数据结构，当然其中也是有一些细微区别的。

MyISAM索引数据结构

MyISAM的B+树叶子节点储存的并不是数据，而是数据地址，所以这种索引是非聚集索引，搜索按照B+树的搜索算法进行。

InnoDB索引数据结构

InnoDB的索引分为主键索引和普通索引。

主键索引

InnoDB的B+树叶子节点储存的就是数据本身，就是聚集索引（聚簇索引）

普通索引

InnoDB的普通索引，存储相应记录主键的值而不是地址。所以使用普通索引时，是先通过该索引取得主键，在通过主键索引获得数据。

MySQL索引算法

算法是为了提升效率的，那么使用B+树的结构肯定是考虑过查找效率的。

Hash查找的算法效率是最高的，二分查找就是B+树采用的算法方式，这里就有一个问题，为什么没有使用Hash算法进行索引？

Hash索引

MEMORY储存引擎：则是MySQL中一类特殊的储存引擎，它使用储存在内存中的内容来创造表，而且数据全部放在内存中。QQQQ

• keys：代表创建索引的列值
• buckets：计算出来的hash值和对应的数据的物理位置组成的hash表
• entries：具体的数据行

MEMORY的索引就是使用了Hash的结构，通过Hash算法得到bucket的值，当出现hash冲突时使用链表保存，跟普通的hash算法处理基本一致。

正因为MEMORY是内存中的，不支持持久化，所以它只能用于做临时表，数据量比较少，因为数据量太大的时候hash冲突过多，会退化为链表的查询复杂度。

InnoDB储存引擎-自适应哈希索引

InnoDB使用了比较聪明的方式，他通过监控对表上各索引页的查询，如果观察到建立哈希索引可以带来速度提升，则建立哈希索引。InnoDB会自动根据访问频率和模式来自动地为某些热点页建立哈希说明

AHI

AHI是通过缓冲池的B+树页构造而来，因此建立的速度很快，而且不需要对整张表构建哈希索引。

AHI有一个要求，对这个页的连续访问模式必须是一样的。如对于(a,b)这样的联合索引页，其访问模式可以是：

1. where a=xxx
2. where a =xxx and b=xxx

访问模式一样是指查询的条件是一样的，若交替进行上述两种查询，那么InnoDB存储引擎不会对该页构造AHI。

AHI还有下面几个要求：

1. 以该模式访问了100次
2. 页通过该模式访问了N次，其中N=页中记录*1/16

由此可见，AHI的建立要求是比较苛刻的，但也是在这样极大压力的情况下建立AHI才有意义。Mysql中AHI只能通过配置设置开启或关闭，不能手动配置它的建立条件。

可以使用mysql命令去查看AHI的相关情况：

• 查看自适应哈希索引使用情况：show engine innodb status\G;

• 查看自适应哈希索引配置：show variables like ‘innodb_adaptive_hash_index’;

所以，Mysql也是对Hash索引有支持的。但是，在最常用的MyISAM和InnoDB上，却没有使用Hash算法。这是因为Hash查找速度虽然高，但是也存在缺点：

• 只能用于等值查询，不能用于范围查询
• 不能使用索引进行排序
• 组合索引不能使用部分索引查询
• hash冲突时仍需要进行表扫描
• 大量hash冲突造成整体性能低下

因为这些缺点，Hash查找对数据库的一些频繁的操作场景支持不足。相反，使用二分查找却能高效地完成这些查找场景。二分查找，虽然在等值查询时效率比不上Hash，但是范围查询的效率高很多。另外，随着数据量的增大，hash冲突增多的情况下，hash查找的效率衰减远远大于二分查找。所以在数据量大的情况下，二分查找是更合适的查找算法。

Mysql索引实现

虽然确定二分查是更合适的查找算法，但二分查找相关的数据结构也很多，主要是各种二叉平衡树，典型的有AVL树和红黑树：

AVL树

红黑树

无论是AVL树还是红黑树，都是通过一定的处理，保证树的平衡性，避免二叉树失衡，使二分查找的效率变成线性查找。

AVL树和RB树的区别查看这篇文章：https://zhuanlan.zhihu.com/p/93369069

二叉查找树：

• 自平衡
• 时间复杂度O(log n)

然而，B+树比这些平衡二叉树更适合作为索引。

下面了解几个概念：

• 局部性原理-空间局部性：如果一个存储器位置被访问了一次，那么程序很可能在不远的将来访问附近的一个存储器位置。
• 磁盘预读：磁盘IO慢，为提高效率，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存
• 逻辑结构和物理结构：逻辑上很近的节点（父子），物理上可能很远
• 索引存储：索引文件是存在于磁盘中的。因为索引通常是很大的，因此无法一次将全部索引加载到内存当中，因此每次只能从磁盘中读取一个磁盘页的数据到内存中。

因为索引很大，不能一次加载所有的索引数据。
因为二叉树相邻的父子节点的物理距离可能很远，没有办法利用磁盘预读一次读取，必须分开读取。所以，实际上每次只能从磁盘加载1个索引节点的数据。从查找的算法可以看出，查找的效率就跟索引树的高度直接相关。

对比一下平衡二叉树和B+树的树高：

以上图为例，同样的数据量，平衡二叉树树高为5，B+树的树高为3。这样查找，B+树在磁盘IO上要少2次操作，从而IO效率更高。

B+树的优点

• B+树的每个节点可以表示的信息更多，充分利用了磁盘预读的数据，这在从磁盘中查找数据（先读取到内存、后查找）的过程中，可以减少磁盘 IO 的次数，从而提升查找速度
• 关键字全部存放在叶子节点中，而叶子节点中有一个指针指向一下个叶子节点。这样可以提高区间访问的性能（范围查询）。

B+树的查找过程

以上图为例，查找数据项29

1. 磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针
2. 通过磁盘块1的P2指针的磁盘地址把磁盘3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘3的P2指针
3. 通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询

赏

谢谢你请我吃糖果

支付宝

微信