MySQL为什么用B+树做索引存储结构?

小白晋级大师第1篇文章,开始写一些有深度的文章了

先推荐一个数据结构可视化工具网站,用于B+树可视化查看

Data Structure Visualizations

面试技术岗的时候,面试官问你:

mysql索引底层用的是B+树结构,为什么不用B树、二叉树、红黑树呢?

这里其实就是比较各种数据结构的优劣点,最后说明为什么要用B+树结构;

假设数据查询场景:现在有100W的数据存储,查询其中的一条,应该用哪种存储结构呢?

二叉查找树

二叉查找树即有序二叉树,满足二叉树的性质,具有下面特点:

  • 任意节点左子树不为空时,左子树值小于根节点值
  • 右子树不为空时,右子树值大于根节点值;

依次存入数据,如果数据是递增的,则原二叉树退化为链表结构,如图

这种情况下,查询的时间复杂度就是O(n)了

AVL树

AVL树即平衡二叉查找树,通过平衡因子差值判断是否平衡,再用旋转来实现树的平衡。左右子树的树高差不超过1。在执行插入删除操作时,对不满足条件的子树,通过旋转保持平衡。性能开销主要在旋转操作上,由此可以知道AVL树适合查询多,插入删除少的场景

如图,我创建了一棵AVL树,感兴趣的可以在网站上看一下插入过程和旋转调整平衡的过程。

AVL树需要维持树的平衡,而维护这种平衡的开销要大于获得的收益,实际应用中不多

红黑树

红黑树是一种二叉查找树,每个节点新增一个存储位标记是red或black,通过任何一条从根节点到叶子节点路径上,各个节点着色方式的限制,确保没有一条路径比其他路径长2倍,红黑树性质:

  • 根节点是黑色,每个节点非红即黑;
  • 叶子节点都是黑色
  • 如果一个节点是红色,那它的子节点都是黑色
  • 任意节点到叶子节点的路径都包含相同数目的黑色节点

如图是红黑树的可视化:

AVL树和红黑树一样,随着记录数的增加,树的高度会不断增加,查询次数也会增加。

文章开头我们说的要查询100w条数据中的一条,就需要20次搜索,搜索效率不高,查询次数分析如下

$$
2^{20} = 1048576
$$

B-树

即B树,和红黑树相比,B树的树高远远小于红黑树的高度。B树是为了和磁盘交互而设计的平衡多路查找树,操作效率有磁盘的访问次数决定,树高越小,磁盘I/O时间越短。

B树性质:

  • 非叶子节点上最多有M个子节点,且M>2;
  • 根节点的子节点数目为[2, M];
  • 每个节点存放至少M/2-1,至多M-1个关键字
  • 非叶子节点关键字数目=指向子节点的指针个数-1;
  • 所有叶子节点位于同一层

对比红黑树可以发现,每个节点上可以存储更多的数据,且树高固定,数据插入之后横向扩展。即每一次查询只需要搜索3次就行。搜索效率大大提高了。接着我们再来看看B+树

B+树

说一下B+树的性质:

  • 非叶子节点的子树指针 和 关键字 个数一样;
  • 非叶子节点的子树指针,指向闭区间[k[i], k[i+1]],即B树不允许关键字重复,B+树允许
  • 为所有叶子节点增加一个链指针;
  • 非叶子节点作为索引,叶子节点才存储关键字
  • 所有关键字存储在叶子节点

B+树比起B树的优点有:

  1. 只在叶子节点存储数据,16k的内存可以存下更多数据,降低树高
  2. 冗余索引,方便查找;
  3. B+树叶子节点增加了双向链表,方便范围查询;

于是,回到开头的问题,100W的数据,B+树只需要3次或4次I/O查询就能定位到了,且相比较B树,B+树更适合复杂的查询场景,如范围查询。


AD:【腾讯云服务器大降价】2核4G 222元/3年 1核2G 38元/年

本文来自一日成建站教程网https://www.yiricheng.cn/),为广大编程爱好者提供零基础快速搭建博客网站的方法,分享计算机网络、HTML、CSS、JavaScript、PHP、响应式设计以及Python自动化办公的博客文章,另有各类小工具、电子书、免费教程。 版权声明:本文知识版权归原作者所有,该文观点仅代表作者本人。本站仅提供信息存储空间服务,非用于商业用途,不拥有所有权,未对原文做任何修改,不承担相关法律责任,仅用于知识分享。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。 原文链接:https://segmentfault.com/a/1190000041790187

相关阅读  为什么我建议需要定期重建数据量大但是性能关键的表