在有些场景中，并不一定要求所有元素有序，而只需知道其中最大或最小的 K 个元素，比如在优先级队列中，只要每次都能获取到队列中最大或最小的的元素即可，于是有人想到了利用树的形式来组织数据，这里称为堆。

排序即将一组对象按照某种逻辑顺序重新排列的过程，通常，整理数据的第一步就是进行排序，因此它是后面很多其它算法和数据结构的基础。在计算机早期年代，据说大约有30%的计算周期都花在了排序操作上，如今这个比例有所降低，并非排序的重要性降低了，而是前辈们不懈的研究，使得如今的排序算法更加高效。

在不同的场景下选择合适的排序算法其实是很重要的，比如下面是使用文中的几种排序策略对同样的1000个随机数进行排序的结果，可以看出来差距还是比较大的

1
2
3
4
5
6
7

SELECT         comp=511566  swap=251579  cost=16355ms
INSERT         comp=252594  wap=251584   cost=16449ms
INSERT_BINARY  comp=14294   move=1011    cost=111ms
INSERT_XIER    comp=13576   swap=8453    cost=578ms
MERGE          comp=9413    swap=0       cost=68ms
QUICK          comp=15391   swap=2225    cost=191ms
QUICK2         comp=13857   swap=13853   cost=905ms

B+树又在B树基础上做了一些改进，主要是在树叶节点上添加了一个链表结构，这样可以很好的解决范围查询问题。具体做法是将所有数据节点放在最下一层树叶节点上， 所有的树叶自左向右为一个链表，而对于任意非树叶节点，不保存数据，只充当索引，这样节点可以保存更多的关键字，从而使树的高度更低，其实如果去掉最下一层树叶节点的话，它就是一颗B树。

前面讨论2-3树时已经提到过，B树就是一颗平衡M叉树，其插入删除操作都可以与2-3树作类似处理，这里不再赘述。

这里简单讨论下其实际意义：之前的各种二叉树都有一个共同假设，即数据全部存储在内存中，因此讨论时只需关心在找到目标之前需要比较多少次数。但是当数据量大到不适合存放在内存时，就需要借助磁盘来保存了，而磁盘访问相对于内存操作要慢得多得多，因此，这时对于性能的考虑更多的是关心如何减少磁盘访问操作，

思路是将（有序）数据分为 N 批，并用 M 叉平衡树来组织，即访问磁盘时每批返回至多 M-1 项数据，那么在访问某项数据时，至多需要访问磁盘的次数就为 $\log_{M} {N}$

前面已经讨论过平衡二叉树Avl，其目的就是通过旋转尽量使树保持平衡，以降低树的高度或查找的时间复杂度。当然，最好的情形是能转化成一颗满二叉树，使树的高度与节点数完全满足 $H = \log_{2} {(n+1)}$，但实际在大部分情形下，无论其如何旋转调整都无法做到，毕竟对于每个节点，其最多只能有一个元素，两个子节点。

既然如此，那就打破规则，允许一个节点最多拥有两个元素，三个子树，这样就不再存在一个节点只有单个子树的情况，取而代之的是节点是二叉还是三叉（如果一个节点只有单个子树，就使其成为三叉节点），这也就是 2-3 树的字面意思：即同时拥有二叉节点和三叉节点的树， 这样在插入删除时就可以自下而上采取分裂合并的方式保证所有叶子节点都在同一层，并使树的节点达到一个绝对平衡的状态。

2-3 树本身并没有什么实际使用场景，但其在思路上打破了二叉树的约束，在树形数据结构中起着一个关键的连接作用，它解决了Avl树无法绝对平衡的问题，并且顺着这个思路可以进一步联想到红黑树以及后面要讲的B树。

定义：红黑树是Avl树的一个变种，它也是在二叉树的基础上添加平衡条件，只是它对平衡条件的定义不像AVl树那样直接，而是转化成对节点颜色规则的描述：

1. 对于任意节点，要么是红色，要么是黑色；
2. 根节点是黑色的；
3. 如果一个节点是红色的，那么它的子节点必须是黑色的（即不能有两个连续的红色节点）；
4. 任意节点到其下面各个空结点（后面称为nil节点，并约定其颜色为黑色）的路径上都包含相同数目的黑色节点（称为黑高）；

通过对任何一条从根到空节点的路径上各个结点的颜色进行约束，红黑树可以确保没有一条路径会比其他路径长出2倍，因而红黑树是近似平衡的。