对MySQL底层索引深度解析 _MySQL

为什么需要索引？
一句话概括：索引的出现其实就是为了提高数据查询的效率。
一、索引常见模型模型：哈希表、有序数组和搜索树
哈希表

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的键即 key，就可以找到其对应的值即 Value 。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。
时间复杂度：0(1)
画重点：如果索引的值有重复的话，会发生hash碰撞，虽然可以解决hash冲突，但是导致查询效率降低。
场景：哈希表这种结构适用于只有等值查询的场景，不适用于查找范围的。类似 redis Memcached 及其他一些 NoSQL 引擎。

搜索树在了解搜索树之前我们需要先知道二叉树、平衡二叉树、B树、B+树
推荐一个工具可以清晰的理解树的原理： https://www.cs.usfca.edu/~gal...
二叉树二叉树特性：左子树的键值小于根的键值，右子树的键值大于根的键值。
如下图就是一个二叉树

文章插图

当前二叉树的插入顺序是： 3 2 4 1 5
如果我们按1 2 3 4 5 的顺序来插入的化，我们得到的二叉树就是如下图所示

文章插图

如果是这种二叉树查询效率就太低了。若想二叉树的查询效率尽可能高，需要二叉树是平衡的从而引出新的定义 - 平衡二叉树或称AVL树。
平衡二叉树【对MySQL底层索引深度解析】平衡二叉树特点：

满足二叉树的特性
任何节点的两个子树的高度最大差为1

如上两个组合之后就是平衡二叉树，如下图
中插入树的顺序为：1 2 3 4 5 6 7 8 时候生成的是如图所示的内容，和图二完成不一样，在通过工具生成这个图的时候明显可以看到不管如何插入节点数据都能满足平衡二叉树的特点2 。
当删除一个节点之后同样能满足avl树，如下图删除图3中的5节点之后展示如下。
总结一下平衡二叉树的优点

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

看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 MySQL 数据库的索引数据结构，因为考虑一下这个问题：
数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=8 这个数据我们就要进行磁盘 IO 三次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。
磁盘 IO 有个有个特点，就是从磁盘读取 1B 数据和 1KB 数据所消耗的时间是基本一样的，我们就可以根据这个思路，我们可以在一个树节点上尽可能多地存储数据，一次磁盘 IO 就多加载点数据到内存，这就是 B 树，B+树的的设计原理了。
B-树B树的特点：

所有健值分布在整棵树中
搜索有可能在非叶子节点结束
根节点至少有2个子树
所有叶子节点都在同一层
分叉数（路数）永远比关键字数多 1
节点存储key和value

文章插图

演示 B树索引分裂合并比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针，子节点会变成 4 路，所以这个时候必须进行分裂。把中间的数据 2 提上去，把 1 和 3 变成 2 的子节点。
如果删除节点，会有相反的合并的操作。注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的。我们继续插入 4 和 5，B Tree 又会出现分裂和合并的操作。