Mysql索引 B+ B AVL RBT Hash

Mysql索引分析

本文主要说明一下Mysql索引类型与索引数据结构，同时推荐一个动画演示数据结构的网站https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引类型分类

Hash索引
B-Tree索引（也就是B+Tree索引）

Hash索引

    Hash索引的思想非常好，需要一个Hash函数（散列函数）对索引字段运算，就能得到索引字段对应的记录或者记录地址。其时间复杂度无论在N有多大基本都是O(1)。然而这只是最理想的情况了，因为散列函数是有可能发生碰撞的，那么碰撞的记录是以链表的方式排列着的，跟HashMap思想一样。因此Hash索引支持精确的查询
    为什么Mysql没用Hash索引当作默认索引？试想一下，如果现在有个查询语句是这样的：select * from name > '鸡蛋'，这种情况下，Hash索引是无法正常工作的，因为无法运用散列函数获得记录的数据。因此，Hash索引不适合范围查询
    那假如Hash索引的散列函数支持一种递增的模式（函数单调递增、单调递减），那这样岂不是能解决上述的范围查询问题了吗？事实上，这种函数本身难找另外也是最主要的是如果数据被一种以单调性的存放在一个有序数组中，在记录的增加删除时会带来非常严重的性能下降，因为在删除增加某条记录时会让数组中的记录依次移位。
    Hash索引的应用场景主要是做静态存储引擎，记录本身基本不会涉及到变化，从插入就固定下来了。

B-Tree索引

    在Mysql数据结构这一块，需要满足查询时间O(logN)，增添删除不会带来更多的开销的数据结构，实际上树是最好的选择。所以有二叉搜索树、AVL（平衡二叉树）、RBT（红黑树）、B-Tree、B+Tree这几种可供选择。当然以上说的几种树都满足左小右大的约束，那为什么最后选择了B+Tree呢？分析如下：

二叉搜索树
    普通二叉树没有任何树高的限制，他只满足基础约束（左小右大），那么有一种极端情况，如下：
在这种情况下，二叉搜索树退化成了线性结构，查询时间会大大飙升。而且树的高度也增加了，这也会带来查询期间的IO开销增大，因为需要不停的读取硬盘上的节点数据。
AVL（平衡二叉树）、RBT（红黑树）
    这两种树前者都会在记录插入期间，通过更多的变化树的结构来保持树的高度京可能的低。只不过AVL要求左右子树的高度差不能超过1，而红黑树只是尽可能的降低树的高度，不会那么严格要求。
上面第一张是AVL的结构，第二张是RBT的结构，可以看到，这两者都能尽可能的降低树的高度，只不过AVL更严格，但是会带来更大的开销，所以可以知道，在非数据库的场景中AVL适合增添删除不多的场景下的查询，而RBT更适合增添删除比较频繁的查询。OK，那为什么Mysql还是没选择这种数据结构来保存索引呢？我们可以想想一下，如果记录量非常大的时候，这两者又能降低多少高度，所以，不适合数据库这种一张表动辄几十万的应用。
B-Tree
    综合上面的几种情况，光在树的结构变化上做文章是不能更好的解决问题的，那么只有增加树每个节点的度了。度是指一个节点指向子节点的数量。在上面的三种树形结构中，我们都是让度最多为2，那如果我们增大树的度，这样树高的问题就能得到好的解决，那么IO开销也会大大降低。所以我们通过一定的算法，可以排列出下面这种B-Tree
可以看到此时每个节点能够保存更多的子节点引用，而且每个非叶子节点也保存了参与比较的K、Data，这就是一条记录了，树的高度被很好的解决了，但是会引申出来一些问题。第一个，范围查询，查询K > 3的数据，会先找到K为3的记录，发现这块数据中比它大的有5，之后它回溯到上一层节点，找到8再找到P2指针指向的另一个数据块，重复这种逻辑。这就会带来重复的比较开销，降低性能。第二个，非叶子节点中保存了一些参与比较的记录，那当一条记录有几十个字段并且字段的容量还很大的时候，整个非叶子节点的空间开销也会很大。
B+Tree
    B+Tree与B-Tree的区别是，B+的所以记录都在叶子节点并且是有序的，每个叶子节点或者说数据块之间有指针指向像一个，非叶子节点只保存指向子节点的指针和参与比较的K。如图：

可以看到，这样就能很好的解决B-Tree带来的两个问题：范围查询和节点存储开销。每个叶子节点都有指针指向与之相邻的叶子节点，在范围查询的时候，不用回溯上一层子节点。非叶子节点不用保持具体数据只保存K，这减少了节点存储开销并且一个节点能够保存更多的K，能够更好的降低树的高度，当然，保存的K不是越多越好，否则会带来比较的开销。