B树（B-Tree）
数据结构
- 节点结构：每个节点包含多个键值和子节点指针。
- 阶（Degree）：B树的阶定义了每个节点的最小和最大键值数。对于阶为 ( m ) 的B树：
- 每个节点最多有 ( m-1 ) 个键值和 ( m ) 个子节点。
- 每个节点（除了根节点）至少有 ( \lceil m/2 \rceil - 1 ) 个键值和 ( \lceil m/2 \rceil ) 个子节点。
- 根节点至少有一个键值。
- 平衡性：所有叶子节点在同一层，保证了树的平衡性。
操作
- 查找：从根节点开始，逐层向下查找，时间复杂度为 ( O(\log n) )。
- 插入：找到合适的叶子节点插入，如果节点满了则进行分裂，时间复杂度为 ( O(\log n) )。
- 删除：从叶子节点删除，如果节点的键值数小于最小值则进行合并或借用操作，时间复杂度为 ( O(\log n) )。
B+树（B+Tree）
数据结构
- 节点结构：和B树类似，但有显著区别：
- 内部节点只包含索引，不存储实际数据。
- 叶子节点包含所有数据，并通过链表相连。
- 阶（Degree）：B+树的阶定义了每个节点的最小和最大索引数。对于阶为 ( m ) 的B+树：
- 每个内部节点最多有 ( m ) 个子节点。
- 每个节点（除了根节点）至少有 ( \lceil m/2 \rceil ) 个索引和子节点。
- 所有叶子节点在同一层，形成一个链表。
操作
- 查找：从根节点开始，逐层向下查找，最后在叶子节点找到数据，时间复杂度为 ( O(\log n) )。
- 插入：找到合适的叶子节点插入，如果叶子节点满了则进行分裂，时间复杂度为 ( O(\log n) )。
- 删除：从叶子节点删除，如果节点的索引数小于最小值则进行合并或借用操作，时间复杂度为 ( O(\log n) )。
红黑树（Red-Black Tree）
数据结构
- 节点结构：每个节点包含键值、颜色（红色或黑色）、左右子节点指针和父节点指针。
- 平衡规则：
- 每个节点是红色或黑色。
- 根节点是黑色。
- 红色节点的子节点必须是黑色（即红色节点不能有红色子节点）。
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
操作
- 查找：从根节点开始，逐层向下查找，时间复杂度为 ( O(\log n) )。
- 插入：按照二叉搜索树插入后，通过旋转和重新着色保持平衡，时间复杂度为 ( O(\log n) )。
- 删除：按照二叉搜索树删除后，通过旋转和重新着色保持平衡，时间复杂度为 ( O(\log n) )。
对比三者的区别
-
节点结构：
- B树：每个节点包含多个键值和子节点指针。
- B+树：内部节点只包含索引，叶子节点包含所有数据并形成链表。
- 红黑树：每个节点包含一个键值和颜色属性，左右子节点指针和父节点指针。
-
平衡性：
- B树和B+树：通过节点分裂和合并保持平衡。
- 红黑树：通过旋转和重新着色保持平衡。
-
查询效率：
- B树和B+树：适用于大数据量的磁盘存储和范围查询，时间复杂度为 ( O(\log n) )。
- 红黑树：适用于内存中的快速查找、插入和删除操作，时间复杂度为 ( O(\log n) )。
-
存储位置：
- B树：数据分布在所有节点。
- B+树：数据只存储在叶子节点，内部节点只存储索引。
- 红黑树：数据存储在每个节点。
-
适用场景：
- B树和B+树：适用于数据库和文件系统等需要大量磁盘I/O操作的场景。
- 红黑树：适用于内存中频繁插入、删除、查找操作的场景，如实现关联容器（如C++ STL中的
map、set）和Java中的TreeMap、TreeSet。
总结
B树和B+树适用于磁盘存储，因为它们减少了磁盘I/O次数。红黑树适用于内存中的动态数据结构操作。B+树特别适合范围查询和顺序访问，而红黑树则在保持平衡的同时提供了高效的插入和删除操作。
标签：黑树,Java,log,复杂度,叶子,键值,红黑树,树和红,节点 From： https://blog.csdn.net/qq_42631788/article/details/139727644