3. ISAM¶

如何处理需要频繁更新的大型数据库？ 线性索引的主要问题在于它是一个单独的大数组，难以适应更新， 因为一次更新可能需要改变索引中每个键的位置。 倒排表缓解了这一问题，但它只适用于次键值远少于记录数的 次键索引。 如果能把线性索引切分成若干块，使每次更新只影响索引的一部分， 那么它作为主键索引的表现会相当好。 本章余下部分将贯穿这一思想，最终引出当今使用最广泛的索引方法 ——\(\mathrm{B}^+\) 树。 但首先，我们来研究 ISAM，它是解决"大型数据库需要频繁更新" 问题的一次早期尝试。 它的缺陷恰好有助于说明 \(\mathrm{B}^+\) 树为什么如此 有效。

在有效的树索引方案发明之前，人们使用过多种基于磁盘的索引 方法。 它们都相当笨重，主要原因是当时还不知道处理更新的好办法。 通常，更新会导致索引性能退化。 ISAM 就是这类索引的一个例子，在 B 树被采用之前曾被 IBM 广泛使用。

ISAM 基于 线性索引 的一种修改形式，如图 15.3.1 所示。记录按主键排序存储。磁盘文件被划分为磁盘上的若干 柱面 。每个柱面按排序顺序存放列表中的一段。初始时，每个柱面都未装满，多余的空间被预留作 柱面溢出 。内存中有一张表，列出文件每个柱面中存放的最低键值。每个柱面内还有一张表，列出该柱面中每个块的最低键值，称为 柱面索引 。插入新记录时，它们被放入正确柱面的溢出区（实际上，每个柱面充当一个桶）。如果某个柱面的溢出区完全装满，则使用全系统溢出区。查找时，先根据主存中维护的全系统表确定适当的柱面，再从磁盘调入该柱面的块表并查阅以确定正确的块。如果在该块中找到记录，则查找结束；否则查找该柱面的溢出区。若该区已满且未找到记录，则查找全系统溢出区。

数据库初始构建之后，只要不插入或删除新记录，访问就是高效的， 因为它只需两次磁盘读取。 第一次磁盘读取取出目标柱面的块表。 第二次磁盘读取取出（在良好条件下）包含目标记录的磁盘块。 多次插入之后，溢出链表会变得过长，随着柱面溢出区被填满， 查找时间显著增加。 在极端条件下，许多查找最终都要落到系统溢出区。 这个问题的"解决方案"是周期性地重组整个数据库。 也就是在柱面之间重新平衡记录、对每个柱面内的记录排序， 并更新系统索引表和柱面内的块表。 这种重组在 20 世纪 60 年代的数据库系统中很典型， 通常每天晚上或每周进行一次。