二叉查找树、平衡二叉树、B-树、B+树概念

二叉查找树(又：二叉排序树)

一颗m阶二叉查找树应具备如下特征：

1.若左子树不为空，那么左子树的关键字应比根节点小
2.若右子树不为空，那么右子树的关键字应比根节点大
3.左子树和右子树都为二叉查找树


平衡二叉树(又：AVL 树)

1.左子树和右子树的深度查的绝对值 <= 1


B-树

B-树的关键是：指针+关键字+地址

一颗 m 阶的 B- 树具备如下特征：

1.所有节点最多 m 颗子树
2.若根节点不为空，则至少2颗子树
3.除根节点之外的所有非终端节点最少 (m/2)向上取整颗子树.


B+树

一颗 m 阶 B+ 树和一颗 m 阶 B- 树的差异：

1.只有指针和关键字了
2.所有的叶子节点包含全部的关键信息，叶子节点按照关键字的大小顺序排列.
3.所有非叶子节点可以看成是索引的一部分，节点中仅包含叶子节点中最小(或最大)的关键字.
4.n 颗子树就有 n 个关键字.