可扩散列

如果需要处理的数据量太大以至于装不进去主存，我们就要考虑检索数据所需的磁盘存取次数了。

我们假设在任意时刻都有 N 个记录要存储，N 的值随时间而变化。此外，最多可把 M 个记录放入一个磁盘区块。

如果使用开放定址散列法或分离链接散列法，那么主要的问题在于，在一次 Find 操作期间，冲突可能引起多个区块被考察，甚至对于理想分布的散列表也在所难免。不仅如此，当表变得过满的时候，必须执行代价巨大的再散列这一步，它需要 次磁盘访问。

一种聪明的选择叫作可扩散列（extendible hashing），它允许用两次磁盘访问执行一次 Find。插入操作也需要很好的磁盘访问。

我们都知道，B 树具有深度 。随着 M 的增加， B 树的深度降低。理论上我们可以选择使得 B 树的深度为 1 的 M。此时，在第一次以后的任何 Find 都将花费一次磁盘访问，因为据推测根节点可能存在主存中。这种方法的问题在于分支系数（branching fator）太高，以至于为了确定数据在哪片树叶上要进行大量的处理工作。如果运行这一步的时间可以缩减，那么我们就将有一个实际的方案。这正是可扩散列使用的策略：

可扩散列使用的策略

上图是一个可扩散列的扩展实例。具体的过程为，插入 100100 时，它将进入第三片树叶，但是第三片树叶已经满了，没有空间存放它。因此我们将这片树叶分裂成两片树叶，它们由前三位确定（左图的树叶由前两位确定）。这时，需要将目录的大小增加到 3。注意，此时，所有未被分裂的树叶现在各由两个相邻目录项所指。因此，虽然重写整个目录，但是其他树叶都没有被实际访问。

如果现在插入关键字 000000，那么第一片树叶就要被分裂，生成两片树叶，故此时，目录中所做的唯一变化是 000 和 001 指针的更新。如下图：

插入关键字 000000

这个非常简单的方法提供了对大型数据库 Insert 操作和 Find 操作的快速存取时间。这里，还有一些重要的细节尚未考虑：

• 首先，有可能当一片树叶的元素多余 D+1（D代表根所使用的位数） 个前导位相同时需要多个目录分裂。例如，从前面的例子开始，D =2，如果插入 111010、111011，并在最后插入 111100，那么目录大小必须增加到 4 以区分五个关键字。这是一个容易考虑到的细节，但是千万不要忘记它。
• 其次，存在重复关键字（duplicate key）的可能性；如存在多于 M 个重复关键字，则该算法根本无效。此时，需要做出某些其他的安排。

这些可能性指出，这些位完全随机是相当重要的，这可以通过把关键字散列到合理长的整数（由此得名）来完成。

树叶的期望个数为 。因此，平均树叶满的程度为 。这和 B 树是一样的，其实这完全不奇怪，因为对于两种数据结构，当添加第 项时，一些新的节点就建立起来了。

更惊奇的结果是，目录的期望大小（换句话说即 ）为 。如果 M 很小，那么目录可能过大。这种情况下，我们可以让树叶包含指向记录的指针而不是实际的记录，这样可以增加 M 的值。为了维持更小的目录，我们为每个 Find 操作添加第二个磁盘访问。如果目录太大装不进主存，那么第二个磁盘怎么说也还是需要的。