B/B+树(二) 详细分析

/ 默认分类 / 0 条评论 / 255浏览

一.什么是B树?

满足下列要求的m叉树就是B树:

B树的节点基本结构如下: image.png 其中n表示当前节点有多少个关键字。

所谓关键字可以理解为实际存储的数据单元,比如二叉树中我们,我们的节点结构基本都是下面这样,也就是一个左孩子指针和一个右孩子指针,外加一个关键字data,其实也就是存储的数据单元了。image.png

也就是说,一个m路的B树,单个节点最多有m个孩子,并且最多有m-1个关键字(因为关键字都是在子孩子指针夹中间)。

所以通常一个B树一定是类似下面的结构(下面是m=4的四阶B树): image.png 可以看到,单个节点最多有三个关键字。

二.使用B树作为数据存储索引会有什么问题?

2.1 磁盘预读

在讨论这个问题之前,我们先来复习下操作系统的相关知识。 cpu执行IO系统调用,将数据从磁盘读到内存中,这个过程读取的交互涉及最小逻辑单元,一般称为存储页。页的大小由操作系统决定,通常是4k或者8k,在进行数据读取的时候,通过取整数倍的页大小进行一次性读取。也就是说可能预读取了一部分额外的数据。这样做其实也就是减少IO的次数,提高IO交互效率。

下面是在我的电脑上创建的一个简单的文本文件,然后操作系统显示的存储信息: image.png 这个文本的内容只有一个"test",实际数据大小是4Byte,但是在磁盘上实际占用的是4KB的空间,这其实就是因为最小逻辑单元是页,也就是4KB。

2.2 B树作为存储索引的问题

上面我们画了一个4阶的B树,但是我们只画出了关键字和孩子指针,实际场景中每个关键字其实还对应了实际的数据项。比如这样: image.png

假设每个B树的节点大小是16KB,再假设每个用户数据的大小是1KB,而孩子指针的大小先忽略不计,那么对于三层高度的子树来说,最多就是每个节点存储16个关键字和相应的用户数据(也就是17阶B树),那么这颗子树最多可以存储的数据量就是:16+1716+1717*16=4912条用户数据。

当数据更多时,比如达到百万级别,那么这颗树就会变得很高,而每一次向下查询一个高度的节点都需要进行一次IO操作,因此B树不是作为数据存储的理想数据结构,尤其是大数据量存储,或者一些文件系统。

三.B+树

类似于手机厂商命名一样,iphone12,iphone12plus,B+树其实也就是在B树的基础上进行了一些改动和针对性优化。使得在大数据量的场景下,不会出现B树那样的因为存储空间有限导致的高度增加的问题。 这其中核心的思想就是将原来B树上存储的实际的数据单元(如上面说的用户数据),全部移动到树的叶子节点上,这样做之后,每个非叶子节点就只存储关键字和指针(比如关键字可以是数据的主键id),那么这些数据的占用空间很小,16kb的数据单元大小就可以存储大量的关键字和指针。另外,叶子节点将会包含整棵树的全部数据。 也就是类似下面的结构: image.png 上面也就是最基本的B+树的结构了,可以看到,数据都在叶子节点,叶子节点之间有指针连接。非叶子节点没有实际数据,这样可以存储更多的指针和关键字,使得在数据量很大的情况下,也可以保持树的高度不会很高,降低查询时磁盘IO的次数。 每个节点中,数据也是有序的,从左到右递增,并且每个节点数据的孩子节点的所有数据一定都小于当前数据。比如上面的根节点的38的孩子有数据16和29,都是小于38;而大于等于的都在右边,比如根节点67的右孩子的数据是90和94,都是大于67;

这样,比如我们需要查找数据58的时候,从根节点开始,58大于38,58小于67,所以找到67的左孩子,找到55,58大于55,58等于58,所以找到58的右孩子,然后从当前叶子节点顺序查找就可以找到58的用户数据了。

下一篇文章和大家一起分析一下B+树在mysql索引结构中的应用