二叉查找树、AVL树、红黑树、B树和B+树

二叉查找树（BST）

二叉查找树也称为二叉查找树，具有以下性质：

• 若左子树不为空，则左子树的值均小于根节点的值。
• 若右子树不为空，则右子树的值均大于根节点的值。
• 左、右子树也分别是二叉查找树。

AVL树

平衡二叉树（AVL Tree）在符合二叉查找树的条件下，还满足任何节点的两个子树的高度差最大为1。

红黑树

红黑树是一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，它是一种弱平衡二叉树（由于是弱平衡，可以推出，相同的情况下，AVL树的高度低于红黑树），相对于要求严格的AVL树来说，它的旋转次数变少，所以对于搜索，插入，删除操作多的情况下，就使用红黑树。

具有以下性质：

• 每个节点非红即黑。
• 根节点是黑的。
• 每个叶节点（叶节点即树尾端null指针或null节点）都是黑的。
• 如果一个节点是红的，那么它的两个儿子都是黑的。
• 对于任意节点而言，其到叶子点树NIL指针的每天路径都包含相同的黑节点。
  

B/B+树

B/B+树是为磁盘或其它存储设备而设计的一种平衡多路查找树（相对于二叉，B树每个内节点有多个分支），与红黑树相比，在相同的节点的情况下，一棵B/B+树的高度远远小于红黑树的高度。B/B+树上操作的时间通常由存储磁盘的时间和CPU计算时间这两个部分构成，而CPU的速度非常快，所以B树的操作效率取决于访问磁盘的次数，关键字总数相同的情况下B树的高度越小，磁盘I/O所花的时间越少。

B树的性质：

定义任意非叶子结点最多只有M个儿子，且M>2；
根结点的儿子数为[2,M]；
除根结点以外的非叶子节点的儿子数为[M/2,M]；
每个节点存放至少M/2-1（取上整）和至多M-1个关键字；（至少两个关键字）
非叶子结点的关键字个数=指向儿子的指针个数-1；
非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
所有叶子结点位于同一层；

B+树是应文件系统所需而产生的一种B树的变形树（文件的目录一级一级索引，只有最底层的叶子节点（文件）保存数据），非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中。所有的非叶子节点都可以看成索引部分。

B+树的性质：

非叶子节点的子树指针与关键字个数相同；
非叶子节点的子树指针p[i]，指向关键字值属于[k[i],k[i+1]]。(B树是开区间，也就是说B树不允许关键字重复，B+树允许重复)
为所有叶子节点增加一个链指针。
所有关键字都在叶子节点出现（稠密索引）。（且链表中的恰是有序的）；
非叶子节点相当于叶子节点的索引（稀疏索引），叶子节点相当于是存储（关键字）数据的数据层。