【数据结构】树结构(B树、23树、B+树)

简介: 【数据结构】树结构(B树、23树、B+树)

一、二叉树和B树

1、二叉树的问题

二叉树需要加载到内存的,如果二叉树的节点很多, 就存在问题:

  1. 在构建二叉树时,需要多次进行 i/o 操作(海量数据存在数据库或文件中),节点海量,构建二叉树时速度有影响
  2. 节点海量,也会造成二叉树的高度很大,会降低操作速度.

2、多叉树

多叉树(multiway tree):每个节点可以有更多的数据项和更多的子节点

多叉树通过重新组织节点,减少树的高度,能对二叉树进行优化。

3、B树基本介绍

B 树通过重新组织节点,降低树的高度,并且减少 i/o 读写次数来提升效率。

文件系统及数据库系统的设计者利用了磁盘预读原理,将一个节点的大小设为等于一个页(页得大小通常为 4k), 这样每个节点只需要一次 I/O 就可以完全载入

二、2-3树

1、2-3树的特点

  1. 所有叶子节点都在同一层(只要是 B 树都满足这个条件)
  2. 2-3 树是由二节点和三节点构成的树。
  3. 有两个子节点的节点叫二节点,二节点要么没有子节点,要么有两个子节点;有三个子节点的节点叫三节点,三节点要么没有子节点,要么有三个子节点。

2、2-3树构建规则

  1. 当按照规则插入一个数到某个节点时,不能满足上面三个要求,就需要拆,先向上拆,如果上层满,则拆本层,拆后仍然需要满足上面 3 个条件。
  2. 对于三节点的子树的值大小仍然遵守(BST 二叉排序树)的规则

3、2-3树构建实例

23Tree

4、2-3-4树

234Tree

三、B树、B+树、B*树

1、B树

B-tree 树即 B 树,B 即 Balanced,平衡的意思。(有人把 B-tree 翻译成 B-树,B-tree 就是指的 B 树)

Mysql的某种类型的索引是基于 B 树或者 B+树的

bTree

  1. B 树的阶:节点的最多子节点个数。比如 2-3 树的阶是 3,2-3-4 树的阶是 4尚硅谷 Java 数据结构和算法。
  2. B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点。
  3. 关键字集合分布在整颗树中, 即叶子节点和非叶子节点都存放数据。
  4. 搜索有可能在非叶子结点结束。
  5. 其搜索性能等价于在关键字全集内做一次二分查找 。

2、B+树

B+树是 B 树的变体,也是一种多路搜索树。

b+Tree

B+树的搜索与 B 树也基本相同,区别是 B+树只有达到叶子结点才命中(B 树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找

所有关键字都出现在叶子结点的链表中(即数据只能在叶子节点【稠密索引】),且链表中的数据是有序的。

非叶子结点相当于是叶子结点的索引【稀疏索引】,叶子结点相当于是存储(关键字)数据的数据层

B+树更适合文件索引系统,B 树和 B+树各有自己的应用场景,不能说 B+树完全比 B 树好,反之亦然

3、B*树

B*树是 B+树的变体,在 B+树的非根和非叶子结点再增加指向兄弟的指针。

b*Tree

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为 2/3,而 B+树的块的最低使用率为的 1/2。B*树分配新结点的概率比 B+树要低,空间使用率更高。

目录
相关文章
|
7月前
|
算法 Java
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
159 3
 算法系列之数据结构-Huffman树
|
7月前
|
存储 自然语言处理 数据库
【数据结构进阶】AVL树深度剖析 + 实现(附源码)
在深入探讨了AVL树的原理和实现后,我们不难发现,这种数据结构不仅优雅地解决了传统二叉搜索树可能面临的性能退化问题,还通过其独特的平衡机制,确保了在任何情况下都能提供稳定且高效的查找、插入和删除操作。
516 19
|
9月前
|
存储 C++
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
197 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
9月前
|
Java C++
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
187 12
|
9月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
167 10
|
9月前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
263 3
|
11月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
291 5
|
11月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
227 59
|
4月前
|
编译器 C语言 C++
栈区的非法访问导致的死循环(x64)
这段内容主要分析了一段C语言代码在VS2022中形成死循环的原因,涉及栈区内存布局和数组越界问题。代码中`arr[15]`越界访问,修改了变量`i`的值,导致`for`循环条件始终为真,形成死循环。原因是VS2022栈区从低地址到高地址分配内存,`arr`数组与`i`相邻,`arr[15]`恰好覆盖`i`的地址。而在VS2019中,栈区先分配高地址再分配低地址,因此相同代码表现不同。这说明编译器对栈区内存分配顺序的实现差异会导致程序行为不一致,需避免数组越界以确保代码健壮性。
61 0
栈区的非法访问导致的死循环(x64)
232.用栈实现队列,225. 用队列实现栈
在232题中,通过两个栈(`stIn`和`stOut`)模拟队列的先入先出(FIFO)行为。`push`操作将元素压入`stIn`,`pop`和`peek`操作则通过将`stIn`的元素转移到`stOut`来实现队列的顺序访问。 225题则是利用单个队列(`que`)模拟栈的后入先出(LIFO)特性。通过多次调整队列头部元素的位置,确保弹出顺序符合栈的要求。`top`操作直接返回队列尾部元素,`empty`判断队列是否为空。 两题均仅使用基础数据结构操作,展示了栈与队列之间的转换逻辑。