B树教程
介绍
B树是一种自平衡的多路搜索树,它是二叉搜索树的扩展,专为磁盘或其他外部存储设备设计。B树的每个节点拥有更多的子节点,这使树的高度更低,减少访问磁盘的次数。
B树中的几个关键概念:
- 阶(Order):定义了一个B树节点最多可以有多少个子节点。具有阶为m的B树也称为m阶B树。
- 内部节点(Internal Node):除根节点和叶节点外的所有节点。
- 叶节点(Leaf Node):没有子节点的节点。
- 键(Key):存储在节点中的值,用于指导搜索过程。
- 子节点(Child):节点的直接后代。
一个阶为m的B树满足以下性质:
- 每个节点最多有m个子节点
- 除了根节点和叶节点,每个节点至少有⌈m/2⌉个子节点
- 如果根节点不是叶节点,则至少有两个子节点
- 所有叶节点都在同一层
- 具有k个子节点的非叶节点包含k-1个键
...