专栏首页Java后端技术栈cwnait现在告诉你MySQL为什么选择B+Tree呢?

现在告诉你MySQL为什么选择B+Tree呢?

大家都知道MySQL数据库选择的是B+Tree作为索引的数据结构,那为什么会选择B+Tree呢?

本文分四种数据结构来分析:

  1. 二叉查找树
  2. 平衡二叉树
  3. 多路平衡查找树
  4. 加强版多路平衡查找树(B+Tree)

二叉查找树

二叉搜索树的特点:左子树的键值小于根的键值,右子树的键值大于根的键值。

从上面的 2 个图来看,同样是 30 个数字,插入的数据顺序不一样,二叉树的结构完全不一样,图 1 里查找 30 需要 2 次检索的 IO 操作,但是在图 2 里查找 30 需要 7 次检索的 IO 操作,在图 2 里查找 30 类似于全表扫描。

此处为什么说是一次检索就有一次 IO 呢,因为要查找的数据在文件里,需要从文件里读取出来加载到内存里进行数据比较,如果相等就返回,如果不相等,假设比要查找的数字大,需要接着往左边找;假设比要查找的数字小,需要接着往右边找。

以上可以看出,二叉树的数据检索取决于数据的分布情况,不适合用作索引的数据结构,因为二叉树的深度太深的话,IO 操作会特变多,查询效率就会很低,因此若想二叉树的查询效率尽可能高,需要这棵二叉树是平衡的,从而引出新的数据结构,平衡二叉树(Balanced Binary Search Tree)或者完全平衡二叉树(又叫 AVL 树)。

平衡二叉树

平衡二叉树(Balanced Binary Search Tree 树)在符合二叉查找树的条件下,满足某一个节点的子节点的高度差不超过 1,也就是相对平衡;如果整棵树的所有节点的高度差不超过 1 就是完全平衡二叉树(又叫 AVL 树)。

树节点的数据存储结构示意图:

每个节点其实就是一个磁盘块,有 3 部分数据区,一个是关键字:用于存放主键或者其他索引的值,一个是数据磁盘块的地址,一个是子节点的引用,分别指向父节点的左子节点的引用和右子节点的引用。

以上面的平衡二叉树的图片为例,通过查找关键字为 10 的数据记录,来说明节点的查找过程说明:

1、先找到节点 15,把节点 15 加载到内存后,与 10 比较,发现比 10 大,那么需要找到 节点 15 的左子节点,也就是节点 8;

2、通过节点 15 的左子节点的引用,找到节点 8,把节点 8 加载到内存后,与 10 比较,发现比 10 小,那么需要找到节点 8 的右子节点,也就是节点 10;

3、通过节点 8 的右子节点的引用,找到节点 10,把节点 10 加载到内存后,与 10 比较,发现正好匹配,那么说明要查询的数据就是节点 10;

4、通过节点 10 的数据磁盘地址,找到数据区,进行数据的获取,返回到客户端即可。

二叉树存在数据分布不均匀,出现查询深度太深,平衡二叉树解决了数据分布相对平衡的事情,但是用平衡二叉树作为索引的话还是有问题,原因主要有两个:

一个就是数据节点的深度决定了磁盘的 IO 操作次数,IO 操作非常消耗时间,从上图可以看出 9 条记录,如果查找 30 就需要 4 次 IO 操作,如果记录成千上万,这种 IO 操作是巨大的灾难。

另外一个就是平衡二叉树的节点磁盘块保存的数据量太少,它没有很好的利用操作系统读取磁盘 IO 的数据交互特性(操作系统去磁盘上读取的数据是 4KB,交互的单位是以页为单位的),以上的二叉树数据结构一个节点不可能用满 4KB 的空间;也没有利用好磁盘 IO 的预读能力(即空间局部性原理)(磁盘预读能力就是当你一次 IO 读取到数据的页后,会认为你马上要读取相邻的数据页,所以磁盘会多返回几个页的数据到内存),从而带来频繁的 IO 操作。

多路平衡查找树

多路平衡(B-Tree)是指每个节点可以有多个分支,也就是可以有多个子节点,二叉树就是 2 个子节点,有几个子节点就是几路。

多路平衡与二叉平衡相比,可以大大减少树的深度,从而减少 IO 的操作次数。

多路平衡查找树的节点里的关键字最多有(路数-1)个,如果用 N 来表示路数,那么关键字的个数最多就是 N-1 个。

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

由于 MySQL 数据库里默认的一页是 16KB,因此在数据库设计的时候要特别注意,如果一个列的长度太大,该列用作索引时,占用的空间就大,那么以此列为索引的索引文件的路数就会减少,从而使树的深度增加,也就使 IO 的操作次数增加,导致数据库性能下降,这也就是人们常说的创建字段的时候,字段的长度尽量小一点,不要太大的原因。

B-Tree 是一个绝对平衡的查找树,也就是所有的子节点都在一个高度上,为了维持树的绝对平衡,在数据插入更新操作时,会通过一些分裂组合的操作来维持,这块也是比较消耗性能的,这也就是人们常说的索引建立够用就行,建立索引不易太多的主要原因。因为索引建多了,当数据插入或者更新的时候,维护索引的成本也是很大的。

本文分享自微信公众号 - Java后端技术栈(t-j20120622),作者:田老师

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 程序员,你心里就没点‘树’吗?

    看官,不要生气,我没有骂你也没有鄙视你的意思,今天就是想单纯的给大伙分享一下树的相关知识,但是我还是想说作为一名程序员,自己心里有没有点树?你会没点数吗?言归正...

    用户4143945
  • 漫画算法:5分钟搞明白红黑树到底是什么?

    红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:

    用户4143945
  • IO入门--基本概念

    所谓IO即input和output的缩写,是对数据的流入和流出的一种抽象,编程中很常见的一个概念。

    用户4143945
  • [leetcode二叉树系列]3 二叉树的最大深度

    二叉树的遍历和队列的相关概念前面已经介绍,忘记了的小伙伴复习后再看效果一定翻倍哟!

    我是程序员小贱
  • [leetcode二叉树系列]4 对称二叉树

    二叉树的遍历和队列的相关概念前面已经介绍,忘记了的小伙伴复习后再看效果一定翻倍哟!

    我是程序员小贱
  • 「leetcode二叉树系列」4 对称二叉树

    二叉树的遍历和队列的相关概念前面已经介绍,忘记了的小伙伴复习后再看效果一定翻倍哟!

    小林coding
  • [leetcode二叉树系列]2 二叉树的层次遍历

    二叉树的遍历和队列的相关概念前面已经介绍,忘记了的小伙伴复习后再看效果一定翻倍哟!

    我是程序员小贱
  • 关于二叉树,你该了解这些!

    说道二叉树,大家对于二叉树其实都很熟悉了,本文呢我也不想教科书式的把二叉树的基础内容在啰嗦一遍,所以一下我讲的都是一些比较重点的内容。

    代码随想录
  • Git 项目推荐 | 基于 C# 的极速 WEB + ORM 框架

    NFine 是基于 C# 语言的极速 WEB + ORM 框架,其核心设计目标是开发迅速、代码量少、学习简单、功能强大、轻量级、易扩展,让Web开发更迅速、简单...

    码云Gitee
  • 基础知识 | 每日一练(46)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    闫小林

扫码关注云+社区

领取腾讯云代金券