B-、B、B+、B*树

B树（即二叉搜索树）：

① 节点本身存储一个关键字
② 非叶子节点至多两个子
③ 左子比父小，右子比父大

特性：
当左右子树节点数差不多时（平衡），
搜索性能逼近二分查找。比起连续内
存空间来，优点是插入和删除节点时
不需要移动大段的内存数据，通常为
常数开销。

缺点：
经过多次插入和删除后，可能导致不同的结构，导致搜索性能降低。

B-树（多路搜索树，不是二叉的）：
（M=3，M应定义为>2）

① 非叶子节点至多M个子
② 根节点应有[2,M]个子
③ 根节点以外的非叶子节点应有[M/2,M]个子
④ 各节点存放至少M/2-1（取上整）和之多M-个关键字（至少2个关键字）
⑤ 非叶子节点的关键字个数=指向子的指针个数-1
⑥ 所有叶子节点位于同一层

特性：
搜索性能等价于在关键字全集内做一次二分查找，有自动层次控制功能。由于根节点以外的非叶子节点至少含M/2个子，保证了最低搜索性能为（N：关键字总数）
所以B-树性能总是等价于二分查找，即没有B树的平衡问题。

B+树（B-树的变体）：

① 定义基本与B-树相同，除了：
② 非叶子节点的子树指针与关键字个数相同
③ 所有叶子节点增加了一个链指针
④ 所有关键字都在叶子节点出现

特性：
所有关键在都出现在叶子节点的链表中，且链表中的关键字都是有序的；非叶子节点相当于是叶子节点的索引，而叶子节点相当于是存储数据的数据层；更适合文件索引系统。

B*树（B+树的变体）：
在B+树的非根和非叶子节点增加指向兄弟的指针。

B*树定义非叶子节点关键字个数至少为（2/3）M，即块的最低使用率为2/3（B+树为1/2）；B树分配新节点的概率比B+树低，空间使用率更高。