本章导读

想要更好地理解红黑树,可以先理解二叉查找树和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读写次数越多,所以为了减少磁盘的IO读写,要想办法进一步降低树的高度。
因此,具有多个孩子的B树便应运而生,因为B树每一个结点可以有几个到几千个孩子,使得在结点数目一定的情况下,树的高度会大大降低,从而有效减少磁盘IO读写消耗。

此外,无论是B树,还是B+树、B树,由于根或者树的上面几层被反复查询,所以树上层几块的数据可以存在内存中。换言之,B树、B+树、B树的根结点和部分顶层数据存在内存中,大部分下层数据存在磁盘上。