二叉查找树、平衡二叉查找树、红黑树查找的时间复杂度O(log2N)与树的深度有关，降低树的深度会提高查询效率

二叉查找树(Binary Search Tree)

左子树键值总是小于根的键值，右子树键值总是大于根的键值。因此中序遍历可以得到键值的排序输出
缺点：存储连续递增的值，会退变为列表

平衡二叉查找树(Balanced Binary Search Tree)

为了提高二叉树的搜索的效率,减少树的平均搜索长度，提出了AVL树，它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1（也就是高度的平衡），且它的左子树和右子树都是一颗平衡二叉树。为了维持高度的平衡，则频繁的插入和删除，会引起频繁的reblance（旋转以维持平衡），导致效率可能会下降

红黑树(Red-Black Tree)

红黑树，一种二叉查找树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树牺牲了绝对平衡，换取了少旋转。红黑树确保没有一条路径会比其他路径长出俩倍，且对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点，因而是接近平衡的。
红黑树不是高度平衡的，算是一种折中，插入最多两次旋转，删除最多三次旋转。很好的解决了平衡二叉树旋转次数出现很多的可能。
红黑树具有5个性质：

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

正是红黑树的这5条性质，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。

B-tree

B+tree