树总结相关

概述

1. 树是一种层次结构的数据结构，它由节点（Node）和边（Edge）组成

特点

层次关系

1. 树形结构具有明确的层次关系，最上层的节点称为根节点（Root）
2. 每个节点都有零个或多个子节点（Child），没有父节点（Parent）的节点就是根节点

无环性

1. 树中不存在环路，即从一个节点沿着树的边不能回到自身

连通性

1. 树中的任意两个节点之间有且只有一条路径

递归定义

1. 树是一种递归定义的数据结构
2. 一个树可以看作是由根节点和若干子树组成，每棵子树又是一个树

树的分类总结

普通树

1. 树是一种数据结构，包含很多状态，如二叉树、三叉树、四叉树等
2. 这些状态描述的是每个节点可以有多少子节点

二叉树（Binary Tree）形态

1. 每个节点最多有两个子节点，通常称为左子节点和右子节点

2. 普通二叉树：

   1. 没有特定的性质约束，任意结构的二叉树

3. 完全二叉树（Complete Binary Tree）

   1. 除了最后一层，其他每一层都是满的
   2. 最后一层的节点从左到右依次排列（缺失的节点都在右边）

4. 满二叉树（Full Binary Tree）

   1. 每个节点要么是叶子节点（没有子节点），要么有两个子节点
   2. 所有叶子节点都在同一层次上

二叉搜索树（Binary Search Tree, BST）

1. 一种特殊的二叉树，满足左子节点的值小于父节点的值，右子节点的值大于父节点的值
   1. 对于任意节点n，其左子树中的所有节点的值都小于n的值，其右子树中的所有节点的值都大于n的值
   2. 这种结构允许快速的查找、插入和删除操作，时间复杂度为O(log n)（在平衡的情况下）

平衡二叉树（Balanced Binary Tree）

1. 在二叉搜索树的基础上，进一步要求任一节点的左子树和右子树的高度差不超过一定的值（通常是1）

   1. 通过平衡操作（如旋转）保持树的高度接近最优，使得查找、插入和删除操作的时间复杂度为O(log n)

2. 常见的平衡二叉搜索树有：

   1. AVL树
   2. 红黑树

多叉树

1. 每个节点的子节点数量可以超过2个

多路搜索树

1. 定义
   1. 多路搜索树是一种树数据结构，其中每个节点可以有多个子节点（超过两个）
   2. 节点可以包含多个键值，并且子节点的数量与键值数量有关
   3. 主要用于高效的查找、插入和删除操作
2. 特点
   1. 每个节点可以包含多个键值
   2. 每个节点可以有多个子节点

平衡多路搜索树

1. 平衡多路搜索树是在多路搜索树的基础上，进一步要求树保持平衡，以确保操作的时间复杂度为O(log n)
   1. 通过特定的规则和操作（如节点分裂和合并）来保持树的高度平衡
2. 常见的平衡多路搜索树有：
   1. 2-3树
   2. 2-3-4树
   3. B树（B-Tree）
   4. B+树（B+ Tree）

图示

二叉树操作

插入

1. 从根节点开始，比较插入值和当前节点的值
2. 若插入值小于当前节点的值，则移到左子节点继续比较，若大于则移到右子节点
3. 直到找到一个空位置，将新节点插入

删除

1. 找到要删除的节点
2. 若该节点无子节点，直接删除
3. 若该节点有一个子节点，用子节点替代该节点
4. 若该节点有两个子节点，找到其右子树中的最小节点（或左子树中的最大节点），用该节点的值替代要删除的节点，然后删除该节点

查找

1. 从根节点开始，比较查找值和当前节点的值
2. 若查找值等于当前节点的值，返回该节点
3. 若查找值小于当前节点的值，移到左子节点继续查找
4. 若查找值大于当前节点的值，移到右子节点继续查找

遍历

1. 遍历是指按某种顺序访问树中的所有节点，常见的遍历方法有以下几种：
2. 前序遍历（Preorder Traversal）：
   1. 先访问根节点，然后访问左子树，最后访问右子树
   2. 根左右

3. 中序遍历（Inorder Traversal）：
   1. 先访问左子树，然后访问根节点，最后访问右子树
   2. 对于二叉搜索树，中序遍历的结果是有序的
   3. 左根右

4. 后序遍历（Postorder Traversal）：
   1. 先访问左子树，然后访问右子树，最后访问根节点
   2. 左右根

5. 层次遍历（Level Order Traversal）：
   1. 按层次从上到下、从左到右访问节点，通常使用队列实现

树高度

1. 树的高度是指从根节点到叶子节点的最长路径上的节点数

树的节点数

1. 统计树中节点的总数

树的叶子节点数

1. 统计树中叶子节点（没有子节点的节点）的数量

判断树是否平衡

1. 判断树是否平衡，即任意节点的左右子树高度差不超过1

树的直径

1. 树的直径是指树中任意两个节点之间最长路径上的节点数

镜像树

1. 将树变成其镜像树，即左右子树交换

AVL树

概述

1. AVL树是最早发明的自平衡二叉搜索树，它以两位发明者G.M. Adelson-Velsky和E.M. Landis的名字命名
2. AVL树的特点是每个节点的左右子树的高度差（平衡因子）不超过1
   1. 高度平衡的二叉搜索树

用途

1. 数据库索引
   1. AVL树常用于数据库管理系统中的索引结构
   2. 数据库索引需要高效的查找、插入和删除操作，而AVL树通过严格的平衡性保证了这些操作的时间复杂度为O(log n)，适合处理频繁的动态更新和查询
2. 内存管理
   1. 在内存管理系统中，AVL树可以用来管理空闲内存块
   2. 内存分配和回收操作需要快速查找和更新空闲块的信息，而AVL树的平衡性和高效性使其成为理想的选择
3. 实时系统
   1. AVL树适合用于实时系统中的任务调度和事件管理
   2. 实时系统需要保证操作的确定性和高效性，而AVL树通过保持树的平衡性，确保了操作的时间复杂度稳定在对数级别，适合用于严格的时间要求场景
4. 路由算法
   1. 在网络路由算法中，AVL树可以用于管理路由表
   2. 路由表需要频繁更新和查找操作，AVL树的平衡性和高效的查找性能能够保证路由操作的快速响应
5. 字符串处理
   1. AVL树可以用于字符串处理中的符号表实现，尤其是在编译器设计中
   2. 符号表需要快速查找和更新变量或函数的信息，AVL树能够高效管理这些符号，保证编译器的性能
6. 动态集合操作
   1. AVL树适用于实现动态集合操作的数据结构
   2. 在一些算法竞赛和在线评测系统中，AVL树用于实现集合数据结构，处理动态数据集的问题，保证了操作的高效性和稳定性
7. 操作系统中的文件系统
   1. 在一些文件系统中，AVL树用于管理文件目录结构
   2. 文件系统需要高效的文件查找和目录更新操作，AVL树能够提供高效的查找和更新性能，保证文件系统的响应速度
8. 游戏开发
   1. 在游戏开发中，AVL树可以用于管理游戏对象的碰撞检测
   2. 游戏中的对象通常需要频繁的插入、删除和查找操作，AVL树的平衡性保证了这些操作的高效性，从而提高游戏的性能和响应速度
9. 高精度计时器
   1. AVL树适用于实现高精度计时器
   2. 在一些系统中，需要管理大量的定时事件，AVL树通过平衡性保证了插入、删除和查找操作的高效性，适合用于高精度定时管理
10. 网络防火墙
    1. 在网络防火墙中，AVL树可以用于管理规则集
    2. 防火墙规则需要频繁的查找和更新操作，AVL树能够高效管理规则，保证防火墙的性能和安全性

插入操作

1. 按照二叉搜索树的规则插入新节点
2. 插入后从插入点开始向上回溯，更新每个节点的高度并检查平衡因子
3. 若某个节点失衡（平衡因子绝对值大于1），则需要通过旋转操作进行调整
   AVL树的旋转操作有四种：单右旋、单左旋、双右旋和双左旋

删除操作

1. 按照二叉搜索树的规则删除节点
2. 删除后从删除点开始向上回溯，更新每个节点的高度并检查平衡因子
3. 若某个节点失衡，则通过旋转操作进行调整

红黑树

概述

1. 红黑树是一种近似平衡的二叉搜索树，它通过约束节点的颜色（红或黑）和树的结构，保证树的平衡
   1. 近似平衡的二叉搜索树

特点

1. 点是红色或黑色
2. 根节点是黑色
3. 所有叶子节点（NULL节点）是黑色
4. 每个红色节点的两个子节点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

用途

1. 数据库实现
   1. 红黑树在数据库系统中被广泛应用，尤其是在实现索引结构时
   2. 红黑树通过保证树的平衡性，使得插入、删除和查找操作的时间复杂度保持在O(log n)级别，这对于需要频繁进行数据操作的数据库系统来说是非常重要的
2. 内存管理
   1. 在操作系统的内存管理中，红黑树用于管理空闲内存块
   2. 内存分配和回收操作需要高效的插入和删除操作，而红黑树的平衡性质使得这些操作能够在对数时间内完成
      例如，Linux内核中的Slab分配器使用红黑树来管理空闲内存块
3. STL
   1. C++标准模板库（STL）中的关联容器，如std::map和std::set，通常通过红黑树实现
   2. 这些容器需要支持高效的插入、删除和查找操作，而红黑树的特性正好满足这些要求
4. 多级缓存
   1. 在一些多级缓存系统中，红黑树用于管理缓存条目
   2. 红黑树的高效查找和更新操作使得它适合作为缓存的底层数据结构，保证缓存命中和替换操作的高效性
5. 动态集合操作
   1. 红黑树可以用于实现动态集合数据结构，支持集合的插入、删除和查找操作
   2. 例如，在一些算法竞赛和在线评测系统中，红黑树用于实现集合数据结构，处理动态数据集的问题
6. 网络路由表
   1. 在网络路由器中，红黑树可以用于实现路由表
   2. 路由表需要高效的查找操作来确定数据包的转发路径，而红黑树能够提供高效的查找性能
   3. 此外，红黑树的自平衡特性保证了路由表的性能稳定
7. 多任务调度
   1. 在操作系统的调度器中，红黑树用于管理任务队列
   2. 任务的插入、删除和查找操作需要高效的实现，以保证系统的响应速度和任务调度的公平性
   3. 红黑树的平衡特性和对数级别的操作时间复杂度使其成为调度器实现的理想选择
8. 事件驱动系统
   1. 在一些事件驱动系统中，红黑树用于管理定时器事件
   2. 定时器事件需要按照时间顺序进行处理，红黑树能够高效地插入和删除事件，同时保持事件的有序性，保证系统能够按时处理事件

左旋图示

左旋总结

1. 先保存目标节点 x 的右子节点 y
   1. 左旋的第一步就是将 x 的右子节点 y 保存起来，因为 y 会在后续操作中成为新的父节点
2. 让y的左子节点成为x的右子节点
   1. 如果 y 有左子节点，这个左子节点在左旋后会变成 x 的右子节点
   2. 这样可以保持树结构的完整性
3. 判断x的情况，让y代替x的位置
   1. 如果 x 是根节点（即 x 的父节点是 nullptr），就让 y 成为新的根节点
   2. 如果 x 是它父节点的右子节点，那么 y 需要成为它父节点的右子节点
   3. 如果 x 是它父节点的左子节点，那么 y 需要成为它父节点的左子节点
4. 让 x 重新成为树的一部分
   1. 让 x 成为 y 的左子节点，这一步是旋转的关键，确保 x 没有被移出树的结构
   2. 将 x 的父节点设置为 y，以完成旋转后的父子关系调整

右旋图示

右旋总结

1. 右旋是左旋的镜像过程
2. 先保存目标节点 x 的左子节点 y
3. 让 y 的右子节点成为 x 的左子节点
4. 判断 x 的情况，让 y 代替 x 的位置
   1. 和左旋一样
5. 让 x 重新成为树的一部分
   1. 让 x 成为 y 的右子节点
   2. 更新 x 的父节点为 y

示例代码

插入操作

删除操作

问题与理解

1. C++标准模板库（STL）中的std::map和std::set选择使用红黑树而不是AVL树，为什么？

   1. 插入和删除操作的平衡调整开销

      红黑树：
      红黑树的插入和删除操作通常涉及较少的旋转和颜色变换，插入操作最多需要两次旋转，删除操作也在常数次旋转内完成
      AVL树：
      AVL树需要在插入和删除操作中进行高度的重新平衡，这通常涉及更多次的旋转操作（插入最多需要两次旋转，删除可能需要多次旋转和重新平衡）
      比较：
      由于红黑树在这些操作上的旋转次数和调整代价较低，在需要频繁插入和删除操作的场景下，红黑树的性能通常优于AVL树

   2. 平衡条件的差异
      红黑树：
      红黑树的平衡条件较为宽松，只要求从根节点到任意叶节点的最长路径不超过最短路径的两倍
      这样的宽松条件允许红黑树保持相对较少的旋转操作，同时仍然保证O(log n)的时间复杂度
      AVL树：
      AVL树要求每个节点的左右子树高度差不超过1，这使得树高度非常接近最优，但也导致插入和删除操作需要更多的旋转和调整
      比较：
      红黑树的宽松平衡条件使得它在处理大量插入和删除操作时，性能更加稳定和高效

   3. 实际性能考虑
      在大多数应用场景中，查找操作的时间复杂度在O(log n)已经足够快速，而插入和删除操作的实际性能差异会对整体系统性能产生更大的影响
      红黑树在这种平衡性和调整开销上的折中使得它在实际应用中表现出更好的性能

   4. 历史原因和标准化
      红黑树的算法和实现细节在计算机科学领域得到了广泛研究和应用，其性能和稳定性在实际应用中得到了验证
      尽管AVL树在查找操作中具有较好的平衡性，但其在插入和删除操作中的调整开销较大，使得它在某些场景下不如红黑树高效

2-3树简介

概述

1. 2-3树是一种自平衡多路搜索树，每个节点可以有2个子节点（2节点）或3个子节点（3节点）
2. 2-3树保持平衡性，所有叶子节点在同一层次上

特点

1. 2节点：
   1. 包含一个键值和两个子节点
2. 3节点：
   1. 包含两个键值和三个子节点
3. 平衡性：
   1. 树保持高度平衡，所有叶子节点都在同一层次上
4. 操作效率：
   1. 查找、插入和删除操作的时间复杂度为O(log n)

结构

1. 2节点：
   1. 形式为 [K]，其中 K 是键值。
   2. 有两个子节点，左子节点的所有键值小于 K，右子节点的所有键值大于 K
2. 3节点：
   1. 形式为 [K1, K2]，其中 K1 和 K2 是键值，且 K1 < K2。
   2. 有三个子节点：
      第一个子节点的所有键值小于 K1
      第二个子节点的所有键值介于 K1 和 K2 之间
      第三个子节点的所有键值大于 K2

操作

1. 查找：
   1. 从根节点开始，根据键值的比较选择相应的子节点，递归进行，直到找到目标键值或达到叶子节点
2. 插入：
   1. 找到适当的叶子节点进行插入
   2. 如果插入导致节点超载（变成4节点），则需要分裂节点，并将中间键值提升到父节点中
   3. 分裂可能会递归地向上进行，直到根节点
3. 删除：
   1. 找到目标键值并删除
   2. 如果删除导致节点不足（少于1个键值），需要从兄弟节点借用键值或合并节点
   3. 合并或借用可能会递归地向上进行，直到根节点

用途

1. 主要用于实现B树或红黑树
2. 数据库实现
3. 文件系统
4. 内存管理
5. 磁盘存储
6. 动态集合操作
7. 索引和排序
8. 编译器实现
9. 实时系统
10. 高度并发系统
11. 游戏开发

示例

1. 假设有如下2-3树：
2. 根节点：
   1. [10, 20]
   2. 这是一个3节点，有两个键值 10 和 20
   3. 有三个子节点
3. 第一个子节点 [5, 7]：
   1. 所有键值都小于 10
4. 第二个子节点 [12, 15]：
   1. 所有键值都介于 10 和 20 之间
5. 第三个子节点 [25, 30]：
   1. 所有键值都大于 20

2-3树和B树

1. 相似点

   1. 平衡性：两者都保持高度平衡，确保所有叶子节点在同一层次上
   2. 操作：插入和删除操作都可能导致节点的分裂和合并，以维持树的平衡
   3. 用途：都适用于需要高效查找、插入和删除操作的应用场景，如数据库和文件系统

2. 区别点

   1. 节点类型
      2-3树：每个节点可以是2节点或3节点

      B树：每个节点可以包含更多的键值和子节点，具体数量取决于树的阶

   2. 灵活性
      2-3树：节点的类型和子节点数量较固定，只有2节点和3节点
      B树：节点的键值和子节点数量更灵活，可以根据树的阶调整

2-3-4树简介

概述

1. 2-3-4树是2-3树的扩展，每个节点可以有2个、3个或4个子节点

特点

1. 保持高度平衡，所有叶子节点在同一层次上
2. 每个节点最多可以有三个键值和四个子节点
3. 2节点：
   1. 包含一个键值和两个子节点
4. 3节点：
   1. 包含两个键值和三个子节点
5. 4节点：
   1. 包含三个键值和四个子节点

结构

1. 2节点：
   1. 形式为 [K]，其中 K 是键值
   2. 有两个子节点，左子节点的所有键值小于 K，右子节点的所有键值大于 K
2. 3节点：
   1. 形式为 [K1, K2]，其中 K1 和 K2 是键值，且 K1 < K2
   2. 有三个子节点：
      第一个子节点的所有键值小于 K1
      第二个子节点的所有键值介于 K1 和 K2 之间
      第三个子节点的所有键值大于 K2
3. 4节点：
   1. 形式为 [K1, K2, K3]，其中 K1 < K2 < K3
   2. 有四个子节点：
      第一个子节点的所有键值小于 K1
      第二个子节点的所有键值介于 K1 和 K2 之间
      第三个子节点的所有键值介于 K2 和 K3 之间
      第四个子节点的所有键值大于 K3

操作

1. 插入：
   1. 如果插入导致节点超载（变成5节点），则需要分裂节点，并将中间键值提升到父节点中
2. 删除：
   1. 如果删除导致节点不足（少于1个键值），需要从兄弟节点借用键值或合并节点

用途

1. 主要用于实现B树或红黑树

示例

1. 假设有如下2-3-4树：
   1. 根节点 [10, 20, 30]
   2. 这是一个4节点，有三个键值 10、20 和 30
   3. 有四个子节点
2. 第一个子节点 [5, 7]：
   1. 所有键值都小于 10
3. 第二个子节点 [12, 15]：
   1. 所有键值都介于 10 和 20 之间
4. 第三个子节点 [22, 25]：
   1. 所有键值都介于 20 和 30 之间
5. 第四个子节点 [35, 40, 45]：
   1. 所有键值都大于 30

B树（B-树）简介

概述

1. B树是一种自平衡的多路搜索树，其中每个节点可以包含多个键和多个子节点
2. B树的阶（degree）m是一个重要的参数，定义了每个节点的最大子节点数量

特点

1. 平衡性：
   1. 所有叶子节点在同一层次上
2. 多路性：
   1. 每个节点可以有多个子节点
3. 键的数量：
   1. 每个节点包含的键的数量在一定范围内（一般为 ⌈m/2⌉ - 1 到 m - 1 之间）
4. 子节点数量：
   1. 非叶子节点的子节点数量在 ⌈m/2⌉ 到 m 之间
5. 高效性：
   1. 插入、删除和查找操作的时间复杂度为O(log n)

操作

1. 查找
   1. 从根节点开始，根据键值的比较选择相应的子节点，递归进行，直到找到目标键或达到叶子节点
2. 插入
   1. 找到适当的叶子节点进行插入，如果节点满了，则需要分裂节点并调整树的结构
3. 删除
   1. 找到目标键并删除，如果删除导致节点不足，需要合并或重新分配键以保持树的平衡

结构

1. 根节点至少有两个子节点，除非树为空或只有一个节点
2. 每个节点包含的键值按升序排列，节点内的键值分隔其子节点
3. B树通过节点的分裂和合并保持平衡，使得树的高度尽可能低，从而提高操作效率

示例

1. 假设有一个阶为 m=4 的B树：
   1. 根节点包含3个键：[10, 20, 30]
   2. 根节点有4个子节点，分别在这3个键之间分隔开
2. 左子节点:
   1. [1, 5, 7]
   2. 这是根节点[10]左边的子节点。所有值都小于10
3. 第二个子节点：
   1. [12, 15]
   2. 这是根节点[10, 20]之间的子节点
   3. 所有值都介于10和20之间
4. 第三个子节点：
   1. [22, 25]
   2. 这是根节点[20, 30]之间的子节点
   3. 所有值都介于20和30之间
5. 右子节点：
   1. [35, 40, 45]
   2. 这是根节点[30]右边的子节点
   3. 所有值都大于30

理解与总结

1. 在B树中，如果一个节点有n个有序的键值，那么它必须有n+1个子节点
2. 每个子节点的值范围由父节点的键值分割而成
   1. 说白了，就是按父节点的有序键值，分成n+1个范围

应用

1. 数据库索引：
   1. B树广泛用于数据库管理系统中的索引结构，以高效地管理大量数据
2. 文件系统：
   1. 许多文件系统使用B树来组织文件和目录，提供快速的文件访问和管理
3. 存储系统：
   1. B树在存储系统中用于管理数据块和索引，优化存储和检索性能

B+树简介

概述

1. B树的一种变体
2. 所有键值都存储在叶子节点，内部节点只存储键值用于索引

节点类型

1. 内部节点（非叶子节点）：
   1. 只存储键值和子节点指针，用于索引
2. 叶子节点：
   1. 存储所有实际数据，并通过链表连接，以便于顺序访问

特点

1. 保持高度平衡，所有叶子节点在同一层次上
2. 所有数据存储在叶子节点，叶子节点之间通过链表连接，便于范围查询和顺序访问
3. 内部节点用于快速索引，提高查找效率

操作效率

1. 查找、插入和删除操作的时间复杂度为O(log n)
2. 顺序访问和范围查询性能优越

结构

1. 内部节点：
   1. 包含 m-1 个键值和 m 个子节点指针，键值用于索引，子节点指针用于指向子节点
   2. 形式为 [K1, K2, ..., Km-1]，其中 K1 < K2 < ... < Km-1
   3. 有 m 个子节点：
      第一个子节点的所有键值小于 K1
      第 i 个子节点的所有键值介于 Ki-1 和 Ki 之间
      第 m 个子节点的所有键值大于 Km-1
2. 叶子节点：
   1. 包含 l 个键值和数据指针，所有叶子节点按键值的顺序通过链表连接
   2. 形式为 [D1, D2, ..., Dl]，其中 D1 < D2 < ... < Dl
   3. 叶子节点之间通过链表连接，便于顺序访问

操作

1. 查找：
   1. 从根节点开始，根据键值的比较选择相应的子节点，递归进行，直到达到叶子节点
   2. 在叶子节点中找到目标键值对应的数据
2. 插入：
   1. 找到适当的叶子节点进行插入
   2. 如果插入导致叶子节点超载，则需要分裂叶子节点，并将中间键值提升到父节点中
   3. 分裂可能会递归地向上进行，直到根节点
3. 删除：
   1. 找到目标键值并在叶子节点中删除
   2. 如果删除导致叶子节点不足，需要从兄弟节点借用键值或合并节点
   3. 合并或借用可能会递归地向上进行，直到根节点

示例

1. 假设有如下B+树（假设阶为4）：
2. 根节点 [10, 20, 30]：
   1. 这是一个内部节点，有三个键值 10、20 和 30
   2. 有四个子节点
   3. 第一个子节点 [1, 5, 7]：
      所有键值都小于 10
   4. 第二个子节点 [12, 15]：
      所有键值都介于 10 和 20 之间
   5. 第三个子节点 [22, 25]：
      所有键值都介于 20 和 30 之间
   6. 第四个子节点 [35, 40, 45]：
      所有键值都大于 30
3. 叶子节点 [1, 5, 7]、[12, 15]、[22, 25]、[35, 40, 45]：
   1. 存储所有实际数据
   2. 叶子节点按键值顺序通过链表连接，便于顺序访问

B树与B+树比较

1. 数据存储位置
   1. B树：
      数据存储在所有节点（叶子节点和内部节点）
      内部节点不仅用于索引，还可以存储实际的数据
   2. B+树：
      所有实际数据都存储在叶子节点
      内部节点只存储键值用于索引，不存储实际的数据
2. 叶子节点链表
   1. B树：
      叶子节点之间没有链表连接
   2. B+树：
      叶子节点通过链表相互连接，这使得范围查询和顺序访问更加高效
3. 树高
   1. 都保持平衡，确保树的高度尽可能低，查找、插入和删除操作的时间复杂度为O(log n)
   2. 由于B+树的叶子节点存储了所有数据，树的高度可能略大于B树，但一般差别不大
4. 操作：查找
   1. B树：
      从根节点开始，依次比较并下探到子节点，直到找到目标数据
   2. B+树：
      从根节点开始，依次比较并下探到子节点，直到达到叶子节点，在叶子节点找到目标数据
5. 操作：插入
   1. B树：
      找到适当的位置插入数据，如果节点满了，需要分裂节点，并将中间键值提升到父节点
   2. B+树：
      找到适当的叶子节点插入数据，如果叶子节点满了，需要分裂叶子节点，并将中间键值提升到父节点
6. 操作：删除
   1. B树：
      找到目标数据并删除，如果删除导致节点不足，需要从兄弟节点借用或合并节点
   2. B+树：
      找到目标数据并在叶子节点删除，如果删除导致叶子节点不足，需要从兄弟节点借用或合并节点，并可能需要调整父节点的索引

B树与B+树示例

1. B树（假设阶为4）

2. B+树（假设阶为4）

B树与B+树优缺点

1. B树
   1. 优点：可以在较少的节点读取中找到数据，适用于较少范围查询的应用
   2. 缺点：范围查询效率较低，内部节点和叶子节点结构相同，可能导致较高的复杂性
2. B+树
   1. 优点：叶子节点通过链表连接，范围查询和顺序访问性能优越，内部节点更简洁，适用于频繁的范围查询和顺序访问的应用
   2. 缺点：查找数据时需要到达叶子节点，可能会稍微增加查找路径长度