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

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

数据结构B树B+树

一.什么是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索引结构中的应用

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2024/05/03 23:29