Question

台湾出版人何飞鹏在《自慢》书中曾经有这样的文字：“要观察一个公司是否严谨，看他们如何开会就知道了。如果开会时每一个人都只是带一张嘴，即兴发言，这肯定是一家不严谨的公司，因为肯定每一个人都只是用直觉与反射神经在互相应对，不可能有深度的思考与规划……，语言是沟通的工具，文字是记录存证的工具，而文字化的过程，又可以让思考彻底沉淀，善于使用文字的人，通常是深沉而严谨的。”显然，这是一个很好理解的观点，但许多人都难以做到它。

图8-8-1

要是我们把开会比作内存中的数据处理的话，那么写下来和时常阅读它就是内存数据对外存磁盘上的存取操作了。

内存一般都是由硅制的存储芯片组成，这种技术的每一个存储单位代价都要比磁存储技术昂贵两个数量级，因此基于磁盘技术的外存，容量比内存的容量至少大两个数量级。这也就是目前PC通常内存几个G而已、而硬盘却可以成百上千G容量的原因。

我们前面讨论过的数据结构，处理数据都是在内存中，因此考虑的都是内存中的运算时间复杂度。

但如若我们要操作的数据集非常大，大到内存已经没办法处理了怎么办呢？如数据库中的上千万条记录的数据表、硬盘中的上万个文件等。在这种情况下，对数据的处理需要不断从硬盘等存储设备中调入或调出内存页面。

一旦涉及到这样的外部存储设备，关于时间复杂度的计算就会发生变化，访问该集合元素的时间已经不仅仅是寻找该元素所需比较次数的函数，我们必须考虑对硬盘等外部存储设备的访问时间以及将会对该设备做出多少次单独访问。

试想一下，为了要在一个拥有几十万个文件的磁盘中查找一个文本文件，你设计的算法需要读取磁盘上万次还是读取几十次，这是有本质差异的。此时，为了降低对外存设备的访问次数，我们就需要新的数据结构来处理这样的问题。

我们之前谈的树，都是一个结点可以有多个孩子，但是它自身只存储一个元素。二叉树限制更多，结点最多只能有两个孩子。

一个结点只能存储一个元素，在元素非常多的时候，就使得要么树的度非常大（结点拥有子树的个数的最大值），要么树的高度非常大，甚至两者都必须足够大才行。这就使得内存存取外存次数非常多，这显然成了时间效率上的瓶颈，这迫使我们要打破每一个结点只存储一个元素的限制，为此引入了多路查找树的概念。

多路查找树（muitl-way search tree），其每一个结点的孩子数可以多于两个，且每一个结点处可以存储多个元素。由于它是查找树，所有元素之间存在某种特定的排序关系。

在这里，每一个结点可以存储多少个元素，以及它的孩子数的多少是非常关键的。为此，我们讲解它的4种特殊形式：2-3树、2-3-4树、B树和B+树。