MySQL索引为什么使用B+树?

前言

有数据库基础的应该都了解数据库利用索引能达到一个快速寻找数据的效果。

更深一点的可能了解到索引(InnoDB)是利用B+树去实现的。

但是为什么要用B+树呢？

这世上树那么多,为何独爱这一棵呢？

一切都源于一个网络’爱情故事’。

艾欧的故事

在城市居住的艾先生,通过网络认识了一个叫欧的女士. 通过几个月的了解,艾先生发现自己爱了这位欧女士,于是向欧女士表白。

欧女士说:”我住在硬盘镇,如果你能找到我,我就答应你”。

欧女士留下了一个地址（0X00000001）给欧先生。

欧先生乘坐高铁来到了硬盘镇,发现这里的房子长的都很像, 想找到欧女士有点困难。

不过好在下车的第一个地方就是0X0000001,但是里面只留下了一个盒子。

欧先生打开盒子后,发现里面有一张纸条写着 0X00000005 , 于是欧先生继续在硬盘镇找寻这个地址。

一段时间后终于找到了, 但是里面同样的还是只有一个盒子, 写着 0X00000099。

过了N段时间后,终于找到了这个地址,也成功的找到了欧女士。

于是艾先生带着欧女士回到了城市。

这个艾先生找寻欧女士花费的时间就是艾欧时间了,从一个盒子找到另一个盒子就是艾欧次数了。

可以看到想要快速的找到欧女士就要缩短寻找的次数。

所以,InnoDB在考虑数据结构时必然要考虑到IO次数的问题。

索引数据结构的选择

Hash

Hash结构等值搜索可以达到O(1)的效果, 但是光不支持范围搜索就毙掉了。

二叉树

树结构的数据在查找中,每一次查询子树都可以看作一次IO. 所以树的高度和IO次数是相等的。

但由于树的根节点一般都会放在内存,根节点不用耗费IO。

一般树高为3的树查询最多需要2次IO。

• 二叉搜索树

特点是左边小于根节点,右边大于根节点,但是插入新数据不会使之旋转。

这也就导致了一个问题, 插入的数据连续时会退化成一个链表,任何搜索都是扫全表.

• AVL搜索树

也叫强平衡二叉搜索树，特点左右子树的高度相差不能超过1.

这也就导致了它会频繁的发生旋转,影响写入的性能。

• 红黑树

特点红色节点的子节点必须是黑色。

每个节点到子节点都必须经过相同的黑色点

这样可以保证不会旋转太频繁,但是树高是不可控的。

多叉树

• B树

B树的特点是每个节点都会保存数据.

这样虽然不用再发生IO去加载数据,但是能记录的节点就少了。

• B+树

B+树的特点是只有叶子节点会保存数据,这个特性能让树尽可能的记录更多的节点。

InnoDB给这个B+树加了’亿’点细节, 每个头尾节点都会记录下一个或者上一个节点的指针, 这样在做范围查询的时候就可以很完美的处理了。

总结

任何不考虑硬件特性的程序都是耍流氓。

可以看到InnoDB为了稳定IO次数选择了B+树,又为了范围搜索添加了指针。

下一篇将会继续讲述B+树到底如何存储索引数据的,如果觉得写的对你有帮助,劳烦一健三连呀。

本文图片来源工具 : 动态数据结构网址

PS： 关注个人公众号: “多边形战士”, 回复”mysql” 送你经典MySQL学习书籍。