B 树
binary search tree，称为二叉搜索树、二叉排序树或者二叉查找树，简称BST
B 树，即二叉搜索树
- 所有非叶子结点都有左右子节点
- 所有结点都会存储一个关键字
- 非叶子节点的左子节点小于其关键字，右子节点大于其关键字
AVL 树
AVL 树是自平衡二叉查找树，在AVL 树中，任何节点的两个子树的高度最大差别为1，查找、插入和删除的平均和最坏情况都是O(log n)
B+ 树
特点
- 所有关键字都出现在叶子节点中，叶子节点和叶子节点之间是以链表的方式来存储的
- 叶子节点是有序的
红黑树
红黑树是满足以下性质的二叉搜索树
- 每个结点是红色的或者黑色的
- 根结点是黑色的
- 如果结点是红色的，其左右叶子结点都是黑色的
保证了从根节点到叶子节点的最长路径的长度不会超过任何其他路径的两倍
- 每个叶子结点都是黑色的
- 对于每个结点，从该结点到其所有子孙叶结点的路径中所包含的黑色结点数量必须相同。
红黑树和B 树的应用场景
红黑树多用在内部排序，即全放在内存中的，STL的map和set的内部实现就是红黑树。
B+树多用于外存上时，B+也被成为一个磁盘友好的数据结构。
红黑树并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能
为什么用二叉树 而不用散列表
- 第一，散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在O(n)的时间复杂度
内，输出有序的数据序列。 - 第二，散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳
定，时间复杂度稳定在O(logn)。 - 第三，笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比logn小，所以实际的查找速度可能不一定
比O(logn)快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。 - 第四，散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一
个问题，而且这个问题的解决方案比较成熟、固定。