结合此前我们一直在讨论的B+树、平衡树这类自平衡多路搜索树的相关背景,2-3树和2-3-4树都是B树的最简特殊形态,是理解自平衡树原理的经典入门结构:
一、2-3树
2-3树是最简单的B树结构,属于自平衡多路搜索树:
节点规则:仅支持两种节点类型,2节点含1个键、2个子节点,3节点含2个键、3个子节点,所有叶子节点处于同一层级。
核心特性:通过叶子节点分裂、中间键向上传递完成自底向上的平衡调整,仅根节点分裂时才会增加树高,查找、插入、删除的时间复杂度稳定为O(log n)。
典型应用:常作为算法教学的入门模型,也可用于小规模文件系统的目录索引管理。
二、2-3-4树
2-3-4树是阶为4的B树,是2-3树的扩展形态:
节点规则:支持三种节点类型,2节点含1个键、2个子节点,3节点含2个键、3个子节点,4节点含3个键、4个子节点,所有叶子节点深度完全一致。
核心特性:采用自顶向下的分裂策略,向下查找插入位置的途中遇到满的4节点就提前分裂,操作逻辑更简单,且它和红黑树是完全等价的结构,可直接完成互相转换。
典型应用:是理解红黑树原理的直观入门模型,也可用于部分内存数据库的小规模索引实现。
三、二者核心差异对比
| 对比维度 | 2-3树 | 2-3-4树 |
|---|---|---|
| 支持节点类型 | 仅2节点、3节点 | 2节点、3节点、4节点 |
| 插入分裂时机 | 自底向上,插入后回溯分裂 | 自顶向下,插入途中提前分裂 |
| 等价关系 | 可对应简化版红黑树 | 和标准红黑树一一对应 |
| 实现复杂度 | 略高,回溯逻辑繁琐 | 更低,分裂逻辑更直观 |