第三章·树·导读

在前面的第二章，我们介绍了数组，数组因为是下标定位，所以查找极快，而hashtable(key,value)借鉴数组O(1)定位的特点，key映射value，所以查找也相当快，只是需要耗费一定的空间存储key和value，所以是典型的空间换时间的思想。

其中，理解红黑树，先理解二叉查找树和2-3树，为何？首先，二叉查找树中的结点是2-结点（一个键两条链），引入3-结点（两个键三条链），即成2-3树；再者，将2-3树中3-结点分解，即成红黑树，故结合二叉查找树易查找和2-3树易插入的特点，便成了红黑二叉查找树，简称红黑树。

进一步，理解了2-3树，也就理解了B树、B+树、B*树，因为2-3树就是一棵3阶的B树，而一颗3阶的B树各个结点关键字数满足1-2，故结点关键字数多于2达到饱和时分裂，结点关键字数少于1时则从兄弟结点“借”关键字补充。

但为何有了红黑树，还要出现B树呢？原因是当计算机要处理的数据量一大，便无法一次性装入内存处理，于是，计算机会把大部分备用的数据存在磁盘中，有需要的时候，就从磁盘调取到在内存中处理，如果处理时修改了数据，则再次写会磁盘，如此导致了不断的磁盘IO读写，而树的高度越到，查找文件所需要的磁盘IO读写次数越多。

因此，为了进一步降低树的高度，具有多个孩子的B树的应运而生，正因为B树每一个结点可以有几个到几千个孩子，在结点数目一定的情况下，树的高度会大大降低，此外，B树的根结点和部分顶层数据在内存中，大部分下层数据在磁盘上。