MySQL中 B-Tree和B+Tree的区别是什么

发布时间:2021-07-06 18:08:23 作者:Leah
来源:亿速云 阅读:169

这篇文章给大家介绍MySQL中 B-Tree和B+Tree的区别是什么,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

B-Tree 的节点是一个二元数组 [key,data],key 是记录的键,data 是键对应的数据,B-Tree中的每个节点根据实际情况可以包含大量的关键字信息和分支,每个节点的每个 key 左右各有一个指针,非叶子节点的指针分别指向下一层的节点,叶子节点的指针为 null,如下图:

MySQL中 B-Tree和B+Tree的区别是什么

要查找值的时候,会先从根节点开始查找,根节点的每个 key 有左右两个指针,可以通过这两个指针访问下一层节点。每次查找都会将查找值与 key 值进行比较,根据比较结果找到合适的指针进入下一层节点,最终,如此重复,最终找到对应的值或者值不存在.

补充下磁盘的知识,系统从磁盘读取数据到内存时是以磁盘块(block)为基本单位的,位于同一个磁盘块中的数据会被一次性读取出来,而不是需要什么取什么。

InnoDB存储引擎中有页(Page)的概念,页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB,可通过参数innodb_page_size将页的大小设置为4K、8K、16K,在MySQL中可通过如下命令查看页的大小:

mysql> show variables like 'innodb_page_size'

而系统一个磁盘块的存储空间往往没有这么大,因此InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位,在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置,这将会减少磁盘I/O次数,提高查询效率。

B+Tree是在B-Tree基础上的一种优化,使其更适合实现外存储索引结构,InnoDB存储引擎就是用B+Tree实现其索引结构。

B-Tree结构每个节点中不仅包含数据的key值,还有data值。而每一个页的存储空间是有限的,如果data数据较大时将会导致每个节点(即一个页)能存储的key的数量很小,当存储的数据量很大时同样会导致B-Tree的深度较大,增大查询时的磁盘I/O次数,进而影响查询效率。在B+Tree中,所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上,而非叶子节点上只存储key值信息,这样可以大大加大每个节点存储的key值数量,降低B+Tree的高度。

B+Tree 节点是 B-Tree 的变种,相对于 B-Tree 而言 B+Tree 有如下不同:

非叶子节点只存储键值信息。

所有叶子节点之间都有一个链指针。

数据记录都存放在叶子节点中。

MySQL中 B-Tree和B+Tree的区别是什么

关于MySQL中 B-Tree和B+Tree的区别是什么就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

推荐阅读:
  1. 面试时怎么表达你对MySQL索引的掌握程度
  2. mysql btree索引概述

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

innodb b+tree mysql

上一篇:Zookeeper的基础原理及应用场景

下一篇:php变量怎么命名

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》