跳到主要内容

第 12 章 - 索引 (Indexing)

查询一张表时，用户常常只关心其中一部分记录，例如某个字段具有指定值的记录。索引 (index) 是一种文件，它让数据库引擎能够快速定位这些记录，而不必搜索整张表。本章讨论三种常见的索引实现方式：静态哈希 (static hashing)、可扩展哈希 (extendable hashing) 和 B 树 (B-trees)。随后，本章会开发能够利用索引的关系代数操作。

12.1 索引的价值 (The Value of Indexing)​

到目前为止，本书一直假设表中的记录没有特定组织。然而，合适的表组织方式可以显著提升某些查询的效率。为了说明这里的问题，可以考虑纸质电话簿的白页。

电话簿本质上是一张大表，其中每条记录列出一个订户的姓名、地址和电话号码。这张表先按订户姓氏排序，再按名字排序。假设要检索某个人的电话号码，最好的策略就是利用记录已经按姓名排序这一事实。例如，可以通过二分搜索定位电话号码，最多只需检查 log2 N 条记录，其中 N 是记录总数。这非常快。比如，如果 N = 1,000,000，那么 log2 N < 20，也就是说，在一百万人的电话簿中找一个人，最多检查不到 20 条记录。

电话簿非常适合按订户姓名检索记录，却不适合其他类型的检索，例如查找拥有某个电话号码的人，或者查找住在某个地址的人。要从电话簿中得到这些信息，唯一办法是检查其中每一条记录。这种搜索可能相当慢。

如果希望能根据电话号码高效查找订户，就需要一本按电话号码排序的电话簿，也就是所谓的“反向电话簿”。当然，这本电话簿只有在已知电话号码时才有用。如果手上有一本反向电话簿，却想知道某个特定订户的电话号码，那么又必须检查这本书中的每一条记录。

这个讨论说明了一个显而易见却非常关键的事实：一张表在同一时间只能按一种方式组织。如果希望在给定电话号码或给定订户姓名时都能快速检索，就需要两份独立的电话簿副本，每份采用不同的组织方式。如果还希望在给定地址时快速检索电话号码，那么还需要第三份按地址组织的电话簿。

这个原则同样适用于数据库表。如果希望高效查找表中某个字段具有特定值的记录，就需要一份按该字段组织的表版本。数据库引擎通过支持索引来满足这一需求。一张表可以有一个或多个索引，每个索引定义在不同字段上。每个索引都像是这张表按其字段组织的一个版本。例如，STUDENT 表的 MajorId 字段上的索引，会让查找具有给定专业的 STUDENT 记录变得容易。

更具体地说，索引是一个由索引记录 (index records) 组成的文件。索引文件为关联表中的每条记录保存一条索引记录。每条索引记录有两个值：关联记录的记录标识符，以及该记录指定字段的值。SimpleDB 将这两个字段称为索引记录的 datarid 和 dataval。图 12.1 描绘了 STUDENT 表及其两个索引：一个定义在 SId 字段上，另一个定义在 MajorId 字段上。图中每个方框表示一条记录。索引记录的 dataval 出现在方框内，datarid 则以箭头形式指向关联的 STUDENT 记录。

图 12.1 索引 SID_IDX 和 MAJOR_IDX

数据库引擎会按 dataval 组织索引文件中的记录。12.3 到 12.5 节会考察几种更复杂的记录组织方式。现在，图 12.1 暂时假设索引记录按 dataval 排序。这个有序组织可以按如下方式使用。

假设要查找 SId 值为 6 的 STUDENT 记录。首先在 SID_IDX 上进行二分搜索，找到 dataval 为 6 的索引记录；然后沿着它的 datarid 定位到关联的 STUDENT 记录，也就是 Kim 的记录。

再假设要查找 MajorId 值为 20 的 STUDENT 记录。首先在 MAJOR_IDX 上进行二分搜索，找到第一条 dataval 为 20 的索引记录。注意，由于索引已排序，其他三条 dataval 同为 20 的索引记录会在文件中紧跟其后连续出现。遍历这四条索引记录；对每条索引记录，沿着它的 datarid 定位到关联的 STUDENT 记录。

这种索引用法的效率如何？如果没有索引，那么对于上述任一查询，最好的办法都是顺序搜索 STUDENT。回忆图 7.8 的统计数据：STUDENT 有 45,000 条记录，每块容纳 10 条记录。因此，顺序扫描 STUDENT 可能需要 4500 次块访问。

使用 SID_IDX 索引的成本可以估算如下。该索引会有 45,000 条记录，这意味着在索引中进行二分搜索最多检查 16 条索引记录，因为 log2(45,000) < 16；最坏情况下，每条索引记录都在不同块中。再多一次块访问，用所选索引记录的 datarid 访问目标 STUDENT 记录，总计 17 次块访问。相比顺序扫描，这是相当大的节省。

使用 MAJOR_IDX 索引的成本可以这样计算。图 7.8 的统计数据说明共有 40 个系，这意味着每个系大约有 1125 名学生主修；因此，MAJOR_IDX 对每个 dataval 大约有 1125 条记录。索引记录很小，假设每块能容纳 100 条索引记录，那么这 1125 条索引记录会占 12 块。对索引进行二分搜索同样需要 16 次块访问来找到第一条索引记录。由于相同 dataval 的索引记录在文件中连续出现，遍历这 1125 条索引记录需要 12 次块访问。因此，该查询需要访问 MAJOR_IDX 共 16 + 12 = 28 次。这非常高效。然而，问题在于需要访问多少个 STUDENT 块。当 1125 条索引记录分别沿着自己的 datarid 前进时，每条都会独立请求一个 STUDENT 块。结果是，查询对 STUDENT 产生 1125 次块访问，总访问次数为 1125 + 28 = 1153。虽然这比 SID_IDX 需要的访问次数多得多，但使用 MAJOR_IDX 仍然比顺序搜索快约四倍。

现在假设只有 9 个系，而不是 40 个。那么每个系会有 5000 名学生主修，这意味着 MAJOR_IDX 对每个 dataval 大约有 5000 条索引记录。考虑执行前一个查询时会发生什么：现在会有 5000 条 MAJOR_IDX 记录尝试获取其关联的 STUDENT 记录，这意味着会对 STUDENT 产生 5000 次独立块读取。也就是说，使用索引造成的块访问次数会超过 STUDENT 自身的块数。在这种情况下，使用索引比直接扫描 STUDENT 表还差。这个索引完全没有用。

这些观察可以总结为如下规则：字段 A 上索引的有用性，与表中不同 A 值的数量成正比。这个规则意味着，如果被索引字段是表的键（如 SID_IDX），那么索引最有用，因为每条记录都有不同的键值。反过来，这个规则也意味着，如果不同 A 值的数量少于每块可容纳的记录数，那么该索引将毫无用处（见练习 12.15）。

12.2 SimpleDB 索引 (SimpleDB Indexes)​

上一节展示了索引的使用方式：可以在索引中搜索第一条具有指定 dataval 的记录；可以找到随后所有具有该 dataval 的索引记录；还可以从给定索引记录中提取 datarid。SimpleDB 接口 Index 形式化了这些操作，其代码如图 12.2 所示。

这些方法类似于 TableScan 中的方法。客户端可以把索引定位到开头并遍历其记录，可以检索当前索引记录的内容，也可以插入和删除索引记录。然而，由于索引总是以明确而固定的方式使用，Index 中的方法比 TableScan 中的方法更专门。

具体而言，SimpleDB 客户端总是通过提供一个值（称为搜索键 (search key)）来搜索索引，并检索 dataval 与之匹配的索引记录。beforeFirst 方法以该搜索键作为参数。随后对 next 的调用会把索引移动到下一条 dataval 等于搜索键的记录；如果不存在更多这样的记录，则返回 false。

另外，索引不需要通用的 getInt 和 getString 方法，因为所有索引记录都具有相同两个字段。而且，客户端从不需要检索记录的 dataval，因为它总是搜索键。因此，索引唯一需要的检索方法是 getDataRid，它返回当前索引记录的 datarid。

图 12.2 SimpleDB Index 接口的代码 (The code for the SimpleDB Index interface)

public interface Index {
    public void beforeFirst(Constant searchkey);
    public boolean next();
    public RID getDataRid();
    public void insert(Constant dataval, RID datarid);
    public void delete(Constant dataval, RID datarid);
    public void close();
}

IndexRetrievalTest 类给出了索引用法示例，见图 12.3。代码打开 MajorId 上的索引，查找专业为 20 的学生，检索相应的 STUDENT 记录，并打印学生姓名。

注意，代码使用表扫描来检索 STUDENT 记录，尽管这张表并不是真的被“扫描”。相反，代码调用表扫描的 moveToRid 方法，把扫描定位到所需记录。

与索引相关的元数据类 API 已在图 7.13 中出现。特别是，IndexMgr 中的 getIndexInfo 方法返回一个映射，其中包含指定表所有可用索引的 IndexInfo 元数据。可以从映射中选择所需的 IndexInfo 对象，并调用其 open 方法得到相应的 Index 对象。

图 12.3 在 SimpleDB 中使用索引 (Using an index in SimpleDB)

public class IndexRetrievalTest {
    public static void main(String[] args) {
        SimpleDB db = new SimpleDB("studentdb");
        Transaction tx = db.newTx();
        MetadataMgr mdm = db.mdMgr();

        Plan studentplan = new TablePlan(tx, "student", mdm);
        Scan studentscan = studentplan.open();

        Map<String,IndexInfo> indexes = mdm.getIndexInfo("student", tx);
        IndexInfo ii = indexes.get("majorid");
        Index idx = ii.open();

        idx.beforeFirst(new Constant(20));
        while (idx.next()) {
            RID datarid = idx.getDataRid();
            studentscan.moveToRid(datarid);
            System.out.println(studentscan.getString("sname"));
        }

        idx.close();
        studentscan.close();
        tx.commit();
    }
}

图 12.4 中的 IndexUpdateTest 类说明数据库引擎如何处理对表的更新。代码执行两个任务。第一个任务向 STUDENT 插入一条新记录；第二个任务从 STUDENT 删除一条记录。代码处理插入时，必须在 STUDENT 的每个索引中插入一条对应记录；删除时也类似。注意代码首先打开 STUDENT 的所有索引，并将它们保存到一个映射中。之后，每当需要对每个索引做某件事时，代码都可以遍历这个映射。

图 12.4 更新索引以反映数据记录的变化 (Updating indexes to reflect changes to data records)

Map<String,Index> indexes = new HashMap<>();
Map<String,IndexInfo> idxinfo = mdm.getIndexInfo("student", tx);
for (String fldname : idxinfo.keySet()) {
    Index idx = idxinfo.get(fldname).open();
    indexes.put(fldname, idx);
}

// 任务 1：插入 Sam 的 STUDENT 记录。
studentscan.insert();
studentscan.setInt("sid", 11);
studentscan.setString("sname", "sam");
studentscan.setInt("gradyear", 2023);
studentscan.setInt("majorid", 30);

RID datarid = studentscan.getRid();
for (String fldname : indexes.keySet()) {
    Constant dataval = studentscan.getVal(fldname);
    Index idx = indexes.get(fldname);
    idx.insert(dataval, datarid);
}

// 任务 2：查找并删除 Joe 的记录。
studentscan.beforeFirst();
while (studentscan.next()) {
    if (studentscan.getString("sname").equals("joe")) {
        RID joeRid = studentscan.getRid();
        for (String fldname : indexes.keySet()) {
            Constant dataval = studentscan.getVal(fldname);
            Index idx = indexes.get(fldname);
            idx.delete(dataval, joeRid);
        }
        studentscan.delete();
        break;
    }
}

图 12.3 和图 12.4 的代码在操作索引时，并不知道（也不关心）索引实际如何实现。唯一要求是这些索引实现 Index 接口。12.1 节假设了一种简单索引实现：使用有序索引和二分搜索。实际系统并不使用这种实现，因为它没有利用索引文件的块结构。12.3 到 12.5 节会考察三种更好的实现：两种基于哈希的策略，以及一种基于有序树的策略。

12.3 静态哈希索引 (Static Hash Indexes)​

静态哈希可能是实现索引的最简单方式。虽然它不是最高效的策略，但它容易理解，并且最清楚地展示了基本原理。因此，它是一个很好的起点。

12.3.1 静态哈希 (Static Hashing)​

静态哈希索引使用固定数量 N 的桶，编号从 0 到 N - 1。该索引还使用一个哈希函数 (hash function)，将值映射到桶。每条索引记录根据其 dataval 的哈希结果分配到相应桶。静态哈希索引的工作方式如下：

  • 存储一条索引记录时，将其放入哈希函数分配的桶中。
  • 查找一条索引记录时，对搜索键求哈希，并检查对应桶。
  • 删除一条索引记录时，先按上述方式找到它，然后从桶中删除。

哈希索引的搜索成本与其桶数成反比。如果一个索引包含 B 个块并有 N 个桶，那么每个桶大约包含 B/N 个块，因此搜索一个桶需要大约 B/N 次块访问。

例如，考虑 SName 上的索引。为了简单起见，假设 N = 3，并且哈希函数将字符串 s 映射为 s 中按字母顺序早于 “m” 的字母数量再对 N 取模。还假设一个块能容纳三条索引记录。图 12.5 描绘了三个索引桶的内容，其中 ri 表示第 i 条 STUDENT 记录的 rid。

现在假设要查找所有名为 “sue” 的学生的 datarid。对字符串 “sue” 求哈希得到桶 1，并搜索该桶。该搜索需要两次块访问。类似地，由于 “ron” 哈希到桶 0，只需一次块访问就能确定没有名为 “ron” 的学生。

图 12.5 具有三个桶的静态哈希索引 (A static hash index with three buckets)

这个示例使用了非常小的块大小和桶数。更现实的样例计算可以假设索引使用 1024 个桶，这意味着（假设记录均匀散列到各桶中）：

  • 最多 1024 块的索引只需一次磁盘访问即可搜索。
  • 最多 2048 块的索引只需两次磁盘访问即可搜索。

以此类推。为了给这些数字提供一点直观感受，注意 SName 上的一条索引记录需要 22 字节：varchar(10) 的 dataval 需要 14 字节，datarid 需要 8 字节。如果再为每条记录加 1 字节保存空/使用中标志，那么一个 4K 块能容纳 178 条索引记录。2048 块的索引大小对应的数据文件约有 364,544 条记录。只用两次磁盘访问就能搜索这么多记录，已经相当可观。

12.3.2 实现静态哈希 (Implementing Static Hashing)​

SimpleDB 中的静态哈希由 HashIndex 类实现，其代码如图 12.6 所示。该类把每个桶存储在一个单独表中，表名是索引名与桶号的拼接。例如，索引 SID_INDEX 的 35 号桶表名为 SID_INDEX35。

beforeFirst 方法对搜索键求哈希，并为得到的桶打开一个表扫描。next 方法从扫描当前位置开始读取记录，直到找到一条具有搜索键的记录；如果找不到这样的记录，则返回 false。索引记录的 datarid 以两个整数存储在字段 block 和 id 中。getDataRid 方法从当前记录读取这两个值并构造 rid；insert 方法执行相反操作。

除了实现 Index 接口的方法外，HashIndex 类还实现了静态方法 searchCost。如图 7.15 所示，IndexInfo.blocksAccessed 会调用这个方法。IndexInfo 对象向 searchCost 传入两个参数：索引中的块数，以及每块的索引记录数。它这样做是因为它不知道索引如何计算其成本。对于静态索引，搜索成本只取决于索引大小，因此会忽略 RPB 值。

图 12.6 SimpleDB HashIndex 类的代码 (The code for the SimpleDB class HashIndex)

public class HashIndex implements Index {
    public static int NUM_BUCKETS = 100;
    private Transaction tx;
    private String idxname;
    private Layout layout;
    private Constant searchkey = null;
    private TableScan ts = null;

    public HashIndex(Transaction tx, String idxname, Layout layout) {
        this.tx = tx;
        this.idxname = idxname;
        this.layout = layout;
    }

    public void beforeFirst(Constant searchkey) {
        close();
        this.searchkey = searchkey;
        int bucket = searchkey.hashCode() % NUM_BUCKETS;
        String tblname = idxname + bucket;
        ts = new TableScan(tx, tblname, layout);
    }

    public boolean next() {
        while (ts.next())
            if (ts.getVal("dataval").equals(searchkey))
                return true;
        return false;
    }

    public RID getDataRid() {
        int blknum = ts.getInt("block");
        int id = ts.getInt("id");
        return new RID(blknum, id);
    }

    public void insert(Constant val, RID rid) {
        beforeFirst(val);
        ts.insert();
        ts.setInt("block", rid.blockNumber());
        ts.setInt("id", rid.slot());
        ts.setVal("dataval", val);
    }

    public void delete(Constant val, RID rid) {
        beforeFirst(val);
        while (next())
            if (getDataRid().equals(rid)) {
                ts.delete();
                return;
            }
    }

    public void close() {
        if (ts != null)
            ts.close();
    }

    public static int searchCost(int numblocks, int rpb) {
        return numblocks / HashIndex.NUM_BUCKETS;
    }
}

12.4 可扩展哈希索引 (Extendable Hash Indexes)​

静态哈希索引的搜索成本与桶数成反比：桶越多，每个桶中的块越少。最理想的情况是有足够多的桶，使每个桶正好一个块长。

如果索引大小永远不变，那么计算理想桶数很容易。但实际中，随着新记录插入数据库，索引会增长。那么应该如何决定使用多少桶？假设根据当前索引大小选择桶数，问题在于索引增长后，每个桶最终会包含许多块。但如果根据未来需求选择更大的桶数，那么在索引增长到相应规模之前，当前为空或几乎为空的桶会造成大量空间浪费。

一种称为可扩展哈希 (extendable hashing) 的策略解决了这个问题。它使用非常大量的桶，保证每个桶永远不会超过一个块长。可扩展哈希通过允许多个桶共享同一个块，解决空间浪费问题。其思想是：即使桶很多，它们也共享少量块，因此浪费空间很少。这是一个非常巧妙的想法。

桶共享块是通过两个文件实现的：桶文件 (bucket file) 和桶目录 (bucket directory)。桶文件包含索引块。桶目录把桶映射到块。可以把目录看成一个整数数组，每个桶对应一个整数。称这个数组为 Dir。如果一条索引记录哈希到桶 b，那么这条记录会存储在桶文件的块 Dir[b] 中。

图 12.7 给出了 STUDENT 的 SId 字段上可扩展哈希索引的一个可能内容。为了便于阅读，假设：

  • 一个块可以容纳三条索引记录。
  • 使用八个桶。
  • 哈希函数为 h(x) = x mod 8。
  • STUDENT 表包含七条记录，ID 分别为 1、2、4、5、7、8 和 12。

与前面一样，ri 表示第 i 条 STUDENT 记录的 rid。

图 12.7 STUDENT 的 SId 字段上的可扩展哈希索引 (An extendable hash index on the field SId of STUDENT)

注意桶目录 Dir 的用法。Dir[0] = 0 且 Dir[4] = 0 意味着哈希到 0 的记录（如 r8）或哈希到 4 的记录（如 r4 和 r12）会放入块 0。类似地，哈希到 1、3、5 或 7 的记录会放入块 1，哈希到 2 或 6 的记录会放入块 2。因此，这个桶目录允许索引记录存储在三个块中，而不是八个块中。

当然，有许多方式可以设置桶目录，让这些桶共享三个块。图 12.7 中显示的目录背后有特定逻辑，下一小节会讨论。

12.4.1 共享索引块 (Sharing Index Blocks)​

可扩展哈希目录总是有 2^M 个桶；整数 M 称为索引的最大深度 (maximum depth)。包含 2^M 个桶的目录可以支持长度为 M 位的哈希值。图 12.7 的示例使用 M = 3。实际中，M = 32 是合理选择，因为整数值有 32 位。

最初，一个空桶文件只有一个块，所有目录项都指向这个块。换句话说，这个块被所有桶共享。任何新的索引记录都会插入该块。

桶文件中的每个块都有一个局部深度 (local depth)。局部深度为 L 意味着块中每条记录的哈希值右侧 L 位相同。文件的第一个块初始局部深度为 0，因为它的记录可以有任意哈希值。

假设向索引插入一条记录，但它放不进被分配的块。于是该块会分裂 (split)：桶文件分配另一个块，并将原来满块中的记录分配到旧块和新块之间。重新分配算法基于该块的局部深度。由于块中所有记录当前的哈希值右侧 L 位都相同，算法考察右侧第 L + 1 位：该位为 0 的记录保留在原块中，该位为 1 的记录转移到新块中。注意，这两个块中的记录现在都有 L + 1 位相同。也就是说，每个块的局部深度都增加了 1。

当块分裂时，必须调整桶目录。设 b 为新插入索引记录的哈希值，也就是桶编号。假设 b 的右侧 L 位为 bL...b2b1。可以证明（见练习 12.10），具有这些右侧 L 位的桶编号（包括 b）都指向刚刚分裂的块。因此，目录必须修改，使所有右侧 L + 1 位为 1bL...b2b1 的槽位都指向新块。

例如，假设桶 17 当前映射到局部深度为 2 的块 B。因为 17 的二进制表示为 1001，其右侧 2 位为 01。因此，所有右侧两位为 01 的桶都映射到 B，如 1、5、9、13、17 和 21。现在，假设块 B 已满并需要分裂。系统分配新块 B'，并将 B 和 B' 的局部深度都设为 3。然后它调整桶目录。右侧 3 位为 001 的桶继续映射到块 B（其目录项保持不变）。但右侧 3 位为 101 的桶被改为映射到 B'。也就是说，桶 1、9、17、25 等继续映射到 B，而桶 5、13、21、29 等现在映射到 B'。

图 12.8 给出了向可扩展哈希索引插入记录的算法。

图 12.8 向可扩展哈希索引插入记录的算法 (The algorithm for inserting a record into an extendable hash index)

1. 对 dataval 求哈希，得到桶号 b。
2. 查找 B = Dir[b]，令 L 为块 B 的局部深度。
3a. 如果记录能放入 B，则插入并返回。
3b. 如果记录不能放入 B：
    在桶文件中分配新块 B'。
    将 B 和 B' 的局部深度设为 L + 1。
    调整桶目录，使右侧 L + 1 位为 1bL...b2b1 的桶指向 B'。
    将 B 中的每条记录重新插入索引。
    再次尝试插入新记录。

作为示例，再次考虑 Sid 上的可扩展哈希索引。假设桶目录有 2^10 个桶（即最大深度为 10），哈希函数将每个整数 n 映射为 n % 1024。初始时，桶文件包含一个块，所有目录项都指向该块，如图 12.9a 所示。

现在假设插入学生 4、8、1 和 12 的索引记录。前三次插入都进入块 0，但第四次插入导致分裂。分裂触发以下事件：分配一个新块，局部深度从 0 增加到 1，目录项被调整，块 0 中的记录被重新插入，学生 12 的记录也被插入。结果如图 12.9b 所示。注意，桶目录中的奇数项现在指向新块。此时索引满足如下性质：哈希值为偶数（即最右位为 0）的所有记录位于桶文件的块 0 中；哈希值为奇数（即最右位为 1）的所有记录位于块 1 中。

接下来插入学生 5、7 和 2 的索引记录。前两条记录可以放入块 1，但第三条记录导致块 0 再次分裂。结果如图 12.9c 所示。桶文件的块 0 现在包含所有哈希值以 00 结尾的索引记录，块 2 包含所有哈希值以 10 结尾的记录。块 1 仍包含所有哈希值以 1 结尾的记录。

图 12.9 向可扩展哈希索引插入记录。(a) 包含一个块的索引，(b) 第一次分裂后，(c) 第二次分裂后

任何哈希策略的一个问题是，记录不保证均匀分布。当块分裂时，其中所有记录可能仍然重新哈希到同一个块；如果新记录也哈希到那个块，那么它仍然放不进去，块必须再次分裂。如果局部深度已经等于最大深度，那么不能再分裂，必须创建一个溢出块来保存索引记录。

12.4.2 压缩桶目录 (Compacting the Bucket Directory)​

我们对可扩展哈希的考察还需要处理桶目录的大小。最大深度为 10 的哈希文件需要 2^10 个桶的目录，假设块大小为 4K 字节，可以存储在一个块中。然而，如果哈希文件最大深度为 20，则目录有 2^20 个桶，不管索引大小如何，都需要 1024 个块。前面已经看到桶文件大小如何扩展以适应索引大小。本节说明桶目录也可以从小开始，并按需扩展。

关键思想是注意图 12.9 中的桶目录项具有特定模式。如果某个块的局部深度为 1，那么每隔一个桶项就指向该块。如果某个块局部深度为 2，那么每隔四个桶项就指向该块。一般而言，如果块的局部深度为 L，那么每隔 2^L 个桶项就指向该块。这种模式意味着，整体最高的局部深度决定目录的“周期”。例如，由于图 12.9c 中最高局部深度为 2，桶目录内容每 2^2 项重复一次。

目录项会重复这一事实意味着没有必要存储整个桶目录；只需要存储 2^d 个项，其中 d 是最高局部深度。我们称 d 为索引的全局深度 (global depth)。

搜索索引的算法需要稍作修改，以适应桶目录的这一变化。具体来说，在对搜索键求哈希后，算法只使用哈希值最右侧的 d 位来确定桶目录项。

插入新索引记录的算法也需要修改。与搜索一样，记录的 dataval 会被哈希，哈希值最右侧的 d 位决定该索引记录要插入的目录项。如果块分裂，算法照常执行。唯一例外是，分裂导致该块局部深度大于当前索引全局深度时，必须先递增全局深度，才能重新哈希记录。

递增全局深度意味着桶目录大小加倍。目录加倍非常容易：由于目录项是重复的，加倍后目录的后半部分与前半部分完全相同。加倍完成后，分裂过程可以继续。

为了说明算法，再考虑图 12.9 的例子。初始索引的全局深度为 0，这意味着桶目录只有一个项，指向块 0。插入 4、8 和 1 的记录时，全局深度保持为 0。

由于全局深度为 0，只使用哈希值最右侧 0 位来确定目录项；换句话说，无论哈希值如何，总是使用条目 0。然而，插入 12 的记录时，分裂导致块 0 的局部深度增加，这意味着索引的全局深度也必须增加，桶目录从一个条目加倍为两个条目。最初两个条目都指向块 0；然后所有最右位为 1 的条目被调整为指向新块。结果目录的全局深度为 1，条目为 Dir[0] = 0 和 Dir[1] = 1。

现在全局深度为 1，插入记录 5 和 7 时使用哈希值最右侧 1 位，在两种情况下该位都是 1。因此使用桶 Dir[1]，两条记录都插入块 1。插入记录 2 后发生的分裂导致块 0 的局部深度增加到 2，这意味着全局深度也必须增加。目录加倍为四个条目，初始为 0 1 0 1。随后右侧位为 10 的条目被调整为指向新块，得到目录条目 0 1 2 1。

当索引中某个相同 dataval 的记录数量超过一个块容量时，可扩展哈希效果不好。在这种情况下，再多分裂也没有帮助；即使索引中的记录相对较少，桶目录也会完全扩展到最大大小。为了避免这个问题，插入算法必须修改为检查这种情况，并为该桶创建溢出块链，而不是分裂块。

12.5 B 树索引 (B-Tree Indexes)​

前两种索引策略都基于哈希。现在考虑一种使用排序的方法。其基本思想是按 dataval 对索引记录排序。

12.5.1 如何改进字典 (How to Improve a Dictionary)​

仔细想想，有序索引文件很像字典。索引文件是一系列索引记录，每条记录包含一个 dataval 和一个 datarid。字典是一系列词条，每个词条包含一个单词和一个定义。使用字典时，希望尽快找到某个单词的定义。使用索引文件时，希望尽快找到某个 dataval 的 datarid。图 12.10 总结了这种对应关系。

图 12.10 字典与有序索引文件之间的对应关系

项目字典有序索引文件
条目[word, definition]。一个单词可以有多个定义。[dataval, datarid]。一个 dataval 可以有多个 datarid。
用法查找给定单词的定义。查找给定 dataval 的 datarid。

字典与有序索引之间的紧密对应意味着，可以把对字典的理解应用到有序索引实现问题上。

可以想象一本大约 1000 页的字典。每一页都有页眉，列出该页第一个和最后一个单词。查找某个单词时，页眉可以帮助定位正确页面；只需查看页眉，而不必查看每页内容。找到正确页面后，再在该页中搜索目标单词。

字典还有目录，列出以每个字母开头的单词从哪一页开始。不过这种目录的信息并不特别有用。真正需要的是这样一种目录：它为每个页眉都包含一行，如图 12.11a 所示。这样的目录是一个真正的改进，因为不再需要翻页；所有页眉信息都集中在一个地方。

一本 1000 页的字典会有 1000 个页眉。假设一页能容纳 100 个页眉，那么目录会有 10 页。搜索 10 页比搜索 1000 页好得多，但仍然工作量不小。还需要某种东西帮助搜索目录，如图 12.11b 所示。“目录指南”列出目录中每一页的页眉信息。因此，该指南包含十个页眉，可以轻松放入一页。

有了这种设置，只需查看正好三页就能找到字典中的任何单词：

  • 指南页告诉查找过程应该使用目录中的哪一页。
  • 该目录页告诉查找过程应该使用哪一页词条内容。
  • 然后搜索该词条内容页，找到目标单词。

如果把这种策略用于一本非常大的字典（比如超过 10,000 页），那么目录会超过 100 页，指南也会超过一页。这时可以构造一个“指南的指南”页，避免搜索指南。在这种情况下，找到一个单词需要查看四页。

观察图 12.11 的两个部分可以发现，目录及其指南具有完全相同的结构。这里把这些页面称为字典的目录 (directory)。目录本身是 0 级目录，指南是 1 级目录，指南的指南是 2 级目录，依此类推。

这个改进后的字典具有如下结构：

  • 有许多按序排列的词条内容页。
  • 每个 0 级目录页包含若干词条内容页的页眉。
  • 每个 N + 1 级目录页包含若干 N 级目录页的页眉。
  • 最高层只有一个目录页。

这个结构可以表示为页组成的树，最高层目录页是根，词条内容页是叶子。图 12.12 描绘了这棵树。

图 12.11 改进字典目录。(a) 每页一行，(b) 每个目录页一行

图 12.12 表示为树的改进字典

12.5.2 B 树目录 (The B-Tree Directory)​

树状目录的概念也可以应用于有序索引。索引记录存储在一个索引文件中。0 级目录为索引文件中的每个块保存一条记录。这些目录记录形式为 [dataval, block#]，其中 dataval 是该块中第一条索引记录的 dataval，block# 是该块的块号。

例如，图 12.13a 描绘了 STUDENT 的 SName 字段上的有序索引文件。该索引文件由三个块组成，每个块包含若干记录。图 12.13b 描绘了该索引文件的 0 级目录。目录包含三条记录，每个索引块一条。

如果目录中的记录按 dataval 排序，那么每个索引块中的值范围可以通过比较相邻目录项确定。例如，图 12.13b 中的三条目录记录表示如下信息：

  • 索引文件的块 0 包含 dataval 从 “amy” 到（但不包括）“bob” 的索引记录。
  • 块 1 包含从 “bob” 到（但不包括）“max” 的索引记录。
  • 块 2 包含从 “max” 到结尾的索引记录。

一般而言，第一条目录记录中的 dataval 并不有趣，通常会被特殊值（如 null）替代，表示“从开头开始的一切”。

目录及其索引块通常表示为一棵树，如图 12.13c 所示。那棵树就是一个 B 树示例。注意，可以通过把每个箭头与它前面的 dataval 配对，得到实际的目录记录。树表示中省略了最左箭头对应的 dataval，因为它不需要。

给定一个 dataval v，目录可以用于查找具有该 dataval 的索引记录，或者为该 dataval 插入一条新索引记录。算法如图 12.14 所示。

图 12.13 SName 上的 B 树索引。(a) 有序索引文件，(b) 有序 0 级目录，(c) 索引及其目录的树表示

图 12.14 在图 12.13 的树中查找和插入索引记录的算法

(a) 查找具有指定 dataval v 的索引记录
1. 搜索目录块，找到其 dataval 范围包含 v 的目录记录。
2. 读取该目录记录指向的索引块。
3. 检查该块内容，找到所需索引记录。

(b) 插入具有指定 dataval v 的新索引记录
1. 搜索目录块，找到其 dataval 范围包含 v 的目录记录。
2. 读取该目录记录指向的索引块。
3. 将新索引记录插入该块。

这些算法有两点值得注意。第一，两个算法的第 1 步和第 2 步完全相同。换句话说，插入算法会把索引记录插入到搜索算法会查找它的同一个块中，这当然正是应该发生的事情。第二，每个算法都识别出一个索引块，目标记录应属于这个块；因此，所有具有相同 dataval 的索引记录都必须位于同一个块中。

图 12.13 的 B 树非常简单，因为索引很小。随着索引变大，算法必须处理以下三种复杂情况：

  • 目录可能有多个块。
  • 新插入的索引记录可能放不进它应该进入的块。
  • 可能有许多索引记录具有相同 dataval。

下面的小节将处理这些问题。

12.5.3 目录树 (A Directory Tree)​

继续图 12.13 的例子，假设数据库中插入了更多新学生，使索引文件现在包含八个块。如果为了举例而假设一个块最多容纳三条目录记录，那么 B 树目录至少需要三个块。一个想法是把这些目录块放入文件中并顺序扫描它们；然而，这种扫描效率不高。更好的想法对应于前面改进字典的方法：B 树需要一个指向 0 级目录的“指南”。

也就是说，现在有两级目录块。0 级包含指向索引块的那些块。1 级包含一个指向 0 级块的块。图形上，B 树可能类似图 12.15。搜索这个索引时，从 1 级块开始。例如，假设搜索键为 “jim”。搜索键位于 “eli” 和 “lee” 之间，因此沿中间箭头前进，搜索包含 “joe” 的 0 级块。搜索键小于 “joe”，因此沿左箭头前进，查看包含 “eli” 的索引块。所有 “jim” 的索引记录（如果存在）都在这个块中。

一般而言，只要某一层包含多个目录块，下一更高层就会有目录块指向它们。最终，最高层只包含一个块。这个块称为 B 树的根 (root)。

图 12.15 具有两级目录的 B 树 (A B-tree having two directory levels)

此时可以停下来，确认能独立遍历 B 树。使用图 12.15 选择几个名字，确信可以找到包含每个名字的索引块。这里不应存在歧义：给定一个 dataval，恰好有一个索引块必须包含带有该 dataval 的索引记录。

还要注意 B 树目录记录中的名字分布。例如，1 级节点中的值 “eli” 意味着 “eli” 是中间箭头指向的子树中的第一个名字，也就是 0 级目录块所指向的第一个索引块中的第一条记录。因此，即使 “eli” 没有显式出现在那个 0 级块中，它也出现在 1 级块中。事实上，除了第一个索引块之外，每个索引块的第一个 dataval 都会在 B 树某一层的某个目录块中恰好出现一次。

搜索 B 树需要在每一层访问一个目录块，再访问一个索引块。因此，搜索成本等于目录层数加 1。为了理解这个公式的实际影响，考虑 12.3.1 节末尾的例子，它计算了使用 4K 字节块的 SName 静态哈希索引的搜索成本。与前面一样，每条索引记录为 22 字节，一个块容纳 178 条索引记录。每条目录记录为 18 字节（dataval 14 字节，块号 4 字节），所以一个块能容纳 227 条目录记录。因此：

  • 0 级 B 树可用 2 次磁盘访问搜索，最多能容纳 227 * 178 = 40,406 条索引记录。
  • 1 级 B 树可用 3 次磁盘访问搜索，最多能容纳 227 * 227 * 178 = 9,172,162 条索引记录。
  • 2 级 B 树可用 4 次磁盘访问搜索，最多能容纳 227 * 227 * 227 * 178 = 2,082,080,774 条索引记录。

换句话说，B 树索引极其高效。除非表异常庞大，否则任何所需数据记录都能在不超过五次磁盘访问中检索到。如果一个商业数据库系统只实现一种索引策略，那几乎肯定会使用 B 树。

12.5.4 插入记录 (Inserting Records)​

如果要插入一条新索引记录，图 12.14b 的算法意味着它只能插入到一个确切的索引块中。如果那个块没有空间怎么办？和可扩展哈希一样，解决方法是分裂块。分裂索引块包括以下活动：

  • 在索引文件中分配一个新块。
  • 将较大值那一半索引记录移动到新块。
  • 为新块创建一条目录记录。
  • 将这条新目录记录插入到指向原索引块的同一个 0 级目录块中。

例如，假设图 12.15 中所有索引块都已满。为了插入新索引记录 (hal, r55)，算法沿 B 树目录前进，确定该记录属于包含 “eli” 的索引块。因此，它分裂该块，将其上半部分记录移动到新块中。假设新块是索引文件的块 8，其第一条记录是 (jim, r48)。目录记录 (jim, 8) 会插入 0 级目录块。所得子树如图 12.16 所示。

图 12.16 分裂索引块的效果 (The effect of splitting an index block)

在这个例子中，0 级块中有空间容纳新目录记录。如果没有空间，那么该目录块也需要分裂。例如，回到图 12.15，假设插入索引记录 (zoe, r56)。这条记录会导致最右侧索引块分裂；假设新块号为 9，其第一个 dataval 是 “tom”。于是 (tom, 9) 被插入最右侧 0 级目录块。然而，该 0 级块没有空间，因此它也会分裂。两条目录记录保留在原块中，两条移动到新块中（比如目录文件块 4）。所得目录块和索引块如图 12.17 所示。注意，目录记录 “sue” 仍然存在，但因为它是其块的第一条记录，所以在图中不可见。

事情还没有结束。新的 0 级块需要向 1 级目录块中插入一条记录，因此相同的记录插入过程会递归发生。要插入的新目录记录为 (sue, 4)。使用值 “sue” 是因为它是新目录块子树中的最小 dataval。这种目录记录的递归插入会一直沿 B 树向上传播。如果根块分裂，就会创建一个新的根块，B 树增加一层。图 12.17 中正是这种情况：1 级块没有空间，因此它也分裂，创建一个新的 1 级块，并创建一个新的 2 级块作为根。所得 B 树如图 12.18 所示。

图 12.17 分裂目录块 (Splitting a directory block)

图 12.18 分裂 B 树的根 (Splitting the root of the B-tree)

注意，分裂一个块会把一个满块变成两个半满块。一般而言，B 树容量利用率会在 50% 到 100% 之间。

12.5.5 重复的 dataval (Duplicate Datavals)​

12.1 节的例子显示，索引只有在具有选择性时才有用。因此，即使索引可以有任意数量的记录具有相同 dataval，实际中这种记录通常不会太多，也很可能不足以填满多个块。尽管如此，B 树必须能够处理这类情况。

为了看清问题，假设图 12.18 中有若干条 dataval 为 “ron” 的记录。注意，所有这些记录都必须位于 B 树的同一个叶块中，即包含 “pat” 的那个块。图 12.19a 显示了该块内容。假设插入 “peg” 的记录，并且该记录导致块分裂。图 12.19b 显示了均匀分裂块的结果：ron 的记录被分到了不同块中。

图 12.19b 的 B 树显然不可接受，因为留在 Pat 块中的 Ron 记录无法被访问。因此有如下规则：分裂一个块时，必须把所有具有相同 dataval 的记录放在同一个块中。这个规则只是常识。使用 B 树目录查找具有特定搜索键的索引记录时，目录总是引向一个叶块。如果具有该搜索键的索引记录存在于其他块中，它们永远不会被找到。

这个规则的结果是，索引块可能无法均匀分裂。图 12.19c 描绘了唯一合理的分裂方式：把五条 “ron” 记录放入新块。

只要索引块中的记录至少包含两个不同 dataval，它总能被分裂。唯一真正的问题发生在索引块中的所有记录具有相同 dataval 时。这种情况下，分裂没有用。最好的方法是使用溢出块 (overflow block)。

例如，从图 12.19c 开始，再插入几条名为 “ron” 的学生记录。此时不应分裂块，而应创建一个新的叶块，并把除一条 “ron” 记录之外的其他记录移动进去。这个新块就是溢出块。旧块链接到溢出块，如图 12.20 所示。

图 12.19 分裂具有重复值的叶块。(a) 原始叶块及其父块，(b) 错误的分裂方式，(c) 正确的分裂方式

图 12.20 使用溢出链存储具有相同 dataval 的记录 (Using an overflow chain to store records having the same dataval)

注意，旧块几乎被清空，这允许继续向其中插入更多记录（这些记录可能是也可能不是名为 “ron” 的学生）。如果该块再次填满，就有两种可能：

  • 如果块中至少有两个不同 dataval，则分裂该块。
  • 如果块中只包含 “ron” 记录，则创建另一个溢出块，并将其链接到现有溢出链。

一般而言，一个叶块可以包含一条溢出块链。每个溢出块都会被完全填满。溢出链中的记录总是具有相同 dataval，而该 dataval 总是与非溢出块中第一条记录的 dataval 相同。

假设要搜索具有特定搜索键的索引记录。沿 B 树目录到达某个叶块。如果搜索键不是该块的第一个键，那么按常规检查块中的记录即可。如果搜索键是第一个键，那么还需要使用溢出链中的记录（如果存在）。

虽然 B 树中的索引记录可能包含重复 dataval，目录项却不会重复。原因是，让 dataval 进入目录项的唯一方式是分裂叶块；新块的第一个 dataval 会加入目录。但是在其块中排第一的 dataval 永远不会再次被分裂：如果块中填满了具有该 dataval 的记录，就会创建溢出块，而不是分裂。

12.5.6 实现 B 树页面 (Implementing B-Tree Pages)​

SimpleDB 中实现 B 树的代码位于 simpledb.index.btree 包。该包包含四个主要类：BTreeIndex、BTreeDir、BTreeLeaf 和 BTPage。BTreeDir 与 BTreeLeaf 分别实现 B 树的目录块和索引块。这里使用术语叶 (leaf) 表示索引块，因为它们构成 B 树的叶子；SimpleDB 使用 “leaf” 是为了避免与实现 Index 接口的 BTreeIndex 类混淆。

虽然目录块和叶块包含不同类型的记录，并以不同方式使用，但它们有共同需求，例如需要按排序顺序插入条目，以及需要能够分裂自身。BTPage 类包含这些公共代码。BTreeIndex 类按 Index 接口规定实现实际 B 树操作。

先考虑 BTPage 类。B 树页面中的记录有如下要求：

  • 记录需要保持排序顺序。
  • 记录不需要有永久 ID，这意味着它们可以按需在页面中移动。
  • 页面需要能够把自己的记录分裂到另一个页面。
  • 每个页面需要一个整数作为标志。目录页使用该标志保存自己的层级，叶页使用该标志指向溢出块。

也就是说，可以把 B 树页面看成保存一个有序记录列表（而记录页保存的是无序记录数组）。当新记录插入页面时，先确定其排序位置，然后把其后的记录向右移动一个位置以腾出空间。类似地，删除记录时，其后的记录向左移动以填补空洞。为了实现这种类似列表的行为，页面还必须存储一个整数，用于保存页面中的当前记录数。

BTPage 类的代码如图 12.21 所示。该类中最有趣的方法是 findSlotBefore。该方法以搜索键 k 作为参数，找到最小槽位 x，使得 k <= dataval(x)；然后返回它前一个槽位。这样做的原因是，它能适应页面搜索的所有方式。例如，它在叶页上表现得像 beforeFirst 操作，使对 next 的调用可以检索到第一条具有该搜索键的记录。

图 12.21 SimpleDB BTPage 类的代码 (The code for the SimpleDB class BTPage)

public class BTPage {
    private Transaction tx;
    private BlockId currentblk;
    private Layout layout;

    public BTPage(Transaction tx, BlockId currentblk, Layout layout) {
        this.tx = tx;
        this.currentblk = currentblk;
        this.layout = layout;
        tx.pin(currentblk);
    }

    public int findSlotBefore(Constant searchkey) {
        int slot = 0;
        while (slot < getNumRecs() &&
               getDataVal(slot).compareTo(searchkey) < 0)
            slot++;
        return slot - 1;
    }

    public boolean isFull() {
        return slotpos(getNumRecs() + 1) >= tx.blockSize();
    }

    public BlockId split(int splitpos, int flag) {
        BlockId newblk = appendNew(flag);
        BTPage newpage = new BTPage(tx, newblk, layout);
        transferRecs(splitpos, newpage);
        newpage.setFlag(flag);
        newpage.close();
        return newblk;
    }

    public Constant getDataVal(int slot) {
        return getVal(slot, "dataval");
    }

    public int getFlag() {
        return tx.getInt(currentblk, 0);
    }

    public void setFlag(int val) {
        tx.setInt(currentblk, 0, val, true);
    }
}

现在考虑 B 树的叶块。BTreeLeaf 类的代码如图 12.22 所示。

构造函数首先为指定块创建一个 B 树页面，然后调用 findSlotBefore，把自己定位到第一条包含搜索键的记录之前。调用 next 会移动到下一条记录，并根据该记录是否具有所需搜索键返回 true 或 false。tryOverflow 调用处理叶块包含溢出链的可能性。

delete 和 insert 方法假定页面当前槽位已经由 findSlotBefore 调用设置好。delete 方法反复调用 next，直到遇到具有指定 rid 的索引记录，然后删除该记录。insert 方法移动到下一条记录，这意味着它现在定位在大于或等于该搜索键的第一条记录上。新记录会插入该位置。注意，如果页面已包含具有该搜索键的记录，则新记录会插入列表前端。

insert 方法返回一个 DirEntry 类型对象，即目录记录。如果插入没有导致块分裂，则返回值为 null。如果发生分裂，则返回值是对应新索引块的 (dataval, blocknumber) 项。

图 12.22 SimpleDB BTreeLeaf 类的代码 (The code for the SimpleDB class BTreeLeaf)

public class BTreeLeaf {
    private Transaction tx;
    private Layout layout;
    private Constant searchkey;
    private BTPage contents;
    private int currentslot;
    private String filename;

    public BTreeLeaf(Transaction tx, BlockId blk, Layout layout,
                     Constant searchkey) {
        this.tx = tx;
        this.layout = layout;
        this.searchkey = searchkey;
        contents = new BTPage(tx, blk, layout);
        currentslot = contents.findSlotBefore(searchkey);
        filename = blk.fileName();
    }

    public boolean next() {
        currentslot++;
        if (currentslot >= contents.getNumRecs())
            return tryOverflow();
        else if (contents.getDataVal(currentslot).equals(searchkey))
            return true;
        else
            return tryOverflow();
    }

    public RID getDataRid() {
        return contents.getDataRid(currentslot);
    }

    public void delete(RID datarid) {
        while (next())
            if (getDataRid().equals(datarid)) {
                contents.delete(currentslot);
                return;
            }
    }
}

BTreeDir 类实现目录块，其代码如图 12.23 所示。search 和 insert 方法都从根开始，沿树向下移动，直到找到与搜索键关联的 0 级目录块。search 方法使用简单的 while 循环沿树向下移动；找到 0 级块后，它搜索该页并返回包含搜索键的叶块号。

insert 方法使用递归沿树向下移动。递归调用的返回值表示子页面插入是否导致分裂；如果是，则调用 insertEntry，把新目录记录插入当前页面。如果这次插入又导致当前页分裂，则新页的目录记录会传回父页。null 值表示没有发生分裂。

当对根页调用 insert 返回非 null 值时，会调用 makeNewRoot。由于根必须始终位于目录文件的块 0，该方法会分配一个新块，把块 0 的内容复制到新块，并将块 0 初始化为新的根。新根总是有两个条目：第一条指向旧根，第二条指向刚刚分裂出来的块（作为参数传给 makeNewRoot）。

图 12.23 SimpleDB BTreeDir 类的代码 (The code for the SimpleDB class BTreeDir)

public class BTreeDir {
    private Transaction tx;
    private Layout layout;
    private BTPage contents;
    private String filename;

    public int search(Constant searchkey) {
        BlockId childblk = findChildBlock(searchkey);
        while (contents.getFlag() > 0) {
            contents.close();
            contents = new BTPage(tx, childblk, layout);
            childblk = findChildBlock(searchkey);
        }
        return childblk.number();
    }

    public DirEntry insert(DirEntry e) {
        if (contents.getFlag() == 0)
            return insertEntry(e);
        BlockId childblk = findChildBlock(e.dataVal());
        BTreeDir child = new BTreeDir(tx, childblk, layout);
        DirEntry myentry = child.insert(e);
        child.close();
        return (myentry != null) ? insertEntry(myentry) : null;
    }
}

12.5.7 实现 B 树索引 (Implementing the B-Tree Index)​

现在已经看过 B 树页面如何实现，接下来看看它们如何被使用。BTreeIndex 类实现 Index 接口的方法，协调目录页和叶页的使用，见图 12.24。它的构造函数承担了大部分繁重工作。它根据提供的 Schema 对象构造叶记录布局。随后，它从叶模式中提取相应信息，构造目录记录的模式，并据此构造其布局。最后，如有必要，它格式化根，并插入一条指向叶文件块 0 的条目。

每个 BTreeIndex 对象持有一个打开的 BTreeLeaf 对象。这个叶对象跟踪当前索引记录：它由对 beforeFirst 的调用初始化，由对 next 的调用递增，并由对 getDataRid、insert 和 delete 的调用访问。beforeFirst 方法通过从根目录页调用 search 来初始化这个叶对象。注意，一旦叶页被定位，目录就不再需要，其页面可以关闭。

insert 方法有两个部分。第一部分定位适当的叶页，并把索引记录插入其中。如果叶页分裂，那么该方法把新叶页的索引记录插入目录，从根开始递归。根的非 null 返回值意味着根已分裂，因此调用 makeNewRoot。

delete 方法从叶页删除索引记录，但不尝试修改目录。另一种策略是像插入一样通过 B 树执行删除。那样当目录块变得足够空时，可以将它们合并。然而，块合并算法复杂且容易出错，实践中很少实现。原因是数据库很少变小：删除通常会被其他插入跟随。因此，保留几乎为空的目录块是有意义的，因为假设很快会有记录插入其中。

图 12.24 SimpleDB BTreeIndex 类的代码 (The code for the SimpleDB class BTreeIndex)

public class BTreeIndex implements Index {
    private Transaction tx;
    private Layout dirLayout, leafLayout;
    private String leaftbl;
    private BTreeLeaf leaf = null;
    private BlockId rootblk;

    public void beforeFirst(Constant searchkey) {
        close();
        BTreeDir root = new BTreeDir(tx, rootblk, dirLayout);
        int blknum = root.search(searchkey);
        root.close();
        BlockId leafblk = new BlockId(leaftbl, blknum);
        leaf = new BTreeLeaf(tx, leafblk, leafLayout, searchkey);
    }

    public boolean next() {
        return leaf.next();
    }

    public RID getDataRid() {
        return leaf.getDataRid();
    }

    public void insert(Constant dataval, RID datarid) {
        beforeFirst(dataval);
        DirEntry e = leaf.insert(datarid);
        leaf.close();
        if (e == null)
            return;
        BTreeDir root = new BTreeDir(tx, rootblk, dirLayout);
        DirEntry e2 = root.insert(e);
        if (e2 != null)
            root.makeNewRoot(e2);
        root.close();
    }

    public void delete(Constant dataval, RID datarid) {
        beforeFirst(dataval);
        leaf.delete(datarid);
        leaf.close();
    }

    public static int searchCost(int numblocks, int rpb) {
        return 1 + (int)(Math.log(numblocks) / Math.log(rpb));
    }
}

12.6 索引感知的操作实现 (Index-Aware Operator Implementations)​

本节考虑查询规划器如何利用索引。给定一个 SQL 查询，规划器需要完成两个任务：确定适当的查询树，并为树中的每个操作符选择一个计划。对于第 10 章的基本规划器，第二个任务很简单，因为它只知道每个操作符的一种实现。例如，无论是否存在合适索引，它总是使用 SelectPlan 实现选择节点。

为了让规划器构造使用索引的计划，需要有使用索引的操作符实现。本节为选择和连接操作开发这样的实现。给定一个查询后，规划器就可以自由地把这些实现纳入计划。

当关系操作符可以有多种实现时，规划过程会复杂得多。规划器必须能够为一个查询考虑多个计划，其中一些使用索引，一些不使用；随后必须决定哪个计划最高效。第 15 章将处理这一特性。

12.6.1 选择的索引实现 (An Indexed Implementation of Select)​

SimpleDB 类 IndexSelectPlan 实现选择操作符，其代码如图 12.25 所示。构造函数接受三个参数：底层表的计划（假定是 TablePlan）、适用索引的信息，以及选择常量。open 方法打开索引，并将它（以及常量）传给 IndexSelectScan 构造函数。blocksAccessed、recordsOutput 和 distinctValues 方法使用 IndexInfo 类提供的方法实现成本估算公式。

图 12.25 SimpleDB IndexSelectPlan 类的代码 (The code for the SimpleDB class IndexSelectPlan)

public class IndexSelectPlan implements Plan {
    private Plan p;
    private IndexInfo ii;
    private Constant val;

    public Scan open() {
        TableScan ts = (TableScan) p.open();
        Index idx = ii.open();
        return new IndexSelectScan(idx, val, ts);
    }

    public int blocksAccessed() {
        return ii.blocksAccessed() + recordsOutput();
    }

    public int recordsOutput() {
        return ii.recordsOutput();
    }
}

IndexSelectScan 的代码如图 12.26 所示。Index 变量 idx 保存当前索引记录，TableScan 变量 ts 保存当前数据记录。对 next 的调用会移动到下一条具有指定搜索常量的索引记录；随后表扫描被定位到当前索引记录 datarid 值对应的数据记录。

注意，表扫描从不会被扫描；其当前记录总是通过索引记录的 datarid 得到。剩余扫描方法（getVal、getInt 等）针对当前数据记录，因此直接从表扫描获得。

图 12.26 SimpleDB IndexSelectScan 类的代码 (The code for the SimpleDB class IndexSelectScan)

public class IndexSelectScan implements Scan {
    private TableScan ts;
    private Index idx;
    private Constant val;

    public void beforeFirst() {
        idx.beforeFirst(val);
    }

    public boolean next() {
        boolean ok = idx.next();
        if (ok) {
            RID rid = idx.getDataRid();
            ts.moveToRid(rid);
        }
        return ok;
    }

    public Constant getVal(String fldname) {
        return ts.getVal(fldname);
    }
}

12.6.2 连接的索引实现 (An Indexed Implementation of Join)​

连接操作接受三个参数：两张表 T1 和 T2，以及一个形如 A = B 的谓词 p，其中 A 是 T1 的字段，B 是 T2 的字段。谓词指定 T1 和 T2 的哪些记录组合应该出现在输出表中。特别地，连接操作定义如下：

join(T1, T2, p) = select(product(T1, T2), p)

索引连接 (index join) 是连接的一种实现，用于特殊情况：T2 是存储表，并且在字段 B 上有索引。图 12.27 给出了算法。

图 12.27 使用索引实现连接 (Implementing a join using an index)

对于 T1 中的每条记录 t1：
1. 令 x 为 t1 的 A 值。
2. 使用 B 上的索引，找到 B 值等于 x 的索引记录。
3. 对每条索引记录：
   a. 获取其 datarid。
   b. 直接移动到具有该 RID 的 T2 记录 t2。
   c. 处理输出记录 (t1, t2)。

注意，索引连接的实现类似于乘积；区别在于，代码不需要反复扫描内表，而只需反复搜索索引。因此，索引连接可以比取两张表的乘积高效得多。

IndexJoinPlan 和 IndexJoinScan 类实现索引连接。IndexJoinPlan 的代码如图 12.28 所示。

构造函数参数 p1 和 p2 表示图 12.27 中表 T1 和 T2 的计划。变量 ii 表示 T2 在 B 上的索引，变量 joinfield 对应字段 A。open 方法把计划转换为扫描，把 IndexInfo 对象转换为索引；随后把这些对象传给 IndexJoinScan 构造函数。

图 12.28 SimpleDB IndexJoinPlan 类的代码 (The code for the SimpleDB class IndexJoinPlan)

public class IndexJoinPlan implements Plan {
    private Plan p1, p2;
    private IndexInfo ii;
    private String joinfield;

    public Scan open() {
        Scan s = p1.open();
        TableScan ts = (TableScan) p2.open();
        Index idx = ii.open();
        return new IndexJoinScan(s, idx, joinfield, ts);
    }

    public int blocksAccessed() {
        return p1.blocksAccessed()
            + (p1.recordsOutput() * ii.blocksAccessed())
            + recordsOutput();
    }
}

IndexJoinScan 的代码如图 12.29 所示。beforeFirst 方法把 T1 的扫描定位到第一条记录，取得其 A 值，并把索引定位到该 dataval 之前。next 方法移动到下一个索引值（如果存在）。如果不存在，它移动到 T1 的下一个值，并重置索引指向新的 dataval。

图 12.29 SimpleDB IndexJoinScan 类的代码 (The code for the SimpleDB class IndexJoinScan)

public class IndexJoinScan implements Scan {
    private Scan lhs;
    private Index idx;
    private String joinfield;
    private TableScan rhs;

    public void beforeFirst() {
        lhs.beforeFirst();
        lhs.next();
        resetIndex();
    }

    public boolean next() {
        while (true) {
            if (idx.next()) {
                rhs.moveToRid(idx.getDataRid());
                return true;
            }
            if (!lhs.next())
                return false;
            resetIndex();
        }
    }

    private void resetIndex() {
        Constant searchkey = lhs.getVal(joinfield);
        idx.beforeFirst(searchkey);
    }
}

12.7 索引更新规划 (Index Update Planning)​

如果数据库引擎支持索引，那么规划器必须确保每当数据记录被更新时，其每条索引记录也进行相应更改。图 12.4 的代码片段展示了规划器需要执行的代码类型。本节说明规划器如何做到这一点。

simpledb.index.planner 包包含规划器类 IndexUpdatePlanner，它修改了基本更新规划器，其代码如图 12.30 所示。

executeInsert 方法检索所提及表的索引信息。与基本规划器一样，该方法调用 setVal 来设置每个指定字段的初始值。每次调用 setVal 后，规划器检查该字段上是否有索引；如果有，就向该索引插入一条新记录。

executeDelete 方法构造要删除记录的扫描，与基本规划器一样。在删除每条数据记录之前，该方法使用记录的字段值确定需要删除哪些索引记录。然后它删除这些索引记录，再删除数据记录。

executeModify 方法构造要修改记录的扫描，与基本规划器一样。在修改每条记录之前，该方法先调整被修改字段上的索引（如果存在）。具体而言，它删除旧索引记录，并插入一条新索引记录。

创建表、视图和索引的方法与基本规划器相同。

为了让 SimpleDB 使用索引更新规划器，必须修改 SimpleDB 类中的 planner 方法，使其创建 IndexUpdatePlanner 实例，而不是 BasicUpdatePlanner。

图 12.30 SimpleDB IndexUpdatePlanner 类的代码 (The code for the SimpleDB class IndexUpdatePlanner)

public class IndexUpdatePlanner implements UpdatePlanner {
    private MetadataMgr mdm;

    public int executeInsert(InsertData data, Transaction tx) {
        String tblname = data.tableName();
        Plan p = new TablePlan(tx, tblname, mdm);
        UpdateScan s = (UpdateScan) p.open();
        s.insert();
        RID rid = s.getRid();

        Map<String,IndexInfo> indexes = mdm.getIndexInfo(tblname, tx);
        Iterator<Constant> valIter = data.vals().iterator();
        for (String fldname : data.fields()) {
            Constant val = valIter.next();
            s.setVal(fldname, val);
            IndexInfo ii = indexes.get(fldname);
            if (ii != null) {
                Index idx = ii.open();
                idx.insert(val, rid);
                idx.close();
            }
        }
        s.close();
        return 1;
    }

    public int executeDelete(DeleteData data, Transaction tx) {
        String tblname = data.tableName();
        Plan p = new TablePlan(tx, tblname, mdm);
        p = new SelectPlan(p, data.pred());
        Map<String,IndexInfo> indexes = mdm.getIndexInfo(tblname, tx);
        UpdateScan s = (UpdateScan) p.open();
        int count = 0;
        while (s.next()) {
            RID rid = s.getRid();
            for (String fldname : indexes.keySet()) {
                Constant val = s.getVal(fldname);
                Index idx = indexes.get(fldname).open();
                idx.delete(val, rid);
                idx.close();
            }
            s.delete();
            count++;
        }
        s.close();
        return count;
    }
}

12.8 本章小结 (Chapter Summary)​

  • 给定表 T 的字段 A，A 上的索引是一个记录文件，T 的每条记录对应一条索引记录。每条索引记录包含两个字段：dataval，也就是 T 中对应记录的 A 值；以及 datarid，也就是该对应记录的 rid。
  • 索引能够提高选择和连接操作的效率。系统不必扫描数据表的每个块，而可以执行以下步骤：
    • 搜索索引，找到所有具有选定 dataval 的索引记录。
    • 对找到的每条索引记录，使用其 datarid 访问所需数据记录。 这样，数据库系统就能够只访问包含匹配记录的数据块。
  • 索引不一定有用。经验法则是：字段 A 上索引的有用性与表中不同 A 值的数量成正比。
  • 查询可能以多种方式使用索引。查询处理器会判断其中哪种实现最好。
  • 当表发生变化时，数据库引擎负责更新索引。每当向表中插入（或从表中删除）一条记录时，引擎都必须在每个索引中插入（或删除）一条记录。这种维护成本意味着，只有最有用的索引才值得保留。
  • 索引的实现目标是让搜索只需要很少的磁盘访问。本章讨论了三种索引实现策略：静态哈希、可扩展哈希和 B 树。
  • 静态哈希把索引记录存储在固定数量的桶中，每个桶对应一个文件。哈希函数决定每条索引记录分配到哪个桶。使用静态哈希查找索引记录时，索引管理器对搜索键求哈希并检查相应桶。如果一个索引包含 B 个块和 N 个桶，则每个桶约为 B/N 块长，因此遍历一个桶需要大约 B/N 次块访问。
  • 可扩展哈希允许桶共享块。这比静态哈希更进一步，因为它可以使用非常多的桶，而不需要特别大的索引文件。块共享通过桶目录实现。桶目录可以看成整数数组 Dir；如果一条索引记录哈希到桶 b，那么该记录会存储在桶文件的块 Dir[b] 中。当一条新索引记录放不进其块时，该块会分裂，桶目录会更新，块中记录会重新哈希。
  • B 树把索引记录存储在按 dataval 排序的文件中。B 树还有一个目录记录文件。每个索引块都有一条对应目录记录，其中包含该块第一条索引记录的 dataval 以及指向该块的引用。这些目录记录构成 B 树目录的 0 级。类似地，每个目录块都有自己的目录记录，存储在目录的下一层。顶层由一个块组成，称为 B 树的根。给定一个 dataval，可以通过在目录树每层检查一个块来搜索目录；该搜索会把我们引向包含目标索引记录的索引块。
  • B 树索引极其高效。除非表异常庞大，否则任何所需数据记录都能在不超过五次磁盘访问中检索到。如果一个商业数据库系统只实现一种索引策略，那几乎肯定会使用 B 树。

12.9 建议阅读 (Suggested Reading)​

本章把索引视为辅助文件。Sieg 和 Sciore (1990) 的文章展示了如何把索引视为一种特殊类型的表，以及如何把 indexselect 和 indexjoin 视为关系代数操作符。这种方法允许规划器以更灵活的方式使用索引。

B 树和哈希文件是通用索引结构，最适合查询具有单个选择性搜索键的情况。当查询具有多个搜索键时，例如地理和空间数据库中的查询，它们效果不太好。（例如，B 树无法帮助处理“查找离我家 2 英里以内所有餐馆”这样的查询。）为处理这类数据库，人们开发了多维索引。Gaede 和 Gunther (1998) 的文章综述了这些索引。

B 树搜索的成本由 B 树高度决定，而高度由索引记录和目录记录的大小决定。Bayer 和 Unterauer (1977) 的文章给出了减小这些记录大小的技术。例如，如果叶节点中的 dataval 是字符串，并且这些字符串有公共前缀，那么这个前缀可以在页面开头存储一次，而每条索引记录只存储 dataval 的后缀。此外，目录记录中通常没有必要存储完整 dataval；B 树只需存储该 dataval 足以确定选择哪个子节点的前缀。

Graefe (2004) 的文章描述了一种新的 B 树实现，其中节点从不被覆盖；相反，对节点的更新会创建新节点。该文章表明，这种实现以稍慢读取为代价，带来了更快的更新。

本章只关注如何最小化 B 树搜索执行的磁盘访问次数。虽然 B 树搜索的 CPU 成本不那么重要，但在商业实现中它常常也很显著，需要被考虑。Lomet (2001) 的文章讨论了如何组织 B 树节点以最小化搜索。Chen 等人 (2002) 的文章展示了如何组织 B 树节点以最大化 CPU 缓存性能。

本章也没有考虑如何锁定 B 树节点。SimpleDB 像处理其他数据块一样锁定 B 树节点，并持有锁直到事务完成。然而，事实证明，为保证可串行化，B 树不需要满足第 5 章的锁协议；锁可以提前释放。Bayer 和 Schkolnick (1977) 的文章讨论了这个问题。

Web 搜索引擎维护网页数据库，而网页主要是文本。这些数据库上的查询往往基于字符串和模式匹配，传统索引结构基本上无用。Faloutsos (1985) 讨论了基于文本的索引方法。

一种不寻常的索引策略为每个字段值存储一个位图；位图为每条数据记录包含一位，表示该记录是否包含这个值。位图索引的一个有趣之处是，它们很容易求交，从而处理多个搜索键。O’Neil 和 Quass (1997) 的文章解释了位图索引如何工作。

第 6 章假设表按顺序存储，基本没有组织。然而，也可以根据 B 树、哈希文件或任何其他索引策略来组织表。这里有一些复杂点：例如，当 B 树记录所在块分裂时，记录可能移动到另一个块，这意味着必须小心处理记录 ID；此外，索引策略还必须支持表的顺序扫描（实际上也必须支持整个 Scan 和 UpdateScan 接口）。但基本原则仍然成立。Batory (1982) 的文章描述了如何从基本索引策略构造复杂文件组织。

  • Batory, D., & Gotlieb, C. (1982). A unifying model of physical databases. ACM Transactions of Database Systems, 7(4), 509–539.
  • Bayer, R., & Schkolnick, M. (1977). Concurrency of operations on B-trees. Acta Informatica, 9(1), 1–21.
  • Bayer, R., & Unterauer, K. (1977). Prefix B-trees. ACM Transactions of Database Systems, 2(1), 11–26.
  • Chen, S., Gibbons, P., Mowry, T., & Valentin, G. (2002). Fractal prefetching B+-trees: Optimizing both cache and disk performance. Proceedings of the ACM SIGMOD Conference, pp. 157–168.
  • Faloutsos, C. (1985). Access methods for text. ACM Computing Surveys, 17(1), 49–74.
  • Gaede, V., & Gunther, O. (1998). Multidimensional access methods. ACM Computing Surveys, 30(2), 170–231.
  • Graefe, G. (2004). Write-optimized B-trees. Proceedings of the VLDB Conference, pp. 672–683.
  • Lomet, D. (2001). The evolution of effective B-tree: Page organization and techniques: A personal account. ACM SIGMOD Record, 30(3), 64–69.
  • O’Neil, P., & Quass, D. (1997). Improved query performance with variant indexes. Proceedings of the ACM SIGMOD Conference, pp. 38–49.
  • Sieg, J., & Sciore, E. (1990). Extended relations. Proceedings of the IEEE Data Engineering Conference, pp. 488–494.

12.10 习题 (Exercises)​

概念性练习 (Conceptual Exercises)

12.1. 考虑图 1.1 的大学数据库。哪些字段不适合建立索引？解释理由。

12.2. 说明哪些索引可能有助于评估以下查询。

(a)

select SName
from STUDENT, DEPT
where MajorId = DId and DName = 'math' and GradYear <> 2001

(b)

select Prof
from ENROLL, SECTION, COURSE
where SectId = SectionId and CourseId = CId
and Grade = 'F' and Title = 'calculus'

12.3. 假设决定在 STUDENT 的 GradYear 字段上创建索引。

(a) 考虑以下查询：

select * from STUDENT where GradYear = 2020

使用图 7.8 的统计数据，并假设学生均匀分布在 50 个不同毕业年份中，计算使用索引回答此查询的成本。

(b) 与 (a) 相同，但把 50 个不同毕业年份改为 2、10、20 或 100 个不同毕业年份。

12.4. 证明：如果不同 A 值的数量少于一个块中可容纳的表记录数量，那么字段 A 上的索引没有用。

12.5. 为另一个索引创建索引是否有意义？解释。

12.6. 假设块大小为 120 字节，DEPT 表有 60 条记录。对 DEPT 的每个字段，计算保存索引记录需要多少块。

12.7. Index 接口包含 delete 方法，它删除具有指定 dataval 和 datarid 的索引记录。再提供一个 deleteAll 方法是否有用？该方法删除具有指定 dataval 的所有索引记录。规划器会如何以及何时使用这种方法？

12.8. 考虑连接两张表的查询，例如：

select SName, DName
from STUDENT, DEPT
where MajorId = DId

假设 STUDENT 在 MajorId 上有索引，DEPT 在 DId 上有索引。使用索引连接实现该查询有两种方式，每种索引对应一种方式。使用图 7.8 的成本信息，比较这两种计划的成本。可以从计算中得出什么一般规则？

12.9. 12.4 节的可扩展哈希示例只插入了七条记录。继续该示例，插入 id 为 28、9、16、24、36、48、64 和 56 的学生记录。

12.10. 在可扩展哈希索引中，考虑一个局部深度为 L 的索引块。证明：指向该块的每个桶编号都有相同的右侧 L 位。

12.11. 在可扩展哈希中，桶文件在块分裂时增长。设计一个删除算法，使两个已分裂的块可以合并。这个算法实用吗？

12.12. 考虑一个可扩展哈希索引，其中一个块能容纳 100 条索引记录。假设索引当前为空。

(a) 在索引全局深度变为 1 之前，可以插入多少条记录？

(b) 在全局深度变为 2 之前，可以插入多少条记录？

12.13. 假设一次向可扩展哈希索引插入记录刚刚导致其全局深度从 3 增加到 4。

(a) 桶目录会有多少个条目？

(b) 桶文件中有多少个块恰好只有一个目录项指向它们？

12.14. 解释为什么任何可扩展哈希索引都可以在正好两次块访问中访问，不论其大小如何。

12.15. 假设为 SId 创建 B 树索引。假设一个块中能容纳 3 条索引记录和 3 条目录记录，画出依次插入学生 8、12、1、20、5、7、2、28、9、16、24、36、48、64 和 56 后得到的 B 树。

12.16. 考虑图 7.8 的统计数据，并假设 ENROLL 的 StudentId 字段上有 B 树索引。假设一个块能容纳 100 条索引记录或目录记录。

(a) 索引文件中有多少块？

(b) 目录文件中有多少块？

12.17. 再次考虑 ENROLL 的 StudentId 字段上的 B 树索引，并假设一个块能容纳 100 条索引记录或目录记录。假设索引当前为空。

(a) 多少次插入会导致根分裂（成为 1 级节点）？

(b) 导致根再次分裂（成为 2 级节点）的最小插入次数是多少？

12.18. 考虑 SimpleDB 的 B 树实现。

(a) 在索引扫描期间，同时被 pin 的缓冲区最大数量是多少？

(b) 在插入期间，同时被 pin 的缓冲区最大数量是多少？

12.19. SimpleDB 的 IndexSelectPlan 和 IndexSelectScan 类假定选择谓词是等值比较，例如 GradYear = 2019。然而，一般而言，索引也可以用于范围谓词，例如 GradYear > 2019。

(a) 从概念上解释，GradYear 上的 B 树索引如何用于实现以下查询：

select SName from STUDENT where GradYear > 2019

(b) 为支持 (a) 的答案，SimpleDB 的 B 树代码需要做哪些修改？

(c) 假设数据库在 GradYear 上有 B 树索引。解释为什么该索引可能对实现这个查询没有用。什么时候它会有用？

(d) 解释为什么静态哈希索引和可扩展哈希索引永远无法用于这个查询。

编程练习 (Programming Exercises)

12.20. SimpleDB 更新规划器的 executeDelete 和 executeUpdate 方法使用选择扫描查找受影响记录。另一种可能是在存在合适索引时使用索引选择扫描。

(a) 解释规划器算法需要如何改变。

(b) 在 SimpleDB 中实现这些改变。

12.21. 实现可扩展哈希。选择一个最大深度，使目录最多占用两个磁盘块。

12.22. 考虑对索引记录的如下修改：索引记录不再包含对应数据记录的 rid，而只包含该数据记录所在的块号。因此，索引记录可能少于数据记录；如果一个数据块包含多条具有相同搜索键的记录，一条索引记录会对应所有这些记录。

(a) 解释为什么这种修改可能减少基于索引查询期间的磁盘访问次数。

(b) 为适应这种修改，索引的 delete 和 insert 方法必须如何改变？它们是否比现有方法需要更多磁盘访问？为 B 树和静态哈希编写必要代码。

(c) 这种修改是好主意吗？

12.23. 许多商业数据库系统允许在 SQL create table 语句中指定索引。例如，MySQL 的语法类似：

create table T (A int, B varchar(9), index(A), C int, index(B))

也就是说，形如 index(<field>) 的项可以出现在字段名列表中的任意位置。

(a) 修改 SimpleDB 解析器以处理这个附加语法。

(b) 修改 SimpleDB 规划器以创建适当计划。

12.24. 更新规划器方法 executeCreateIndex 的一个问题是，即使被索引表已经包含记录，新创建的索引也是空的。修改该方法，使其自动为被索引表中的每条现有记录插入索引记录。

12.25. 修改 SimpleDB，使其具有 drop index 语句。创建自己的语法，并相应修改解析器和规划器。

12.26. 修改 SimpleDB，使用户能够指定新创建索引的类型。

(a) 为 create index 语句开发新语法，并给出其文法。

(b) 修改解析器（可能还包括词法分析器）以实现新语法。

12.27. 使用单个索引文件实现静态哈希。该文件的前 N 个块包含每个桶的第一个块。每个桶中的剩余块链接在一起，使用存储在块中的一个整数作为链指针。（例如，如果块 1 中存储的值为 173，那么链中的下一个块就是块 173。值 -1 表示链结尾。）为简单起见，可以把每个块的第一个记录槽专门用于保存这个链指针。

12.28. SimpleDB 在 B 树块一满时就分裂它。另一种算法是允许块满，并在 insert 方法期间分裂它们。具体来说，当代码沿树向下查找叶块时，它会分裂遇到的任何满块。

(a) 修改代码以实现这个算法。

(b) 解释这个代码如何减少 insert 方法的缓冲区需求。