为什么MySQL索引要用B+树，而不是B树？

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

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

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

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

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

 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。内容未经允许不得转载，或转载时需注明来源： 创新互联