B 树

定义

B 树是一种多路平衡查找树，每个节点可以有多个键和多个子节点。它专为减少磁盘 IO 而设计，常用于数据库和文件系统的索引。

原理

一棵 m 阶 B 树的每个节点最多有 m 个子节点、m-1 个键，键在节点内有序排列，子节点的键落在相邻键之间。所有叶子位于同一层，保证全局平衡。由于节点扇出大、树高很矮，一次磁盘读取可加载一个节点中的多个键，从而大幅减少访问磁盘的次数。插入或删除导致节点过满或过空时，通过分裂与合并维持平衡。

复杂度

• 查找：O(log n)
• 插入：O(log n)
• 删除：O(log n)
• 空间复杂度：O(n)

应用场景

• 数据库索引
• 文件系统（如 NTFS、HFS+）
• 大规模有序数据的外存存储