mysql索引数据结构选型

目录

01、导语

02、哈希表和红黑树、AVL树

03、B树

04、B+树

导语

大家先看一下下面这个数据表：

这里有一张用户表，可以当作一张普通的链表，那么查找 id=7 这个数据，那么只能采取暴力顺序遍历查找，找到 id=7 这个数据需要比较 7 次，如果这个表存储的是 1000W 个数据，查找 id=1000W 这个数据那就要比较 1000W 次，这种速度是不能接受的。

我们可以通过不同数据结构的选择来实现数据的快速检索

选型1：哈希表

通样是刚刚的查询语句select * from user where id=7; 我们看看哈希表结构是怎样进行查询的。

如上图所示，会先使用哈希算法计算存储 id=7 的数据的物理地址 addr=hash(7)=4231，而 4231 映射的物理地址是 0x77，0x77 就是 id=7 存储的额数据的物理地址，通过该独立地址可以找到对应 user_name='g'这个数据。

对比普通链表的查询，用哈希表进行点查可以减少顺序遍历查找，大大提高效率。

但哈希算法是一个输入无限但输出有限的函数，有可能会发生数据碰撞

这个就是哈希冲突，也就是哈希函数可能对不同的 key 会计算出同一个结果，比如 hash(7)可能跟 hash(199)计算出来的结果一样

。解决碰撞问题的一个常见处理方式就是链地址法，即用链表把碰撞的数据接连起来。计算哈希值之后，还需要检查该哈希值是否存在碰撞数据链表，有则一直遍历到链表尾，直达找到真正的 key 对应的数据为止。

当key越多的时候，hash冲突发生的概率也越大。链表越长，最终hash表也会退化成一张大链表，这是mysql没有选用哈希表结构的原因之一。

还有另外一个原因，我们mysql经常会进行类似的范围查询，如果使用了hash表结构，要怎样查呢？一个简单的思路就是一次把所有数据找出来加载到内存，然后再在内存里筛选筛选目标范围内的数据。但是这个范围查找的方法也太笨重了。

选型2：红黑树

红黑树是一棵特殊的平衡二叉树。为什么要平衡呢？因为二叉查找树遍历数据时树越高效率越低。

想要解决这个问题，有效的一种办法就是使得树的高度不要差很多，也就是平衡它。

那下面我们看看红黑树是怎样做到把二叉树平衡的。

首先红黑树定了一些必须满足的规则：

性质1. 结点是红色或黑色。

性质2. 根结点是黑色。

性质3. 所有叶子都是黑色。（叶子是NIL结点）

性质4. 每个红色结点的两个子结点都是黑色。（从每个叶子到根的所有路径上不能有两个连续的红色结点）

性质5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

上图所示，每次插入或者删除都会导致红黑树规则被打破，需要进行旋转和变色从而达到平衡，大家可以从下面的旋转变色过程中找到红黑树的变化规律

红黑树拥有不错的平均查找效率，也不存在极端的退化成链表的情况，那红黑树作为 Mysql 底层索引实现是否可以呢？

其实红黑树也存在一些问题，数据库中的基本主键自增操作，虽然旋转后右倾的情况并没有退化成链表那么夸张，但主键一般都是数百万数千万的，对于查找性能而言也是巨大的消耗。

自增主键的情况：

选型3：AVL树（高度平衡树）

AVL 树是个高度平衡的二叉树，对比红黑树的满足规则就不继调整，AVL树会一直调整的高度平衡。添加和删除操作都可能导致avl树失衡，需要判断失衡类型（LL/LR/RR/RL），然后做旋转。

失衡类型：

1.LL型：右旋（LL旋转）

2.RR型：左旋（RR旋转）

3.LR型：先左旋，后右旋（LR旋转）

4.RL型：先右旋，后左旋（RL旋转）

判断为LR型，需要进行先左旋，后右旋

对比红黑树，虽然插入时旋转次数更多了，但在查询时不存在低效查找的情况

总结一下 AVL 树的优点：

不错的查找性能（O（logn）），不存在极端的低效查找的情况。看起来 AVL 树作为数据查找的数据结构确实很不错，但是 AVL 树并不适合做 Mysql 数据库的索引数据结构。

因为考虑一下这个问题： 数据库查询数据的瓶颈在于磁盘 IO，如果使用的是 AVL 树，我们每一个树节点只存储了一个数据，我们一次磁盘 IO 只能取出来一个节点上的数据加载到内存里，那比如查询 id=8 这个数据我们就要进行磁盘 IO 4次，这是多么消耗时间的。所以我们设计数据库索引时需要首先考虑怎么尽可能减少磁盘 IO 的次数。

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

选型4：B树（多路平衡查找树）

B 树的节点可以包含有多个字节点，所以 B树是一棵多叉树。

数据量不大时可能不太真切。但当数据量大时，节点也会随着增多；由于二叉树只能最多2个叶子节点的约束，也只能纵向去的去扩展子节点，树的高度会很高，意味着需要更多的操作磁盘I/O次数。

而B树则可以通过横向扩展节点从而降低树的高度，所以效率自然要比二叉树效率更高。

那B树解决了磁盘I/O的问题，为什么还不是最适合的呢？

虽然B树支持按区间查找，但并不高效。例如上面的例子中，B树能高效的通过等值查询 90 这个值，但不方便查询出一个期间内3 ~ 28区间内所有数的结果。

因为当B树做范围查询时需要使用中序遍历（左子树->根节点->右子树），那么父节点和子节点也就需要不断的来回切换涉及了多个节点会给磁盘I/O带来很多负担。

选型5：B+树

后来为了解决这类型的问题又有了B+树，也就是MySQL 中innoDB引擎中的索引底层数据结构采用的。

B+树有2 个特点：

1、非叶子节点都不存储数据，而是只作为索引。对比B树，这里每个节点就可以存储更多的关键字，使树更加的矮胖，提高查询效率。

2、叶子节点存放数据，以及指向相邻叶子节点的指针，形成了一个有序链表。

单点查询：

ID=7

由于子节点只存了索引，整棵树的高度会变矮，磁盘IO的次数也会大大减少

范围查询：

ID >=7 && ID <=18

对比B树的中序遍历需要进行父子节点不断切换读取磁盘，B+树使用叶子节点链表的方式，能减少多次回到父节点的查询，效率大大提高。

总结

以上就是对mysql索引数据结构选型的一些对比与思考，感谢大家阅读。