登录
首页 >  数据库 >  MySQL

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

来源:SegmentFault

时间:2023-01-26 17:43:18 457浏览 收藏

对于一个数据库开发者来说,牢固扎实的基础是十分重要的,golang学习网就来带大家一点点的掌握基础知识点。今天本篇文章带大家了解《MySQL为什么用B+树做索引存储结构?》,主要介绍了MySQL、索引,希望对大家的知识积累有所帮助,快点收藏起来吧,否则需要时就找不到了!

小白晋级大师第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+树更适合复杂的查询场景,如范围查询。

好了,本文到此结束,带大家了解了《MySQL为什么用B+树做索引存储结构?》,希望本文对你有所帮助!关注golang学习网公众号,给大家分享更多数据库知识!

声明:本文转载于:SegmentFault 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表