为什么MySQL索引要用B+树,而不是B树?

2021-02-26    分类: 网站建设

一个面试题:InnoDB 一棵 B+ 树可以存放多少行数据?这个问题的简单回答是:约 2 千万。

我们先将数据记录按主键进行排序,分别存放在不同的页中(为了便于理解我们这里一个页中只存放 3 条记录,实际情况可以存放很多)。

除了存放数据的页以外,还有存放键值+指针的页,如图中 page number=3 的页,该页存放键值和指向数据页的指针,这样的页由 N 个键值+指针组成。

当然它也是排好序的。这样的数据组织形式,我们称为索引组织表。

现在来看下,要查找一条数据,怎么查?如:

  1. select * from user where id=5; 

这里 id 是主键,我们通过这棵 B+ 树来查找,首先找到根页,你怎么知道 user 表的根页在哪呢?

其实每张表的根页位置在表

接下来我们用 hexdump 工具,查看表

总结

lineitem 表的数据行数为 600 多万,B+ 树高度为 3,customer 表数据行数只有 15 万,B+ 树高度也为 3。

可以看出尽管数据量差异较大,这两个表树的高度都是 3。换句话说这两个表通过索引查询效率并没有太大差异,因为都只需要做 3 次 IO。

那么如果有一张表行数是一千万,那么他的 B+ 树高度依旧是 3,查询效率仍然不会相差太大。region 表只有 5 行数据,当然他的 B+ 树高度为 1。

最后回顾一道 MySQL 面试题:为什么 MySQL 的索引要使用 B+ 树而不是其他树形结构?比如 B 树?现在这个问题的复杂版本可以参考本文。

他的简单版本回答是:因为 B 树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节点中能保存的指针数量变少(有些资料也称为扇出)。

指针少的情况下要保存大量数据,只能增加树的高度,导致 IO 操作变多,查询性能变低。

本文从一个问题出发,逐步介绍了 InnoDB 索引组织表的原理、查询方式,并结合已有知识,回答该问题,结合实践来证明。

当然为了表述简单易懂,文中忽略了一些细枝末节,比如一个页中不可能所有空间都用于存放数据,它还会存放一些少量的其他字段比如 page level,index number 等等。

另外还有页的填充因子也导致一个页不可能全部用于保存数据。关于二级索引数据存取方式可以参考 MySQL 相关书籍,他的要点是结合主键索引进行回表查询。

文章名称:为什么MySQL索引要用B+树,而不是B树?
网站URL:https://www.cdcxhl.com/news/103077.html

成都网站建设公司_创新互联,为您提供小程序开发软件开发品牌网站设计App开发关键词优化响应式网站

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联

h5响应式网站建设