数据结构和算法 十四、B树和B+树
一、B树(B Tree)
1、概述
B-Tree 是一种自平衡的搜索树。在大多数其他自平衡搜索树(如AVL和红黑树),假设一切都在主存储器中。要了解 B-Trees 的使用,我们必须考虑无法放入主存的大量数据。当键数较多时,以块的形式从磁盘中读取数据。与主存访问时间相比,磁盘访问时间非常长。使用 B-Tree 的主要思想是减少磁盘访问次数。大多数树操作(搜索、插入、删除、max、min、..etc)需要 O(h) 磁盘访问,其中 h 是树的高度。B树是一棵肥树。通过在 B-Tree 节点中放置最大可能的键来保持 B-Tree 的高度较低。通常,B-Tree 节点大小保持等于磁盘块大小。
2、特性
1、所有叶子都处于同一水平。
2、B树由术语最小度't'定义。t 的值取决于磁盘块的大小。
3、除根以外的每个节点都必须包含至少 t-1 个键。
4、所有节点(包括根节点)最多可以包含 2*t – 1 个键。
5、节点的子节点数等于其中的键数加 1。
6、节点的所有键都按升序排序。两个键 k1 和 k2 之间的孩子包含 k1 和 k2 范围内的所有键。
7、B-Tree 从根开始生长和收缩,这与二叉搜索树不同。二叉搜索树向下生长,也向下收缩。
8、与其他平衡二叉搜索树一样,搜索、插入和删除的时间复杂度为 O(log n)。
9、B-Tree 中节点的插入仅发生在叶节点处。
3、示例
以下是最小阶数为 5 的 B-Tree 的示例。在实际的 B-Trees 中,最小阶数的值远大于 5。
在上图中看到,所有叶子节点都处于同一级别,并且所有非叶子节点都没有空子树,并且键的数量比其子节点的数量少一。
4、操作
在 B 树上执行某些操作时,B 树的任何属性都可能违反,例如节点可以拥有的最小子节点数。为了保持 B 树的属性,树可以分裂或加入。
![](https://img-blog.csdnimg.cn/521b6e5d64b5422da12aed8be9493fed.gif)
5、应用
B树大量应用在数据库和文件系统当中。B 树用于索引数据并提供对存储在磁盘上的实际数据的快速访问,因为访问存储在存储在磁盘上的大型数据库中的值是一个非常耗时的过程。
它的设计思想是,将相关数据尽量集中在一起,以便一次读取多个数据,减少硬盘操作次数。B树算法减少定位记录时所经历的中间过程,从而加快存取速度。
二、B+树
1、概述
B+ 树是 B 树的扩展,它允许高效的插入、删除和搜索操作。
在 B 树中,键和记录都可以存储在内部节点和叶节点中。而在 B+ 树中,记录(数据)只能存储在叶子节点上,而内部节点只能存储键值。
B+树的叶子节点以单链表的形式链接在一起,使搜索查询更加高效。
B+树用于存储无法存储在主存储器中的大量数据。由于主存的大小总是有限的,B+树的内部节点(访问记录的键)存储在主存中,而叶节点存储在辅助内存中。
2、属性
(1)a阶B+树的内部节点结构
1、每个内部节点的形式为:
<P 1 , K 1 , P 2 , K 2 , ....., P c-1 , K c-1 , P c >
其中 c <= a 并且每个P i是一棵树指针(即指向树的另一个节点),并且每个K i是一个键值
2、每个内部节点都有:K 1 < K 2 < ...。< ķ c-1
3、对于 P i指向的子树中的每个搜索字段值“X” ,以下条件成立:
K i-1 < X <= K i,对于 1 < i < c 并且,
K i-1 < X,对于 i = c
4、每个内部节点最多有“一个”树指针。
5、根节点至少有两个树指针,而其他内部节点每个都至少有 \ceil(a/2) 树指针。
6、如果任何内部节点有'c'指针,c <= a,那么它有'c - 1'键值。
(2)'b' 阶 B+ 树的叶节点结构如下
1、每个叶节点的形式为:
<<K 1 , D 1 >, <K 2 , D 2 >, ....., <K c-1 , D c-1 >, P next >
其中 c <= b 和每个D i是一个数据指针(即指向磁盘中键值为 K i的实际记录或指向包含该记录的磁盘文件块),每个K i是一个键值,并且P next指向下一个叶节点在 B+ 树中(参见图 II)。
2、每个叶节点有:K 1 < K 2 < ...。< K c-1 , c <= b
3、每个叶节点至少有 \ceil(b/2) 值。
4、所有叶节点都在同一级别。
3、示例
下图显示了一个3阶的B+树。
4、与B-Tree比较
B树 | B+树 |
---|---|
数据存储在叶节点和内部节点中。 | 数据仅存储在叶节点中。 |
由于数据存储在内部节点和叶节点中,因此搜索速度有点慢。 | 由于数据仅存储在叶节点中,因此搜索速度更快。 |
不存在冗余搜索键。 | 可能存在冗余搜索键。 |
删除操作很复杂。 | 删除操作很简单,可以直接从叶子节点中删除数据。 |
叶节点不能链接在一起。 | 叶节点链接在一起形成一个链表。 |
相关文章
- 数据结构与算法栈的详解_数据结构怎么判断出栈的顺序
- 八皇后问题递归算法思想_迷宫在数据结构中的地位
- 数据结构b-树和b+树_A票领导B票算法
- 图的数据结构_数据结构关于图的算法
- 智驾车技术栈 | Apollo规划模块详解(二):算法实现-数据检查及更新
- 【数据结构】— kmp算法和strstr函数
- 数据结构篇——KMP算法
- 「数据结构与算法Javascript描述」栈
- 【算法竞赛 - 搜索】Eight II
- 外网疯传!字节大佬闭关三月撰写的数据结构与算法笔记遭恶意开源
- 算法与数据结构之最大/最小堆
- 新项目构思 | 小半个性文章推荐算法
- 二叉树、队列、栈、广义表(二)数据结构与算法(十八)
- Go 数据结构和算法篇(十四):哈希表、哈希函数、哈希冲突和哈希算法
- 分布式缓存的路由算法是如何实现的?
- 七日算法先导(一)—— 数组
- PTA 数据结构与算法题目集(中文)7-44 基于词频的文件相似度 (30分)
- 技术盛宴来袭,黑客马拉松开赛,这场专注算法与创新的技术盛宴邀你来看!
- Java数据结构和算法(四)——栈详解编程语言
- Python杨辉三角算法详解编程语言
- Python数据结构与算法详解编程语言
- 并非完全依赖算法:苹果自称雇佣 500 人手动审核每份应用提交申请
- PHP数据结构算法三元组Triplet
- php全排列递归算法代码
- C语言实现的PNPoly算法代码例子