多叉树

多叉树是一种树形数据结构，其中每个节点可以有多个子节点（通常多于两个），与二叉树（每个节点最多有两个子节点）形成对比。

常见多叉树类型：

1. B树(B-Tree):自平衡的多路搜索树，常用于数据库和文件系统
2. B+树(B+ Tree):B树的变种，所有数据都存储在叶节点，范围查询效率更高
3. Trie树(前缀树):用于字符串搜索，每个节点代表一个字符
4. 2-3树:每个节点有2个或3个子节点，自平衡搜索树

B树

B树具有以下特性：
阶数(m)：B树的阶数指树中节点最大的子节点数目
例如：m阶B树表示每个节点最多有m个子节点

节点结构：
每个节点最多包含m-1个键(key)
根节点至少包含1个键
非根节点至少包含⌈m/2⌉-1个键

子节点规则：
每个节点最多有m个子节点
非叶子节点如果有k个键，则有k+1个子节点

平衡性：
所有叶子节点位于同一层级
保持树的平衡，确保操作效率

B树的构建

1. 找到合适的叶子节点插入
2. 如果叶子节点未满(键数 < m-1)，直接插入
3. 如果叶子节点已满：
   将节点分裂为两个
   中间键提升到父节点
   递归检查父节点是否需要分裂

构建一个五阶B树例题1：

构建一个五阶B树例题2：

B树的优势

减少磁盘I/O：每个节点存储更多数据，减少树的高度
适合外存存储：节点大小通常设计为磁盘块大小（页）
稳定性能：所有操作时间复杂度为O(log n)
自动平衡：插入删除后自动调整保持平衡

B树是理解现代存储系统的关键数据结构

B+树

B+树是一种平衡树数据结构，是B树的变体，广泛用于数据库和文件系统中作为索引结构。
B+树的非叶子节点仅具有索引作用，非叶子节点仅存储key值，不存value值
B+树的所有叶子节点构成一个有序链表

M阶B+树：
每个节点最多M个子节点
每个节点最多存 M-1个 key值
key 以升序排列

构建

1. 找到合适的叶子节点插入数据
2. 如果叶子节点已满，则分裂节点：
   将中间键提升到父节点
   分裂后的两个节点作为父节点的子节点
3. 递归向上处理可能的分裂，直到根节点

构建五阶B+树例题：

优缺点

优点：
高效的查找、插入和删除操作(O(log n))
适合磁盘存储(减少I/O操作)
优秀的大数据量处理能力
高效的范围查询

缺点：
实现复杂
维护平衡需要额外开销
对小数据集可能不如哈希表高效

与B树的比较

1. 数据存储：
   B树：数据可以存储在所有节点
   B+树：数据只存储在叶子节点
2. 查询效率：
   B树：可能在内部节点找到数据，查询时间不稳定
   B+树：必须到达叶子节点，查询时间更稳定
3. 范围查询：
   B树：需要中序遍历
   B+树：通过叶子节点链表高效支持
4. 空间利用率：
   B+树内部节点不存储数据，可以容纳更多键值，树高更低