MySQL相信大家都不陌生,索引的日常使用应该也是比较频繁的,今天就聊一聊索引底层的数据结构;
MySQL索引底层为什么使用B+树而不是二叉树;红黑树;B树?
索引:索引是帮助MySQL高效获取数据的的排好序的数据结构(B+Tree),例如日常看书的目录,可以快速的帮我们定位到我们想看的位置.
1. 二叉树
使用二叉树来做索引的数据结构,每一个节点储存一个索引和当前记录再磁盘所在的位置;
例如我们现在有这么一张表,如下图
binary_tree_test这张表中有column_1;column_2两个字段;
column_2这个字段来做索引 
如果以column_2这个字段来做索引的话,再使用二叉树的数据结构的情况下是这样的,
select * from binary_tree_test where column_2 = 66;
这条sql查询,再使用索引的情况下,再底层的结构中只需要37->73->66作比较,最后查询到我们想要的column_2 = 66的数据;比较三次,从这一点看还是狠快的;好像没有什么问题;接下来看下一种情况
column_1这个字段来做索引
如果使用column_1这个字段来做索引,那么它底层的结构就应该是这样的.
select * from binary_tree_test where column_1 = 6;
上面这条sql查询,在使用索引的情况下,在底层的数据结构中,需要1->2->3->4->5->6做6次比较,基本上跟没有使用索引进行全表扫描是没什么区别的;效率会非常低的;没有太大的提升
总结:二叉树这种数据结构再对单边增长的数据/列,对于我们查找的效率并没有什么显著的提升,搜索的数值越大,越接近全表扫描,这也是MySQL为什么不使用二叉树来做索引底层的数据结构的原因
2. 红黑树(二叉平衡树)
红黑树又叫二叉平衡树,这种数据结构跟二叉树类似,但是比二叉树多一个自动平衡的功能,根节点左右两边,一边比另一边的树的高度要高的多的时候,会通过变色或者旋转的方式自动平衡;
binary_tree_test表使用column_1这个字段来做索引
如果索引底层是红黑树的情况下,binary_tree_test表使用column_1这个字段来做索引就不会再出现一边倒的二叉树了,因为红黑树可以帮我们自动平衡;
select * from binary_tree_test where column_1 = 6;
我们再获取column_1 = 6的数据时,只需要跟2->4->6依次比较就可以了,这样下来比较了3次,是要比使用二叉树的效率提升很多的,虽然看起来使用红黑树是要比使用二叉树的效率高很多,但是红黑树依然不是MySQL索引选中的数据结构,具体原因是因为上面例子是一个数据量非常比较小的表,但是再我们生产环境下是没有数据量这么小的表的,基本上都是几十万几百万甚至上千万的数据量,随着数据量越来越多的情况下,我们红黑树的高度也会越来越高,假设树的高度是50,我们查询的元素刚好再底层的叶子节点,我们就需要从根节点一直比较,直到第50次比较到叶子节点获取到我们要的数据为止.同学们设想一下,50次比较,50次的磁盘IO效率同样不会很高
总结:再数据量越来越大的情况下,红黑树的高度不可控,查询的数据越接近根节点效率越高,越接近叶子节点效率越低.使用红黑树来做MySQL索引的底层数据结构同样不理想
3:B树
- B树所有索引元素不重复
- 叶节点具有相同的深度,叶节点的指针为空
- 节点中的数据索引从左到右依次递增排列
如图,B树每个节点中不仅存放着索引,并且还储存着当前列的数据data;mysql对B树的每一块节点的大小规定的是16K,当一块节点分配出去以后,mysql会直接再磁盘上画出16K的空间用来储存当前块的节点
总结:假设我们使用B树来做我们的Mysql的底层数据结构,在使用bigint来做我们的索引的话,bigint再Mysql中占8个字节,每一列的数据假设占用1KB,那么我们三层才可以储存16×16×16=4096条数据,数据量过大的时候我们的B树的高度同样不可控,数据量越大效率会越低,所以Mysql同样不会使用B树来做底层的数据结构
4:B+树
- B+树为了储存更多的索引,非叶子节点不储存当前列的数据再磁盘中的地址data,只储存索引;非叶子节点储存的索引都相当于冗余索引,再叶子节点还会有该索引的值
- 叶子节点储存着所有的索引字段
- 叶子节点用双向指针连接,提高区间访问的性能
- B+树同样的也是从左到右依次递增排列的
B+树不仅使用了双向指针来连接叶子节点,还是用了指针来连接上层节点和下层节点,上层节点储存着下次节点的地址;方便我们可以更快的进行查询;
常驻内存机制:Mysql会把B+树的非叶子节点中的数据提前加到内存中,减少不必要的IO次数,方便我们更快的查询.
使用B+树是否还会出现树的高度不可控的情况?
- 不会;从前面几个数据结构的判断中,我们大概都清楚了,决定我们的效率的往往是树的高度,树的高度越低,经历的磁盘IO的次数就越少,效率也会越高,而我们B+树的高度是由我们的非叶子节点可以存放多少的数据而决定的,所以B+树使用冗余索引,把data放在叶子节点上去,就是为了非叶子节点的可以储存更多的元素
- 假设我们使用bigint来做我们的索引;一个bigint的索引大概再mysql占用8个字节,存放着下层节点的指针再C语言中占6个字节;16KB÷(8B+6B)=1170;顶层节点可以存放1170个节点;第二层每个节点块也可以储存1170个节点;叶子节点正常情况下一列约等于1KB的元素,每个叶子节点就可以储存16个索引;B+树三层的情况下可以储存1170×1170×16=21902400个元素;2190万条数据的表常驻内存机制加上B+树作为我们底层数据结构时,mysql还会把非叶子节点的节点块给提前放到内存中(常驻内存机制);节省掉不必要的磁盘IO;我们的查询再底层只需要经历一次磁盘IO就可以完成,效率比其他的数据节点快的不是一点点;而且数据量越大,使用B+树的效率提高越明显