B 树和 B+ 树

B 树又称多路平衡查找树，是一种适合外存（磁盘）存取的多叉平衡树。

B 树的概念

一棵 $m$ 阶 B 树满足：

• 每个结点至多有 $m$ 棵子树
• 根结点（若非叶子）至少有两棵子树
• 除根结点外的所有非终端结点至少有 $\lceil m/2\rceil$ 棵子树
• 终端结点（叶子结点）位于同一层

B 树中关键字按顺序排列，结点内关键字个数比子树个数少 1。

B 树的基本操作

• B 树的高度（决定磁盘存取次数）
• B 树的查找
• B 树的插入（结点分裂）
• B 树的删除（结点合并）