mysql索引底层原理

mysql的数据检索性能取决于其底层的储存引擎和数据检索引擎，尤其是数据的存储形式和索引的设计。

索引的作用是做数据的快速检索，而快速检索的实现本质是数据结构 ；数据库中存放了大量的数据，高效的查找算法决定了快速检索的效率，可以节省巨大的时间。如果没有索引，那么查找一条记录只能采取暴力的顺序遍历查找，消耗的时间是很可怕的！

Mysql 索引底层数据结构选择

1.哈希表

哈希表是做数据快速检索的有效利器；

哈希算法 ： 也叫散列算法，把任意值（key）通过哈希函数变换为固定长度的 key 地址 ，通过这个地址进行直接的访问。
表示为 Addr = H（key）

常用的构造哈希函数的方法：
1.直接定址法（取关键字或关键字的某个线性函数值为哈希地址）
2.数字分析法
3.平方取中法
4.折叠法
5.除留余数法
6.随机数法

： 查找id为100的数据

哈希算法的处理过程是首先计算存储id = 100 的数据的物理地址，通过该物理地址可以找到对应的数据。
但是哈希算法会有个数据碰撞的问题，即不同的key可能会计算出相同的物理地址。解决碰撞问题常见的处理方式之一 - 链地址法；（此法可以完全避免哈希函数的冲突）

Chaining.png

有个最差的场景，即是哈希表带有许多很长的链表，这样看来查询效果就会收到影响。

从算法时间复杂度分析来看，哈希算法时间复杂度为 O（1）（在最差的情况下也是个O(n)的），检索速度非常快。查找数据需要一次寻址就可以获得对应的数据。但是 Mysql 并没有采取哈希作为其底层算法，这是为什么呢？

因为考虑到数据检索有一个常用手段就是范围查找

： 查找id大于100的数据

针对以上这个场景，我们希望做的是找出 id>100 的数据，这是很典型的范围查找。如果使用哈希算法实现的索引，范围查找怎么做呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选目标范围内的数据。但是这个办法没有一点效率而言。

所以，使用哈希算法实现的索引虽然可以做到快速检索数据，但是没办法做数据高效范围查找，因此哈希索引是不适合作为 Mysql 的底层索引的数据结构。

2.二叉查找树（二叉排序树 ｜Binary Sort Tree ｜BST）

二叉树基础知识 ：

二叉树是n（n >= 0）个结点的有限集，特点是每个结点至多只有两颗子树（即二叉树中不存在度大于2的结点，结点拥有的子树数称为结点的度）。

完全二叉树和满二叉树是两种特殊形态的二叉树。

一棵深度（树中结点的最大层次称为树的深度或高度）为k且有2^k - 1 个结点的二叉树称为满二叉树

完全二叉树是由满二叉树而引出来的，设二叉树的深度为k,有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树
(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）
(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l。

tree.jpg

二叉查找树是一棵特殊的二叉树。
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

bst.jpg

：查找id为100的数据

二叉查找树的时间复杂度是O(lgn),从检索效率上看来是能做到高速检索的,此外二叉树的结构能不能解决哈希索引不能提供的范围查找功能呢？

答案是可以的。二叉树的叶子节点都是按序排列的，从左到右依次升序排列，如果我们需要找 id> 100 的数据，那我们取出节点为 101 的节点以及其右子树就可以了，范围查找也算是比较容易实现。

但是普通的二叉查找树有个致命缺点：极端情况下会退化为线性链表，例如id为auto_increment。（因为二叉查找树的特性，左子树小于跟结点，跟结点小于右子树），时间复杂退化为 O（N），检索性能急剧下降。

如果采取二叉树这种数据结构作为索引，那上面介绍到的不平衡状态导致的线性查找的问题必然出现。因此，简单的二叉查找树存在不平衡导致的检索性能降低的问题，是不能直接用于实现 Mysql 底层索引的。

3.AVL (自平衡二叉查找树)树和红黑树

二叉查找树存在不平衡问题，因此学者提出通过树节点的自动旋转和调整，让二叉树始终保持基本平衡的状态，就能保持二叉查找树的最佳查找性能了。基于这种思路的自调整平衡状态的二叉树有 AVL 树和红黑树。

AVL树本质上还是一棵二叉搜索树，查找的时间复杂度是O(log n)，它的特点是 :
1.本身首先是一棵二叉搜索树。
2.带有平衡条件：任意一个结点的左右子树的高度之差的绝对值（平衡因子）最多为1,所以它也被称为高度平衡树。

红黑树是一种平衡二叉查找树的变体，它的左右子树高差有可能大于 1，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。查找的时间复杂度是O(log n),它的特点是 ：
1. 节点是红色或黑色。
2. 根节点是黑色。
3.所有叶子都是黑色。（叶子是NULL节点）
4. 每个红色节点的两个子节点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

红黑树并没有完全解决二叉查找树退化为线性链表的问题，虽然这个“右倾”趋势远没有二叉查找树退化的那么夸张，但是数据库中的基本主键自增操作，主键一般都是数百万数千万的，如果红黑树存在这种问题，对于查找性能而言也是巨大的消耗。
因为 AVL 树是个绝对平衡的二叉树，因此他在调整二叉树的形态上消耗的性能会更多。

AVL 树相比哈希表的优点：

不错的查找性能（O（logn）），不存在极端的低效查找的情况。
可以实现范围查找、数据排序。

但是ALV树并没有作为MYSQL索引的数据结构，因为考虑到数据库的最大瓶颈是磁盘IO,如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里,效率太低，所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。

4. B-tree

B-tree中，每个结点包含：

1、本结点所含关键字的个数；
2、指向父结点的指针；
3、关键字；
4、指向子结点的指针；

B-tree 特性：
每个非终端节点包含n个关键字信息（P0,P1,…Pn, k1,…kn） 这样每个节点就可以存储更多的数据了，可以减少节点个数，降低B-树的深度，从而减少读磁盘次数，将计算放到内存中。
在磁盘上进行一次查找比在内存中进行一次查找耗费时间多得多，因此，在磁盘上进行查找的次数，即待查关键字所在结点在B-树上的层次树，是决定B-树查找效率的首要因素

B-.png

磁盘知识 ：
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么

InnoDB存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数innodb_page_size将页的大小设置为4K、8K、16K，而系统一个磁盘块的存储空间往往没有这么大，因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位。

每个节点占用一个盘块的磁盘空间，一个节点上有两个升序排序的关键字和三个指向子树根节点的指针，指针存储的是子节点所在磁盘块的地址。两个关键词划分成的三个范围域对应三个指针指向的子树的数据的范围域。
B-Tree相对于AVLTree缩减了节点个数，使每次磁盘I/O取到内存的数据都发挥了作用，从而提高了查询效率。

B+tree

B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。

从上面的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点的物理地址都是存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

B+Tree相对于B-Tree有几点不同：

1. 非叶子节点只存储键值信息。

2. 所有叶子节点之间都有双向链指针。

3. 数据记录物理地址都存放在叶子节点中。

将上面的B-Tree优化，由于B+Tree的非叶子节点只存储键值信息，假设每个磁盘块能存储4个键值及指针信息，则变成B+Tree后其结构如下图所示：

image

通常在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。因此可以对B+Tree进行两种查找运算：一种是对于主键的范围查找和分页查找，另一种是从根节点开始，进行随机查找。

推算：

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗^{3）。也就是说一个深度为3的B+Tree索引可以维护10}3 * 10^3 * 10^3 = 10亿 条记录。

实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree的高度一般都在2_{4层。mysql的InnoDB存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1}3次磁盘I/O操作。

数据库中的B+Tree索引可以分为聚集索引（clustered index）和辅助索引（secondary index）。上面的B+Tree示例图在数据库中的实现即为聚集索引，聚集索引的B+Tree中的叶子节点存放的是整张表的行记录数据。辅助索引与聚集索引的区别在于辅助索引的叶子节点并不包含行记录的全部数据，而是存储相应行数据的聚集索引键，即主键。当通过辅助索引来查询数据时，InnoDB存储引擎会遍历辅助索引找到主键，然后再通过主键在聚集索引中找到完整的行记录数据。

通过 B 树和 B+树的对比我们看出，B+树节点存储的是索引，在单个节点存储容量有限的情况下，单节点也能存储大量索引，使得整个 B+树高度降低，减少了磁盘 IO。其次，B+树的叶子节点是真正数据存储的地方，叶子节点用了链表连接起来，这个链表本身就是有序的，在数据范围查找时，更具备效率。因此 Mysql 的索引用的就是 B+树，B+树在查找效率、范围查找中都有着非常不错的性能。