平衡二叉树
- 左右子树高度相差不超过1
- 适用于查询多，修改少
红黑树
- 没有一条路径比其他路径长出两倍：一条全黑，另一条半黑半红
- 从一个节点到该节点的子孙节点的所有路径包含相同数目的黑节点
- 一个红色节点的子节点是黑色
- 根节点黑色，叶子节点也是黑色
- 适用于修改多
B树
- 根节点至少两个子节点，至多M个子节点
- 其他节点至少M/2个子节点，至多M个子节点
- 每个节点至少M/2-1个Key，至多M-1个Key，并且升序排列
- 所有叶子节点位于同一层
- 适用于查询多
B+树
- 非叶子节点Key的个数与子节点的个数相等。所有Key都出现在叶子节点。非叶子节点仅具有索引功能，跟记录有关的信息存放在叶子节点
- 叶子节点增加链指针，所有叶子节点构成一个有序链表
- 适用于索引与数据的分离
B*树
- 非根非叶子节点增加链指针
