数据结构之「B+树」

深藏阁楼爱情的钟 2022-01-20 08:43 245阅读 0赞

### B+树 ###

**B+树** 是 B树 的扩展，允许有效的插入，删除和搜索操作。

在 B树 中，键和记录（数据）都可以存储在内部节点和叶子节点中。 然而，在 B+树 中，记录只能存储在叶节点上，而内部节点只能存储键值。

B+树 的叶节点以单链表的形式链接在一起，解决区间查询，以使搜索查询更加高效。

B+树 用于无法存储大量的数据在主存储器中。 由于主存储器的大小总是有限的，B+树 的内部节点（访问记录的键）存储在主存储器（内存）中，而叶节点存储在辅助存储器（硬盘）中。由于内存的查询速度远大于硬盘，就可以把 键 放入内存，把 记录 放入硬盘，以达到最优方案。

B+树 的内部节点通常称为索引节点。

在 B+树 中的节点通常被表示为一组有序的元素和子指针。如果此 B+树 的阶数是m，则除了根之外的每个节点都包含最少 m/2 个元素最多 m 个元素，对于任意的结点有最多 m 个子指针。对于所有内部节点，子指针的数目总是与元素的数目相同。所有叶子都在相同的高度上，叶结点本身按关键字大小从小到大链接。

### B+树 的优点 ###

可以在相同数量的磁盘访问中获取记录。 树的高度保持平衡，与 B树 相比较少。 我们可以顺序访问存储在 B+树 中的数据，也可以直接访问。 键用于索引。 更快的搜索查询，因为数据仅存储在叶节点上。

### B+树 的实现 ###

**1.查找** 类似于 **二叉查找树**。起始于根节点，自顶向下遍历树，选择其分离值在要查找值的任意一边的子指针。

**2.插入** 首先，查找到要插入其中的节点的位置。接着把值插入这个节点中。

如果没有节点违反 B+树 的规则（不能大于 m-1 个元素）直接成功返回。

如果某个节点有过多元素，则把它分裂为两个节点，每个都有最小数目的元素。在树上递归向上继续这个处理直到到达根节点，如果根节点被分裂，则创建一个新根节点。分裂的节点一般是这组元素的中位数。

**3.删除** 首先，查找到要删除的值，从叶子节点中删除键和数据。

如果没有节点违反 B+树 的规则（不能小于 m/2 个元素）直接成功返回。

如果叶节点包含少于最小数量的元素，则将节点与其兄弟节点合并，并删除它们之间的键。

如果索引节点包含少于最小数量的元素，则将节点与兄弟节点合并，并在它们之间向下移动键。

### B-树 与 B+树的区别 ###

1.搜索键无法重复存储； 可以存在冗余搜索键。 2.数据可以存储在叶节点以及内部节点中；数据只能存储在叶节点上。 3.搜索某些数据的过程较慢，因为可以在内部节点和叶节点上找到数据； 搜索速度相对较快，因为只能在叶节点上找到数据。 4.删除内部节点非常复杂且耗时；删除永远不会是一个复杂的过程，因为元素将始终从叶节点中删除。 5.叶节点不能链接在一起；叶节点链接在一起以使搜索操作更有效。

### 总结 ###

B+树 把内部节点当作键来存储，存储的元素比较少，可以放入内存中，提升查询效率。叶子节点里存储里键和数据，适合放入硬盘，只需要少量的读取硬盘即可完成查询。因为内存的读取比硬盘块很多，所以效率提升很多。

由于 B+树 内部节点只有键，存储内容较少，增删查时间复杂度为 O(log n)，叶子节点链接在一起，可以区间查询等，所以非常适合做数据库索引存储结构。数据库主键索引最好是自增的，以提升插入效率。

PS:  
清山绿水始于尘，博学多识贵于勤。  
我有酒，你有故事吗？  
公众号：「**清尘闲聊**」。  
欢迎一起谈天说地，聊代码。

发表评论取消回复

表情：

评论列表（有 0 条评论，245人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】B树，B+树，B*树

B树的插入，B+树的插入，B*树

桃扇骨/ 2024年04月21日 19:19/ 0 赞/ 87 阅读

相关数据结构之B树和B+树整理

B树又称多路平衡查找树，所有结点的最大孩子数称为阶。一般用m来指代。 B树的性质对于m阶的B树： 1. 每个结点最多有m棵子树，自身最多有m-1个关键字

- 日理万妓/ 2023年02月19日 05:23/ 0 赞/ 9 阅读

相关数据结构--B 树、B+ 树、B* 树

1. B 树、B+ 树、B\ 树 1.1. 前言 > 前面讨论的二叉查找树（Binary Search Tree），平衡二叉查找树（Balanced BinaryS

た入场券/ 2022年08月20日 04:26/ 0 赞/ 219 阅读

相关数据结构五之B+树

你看，像这个B树，B+树，数据库索引，这些基础，你在大学里都学过吧。。。。。。放屁，大学里哪学过这些。------------你知道我是在讽刺我的大学吗？不过，我仍然对我的

我不是女神ヾ/ 2022年05月29日 08:41/ 0 赞/ 188 阅读

相关数据结构之B-树、B+树

B树的概念是为了解决一些现实问题而提出的，当数据量太大时，而内存中又无法存储这么多的数据，那么就需要将数据存储在磁盘上，如果继续采用平衡树的方法就会带来一些问题，平衡树每个节点

我就是我/ 2022年05月27日 14:09/ 0 赞/ 223 阅读

相关数据结构之B树

1.0 简介 1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B\_树）。一棵m阶B树(

女爷i/ 2022年05月25日 05:17/ 0 赞/ 213 阅读

相关数据结构之B+树

1.0 简介 B+ 树是一种树数据结构， 1. B+树是B树的一种变体 2. 所有信息都存储在终端结点中 3. 每一个关键码对应一个子树 4. 内部节点的值是记

痛定思痛。/ 2022年05月25日 05:17/ 0 赞/ 182 阅读

相关数据结构之「B+树」

B+树 B+树是 B树的扩展，允许有效的插入，删除和搜索操作。在 B树中，键和记录（数据）都可以存储在内部节点和叶子节点中。然而，在 B+树中，记录只能存储

深藏阁楼爱情的钟/ 2022年01月20日 08:43/ 0 赞/ 246 阅读

相关数据结构 —— B+树

文章目录前言 1 、B+树的定义 1.1、B+树的补充说明: 2、B+树的插入操作 2.

我不是女神ヾ/ 2021年10月19日 09:34/ 0 赞/ 338 阅读

相关数据结构 —— B树

文章目录 1、B树的定义 1.1、B树的特性 1.2、B树的高度 1.3、性能分析 1.4、B树的补充说明

朱雀/ 2021年10月19日 09:26/ 0 赞/ 628 阅读