登录
首页 >  数据库 >  MySQL

Mysql 索引模型 B+ 树详解

来源:SegmentFault

时间:2023-01-22 09:40:41 238浏览 收藏

在IT行业这个发展更新速度很快的行业,只有不停止的学习,才不会被行业所淘汰。如果你是数据库学习者,那么本文《Mysql 索引模型 B+ 树详解》就很适合你!本篇内容主要包括Mysql 索引模型 B+ 树详解,希望对大家的知识积累有所帮助,助力实战开发!

一、认识二叉树

首先,在了解 mysql 中的 B+ 树之前,我们需要搞懂什么是二叉树。二叉树是一种常见的非线形数据结构,数据是以一对多的形态组织起来的,我画了一张图来帮助你理解:

在这里插入图片描述

在二叉树中,有一种比较特殊的,也是最常用的二叉树,那就是二叉搜索树,也叫做二叉查找树。它最大的特点是:对于树中的任意一个节点,假如节点值为 x,其左子树节点的值必须小于 x,其右子树节点的值必须大于 x,就像下图的这几种数据排列结构:

在这里插入图片描述

那为什么需要使用二叉搜索树这种结构呢,它有什么好处吗?我们知道,常见的线性表结构,例如链表,要查找一个数据,必须从头开始遍历链表,在最坏的情况下,需要遍历整个链表才能够找到需要的数据。

而使用二叉搜索树这种结构,在树结构趋于平衡的情况下,借助二分的思想,每次查找数据的时候,都会舍弃掉另一个子树,所以在平均情况下,我们只需要在 O(logn)(也就是树的高度)的时间复杂度内就可以查找到数据。

二、为什么会选择 B+ 树

在了解了二叉搜索树之后,我们就为学习 B+ 树打下了坚实的基础。只不过先别着急,我们再来明确一个问题,为什么 mysql 会选择 B+ 树做为其索引模型呢?其他的数据结构不行吗?

要搞懂这个问题,我们先想想,mysql 中最常见的操作是什么?既然是数据库,最常见的操作当然是数据查询了,好的,我以最常见的两条 sql 查询语句为例:

  • select * from T where id = 1;
  • select * from T where id > 10 and id 

一个是等值查询,一个是范围查询。

支持快速查询的常见数据结构有哈希表、平衡二叉查找树、跳表,我们依次来看看这几种结构能否做为 B+ 树的索引模型。

如果使用哈希表,虽然等值查询非常高效,但是数据的排列是无序的,所以并不支持范围查询。

在这里插入图片描述

如果使用平衡二叉查找树,例如红黑树、AVL 树等,可以在接近 O(logn) 的时间内找到数据,但是对于树结构来说,范围查询仍然是很低效的,因为只能中序遍历一棵树得到一个有序的数据集,然后再依次查找。

在这里插入图片描述

如果使用跳表,等值查询的效率和平衡二叉查找树差不多,并且也支持范围查询,例如下图中,我们查找节点 7(红色粗线为查找路径),如果需要范围查询的话,可以顺着原始链表依次遍历下去,因为链表节点之间是有序的。

在这里插入图片描述

这样来说的话,跳表也是可以做为索引模型的,但 mysql 还是选择了 B+ 树,实际上 B+ 树和跳表的设计思想有一些类似的地方,我们现在来看看 B+ 树是什么样子的。

三、B+ 树模型

1. B+ 树的优点

对数据构建索引,我们可以使用平衡二叉查找树,并且稍微做一下改造,把树的叶子节点使用链表串联,并且是从小到达顺序排列的,那么这种结构就能够支持等值查询和范围查询了,如下图:

在这里插入图片描述

当查找到一个节点之后,我们继续向后遍历,就能够实现高效的范围查询了。值得一提的是,这里串联叶子节点的链表,应该使用双向链表,方便在数据查询后进行升序或者降序操作。

这种结构虽然高效,但存在一个致命的问题,那就是太消耗内存空间了。

假如我们给 1000 万条数据建立索引,每个节点假设大约占用 16 字节的空间,那么构建一个索引大概就需要 150MB 内存,实际上我们还会给很多张表的很多字段建立索引,这样的话内存空间消耗还是太大了。

所以我们可以根据空间换时间的思想,使用磁盘来代替内存,磁盘是一种慢速的存储设备,造价也比内存低廉很多,因此我们可以将数据存储到磁盘上,只不过这样数据查询的速度就会慢一些了。

针对这种数据存储的方式,如果我们还是用上述的那种二叉树结构的话,每访问一层节点就对应着一次磁盘 IO,那这样的查询速度还是太慢了。因此我们可以改造一下上图中的这个结构,将二叉变成 n 叉,这样每一层节点存储的数据变多了,树的高度也降低了,访问磁盘的次数变少了,相应的查询性能就能够得到提升。

比如存储 30 个数据,构建二叉树的高度是 5,而 5 叉树的高度仅为 3:

在这里插入图片描述

如果数据量再大一点,就更能看出差别了,比如我们构建的是 100 叉树,那么存储 1 亿个数据,树的高度也只是 5 ,这样的话磁盘 IO 的操作次数就被大大的降低了。

那么在实际的应用中,到底应该构建多少叉树呢?是不是树的节点越多,即 n 越大越好?我们知道,操作系统对磁盘的访问是以页为单位读取的,每页的大小通常是 4KB,也就是说我们只需要将 n 叉树的每个节点存储为一页大小左右,这样每次访问都能够整页读取,不会进行多余的磁盘 IO 操作。

假如每页的大小可以存储 3 个数据,那么最终的 B+ 树结构就是这个样子:

在这里插入图片描述

2. B+ 树的缺点

这样来看的话,似乎 B+ 树已经比较完美的解决了数据索引的问题,但是,天下没有免费的午餐,B+ 树对查询操作有了很大的提升,但同时也降低了数据插入和删除的效率。

这个问题似乎不难理解,当我们不断插入数据的时候,B+ 树中的节点肯定会越来越多,直到大于了页大小,这时,为了维护查询的效率,不产生多余的 IO 操作,我们不得不进行节点的重构。

假如叶子节点的数量是 m,当节点数量大于 m 的时候,该节点就会分裂,从叶子节点的最中间的那个节点,让其成为父节点,节点左右的值,分别成为新的左右子节点;如果上一层又超过了限制,则继续向上进行分裂,直到影响到根节点,参照下面的图就很容易理解了:

在这里插入图片描述

删除也是类似的道理,当叶子节点过少,例如少于 m / 2 的时候,就可以将节点合并至旁边的兄弟节点。你可以自己参照插入的思路,想想删除是怎么进行节点重构的。

好了,这篇文章讲述了 mysql 的索引模型 B+ 树,首先需要了解一下二叉树,这是学习 B+ 树的前提,然后我以两个最常见的查询 sql,向你描述了为什么其他的常见数据结构不适合用来做索引,然后由此引出了 B+ 树。

根据数据查询和存储的特点,对平衡二叉树逐步改造成了 B+ 树,B+ 树对数据查询起到了很好的作用,但是它也带有副作用,那就是对插入删除操作有影响,于是需要进行节点的重构。

为了帮助你更深刻的理解并学习 B+ 树,这里贴一下其他关于 B+ 树的优秀文章:

https://zh.wikipedia.org/wiki/B%2B%E6%A0%91
https://zhuanlan.zhihu.com/p/27700617
https://www.cnblogs.com/nullzx/p/8729425.html

好了,本文到此结束,带大家了解了《Mysql 索引模型 B+ 树详解》,希望本文对你有所帮助!关注golang学习网公众号,给大家分享更多数据库知识!

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