第 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 方法的缓冲区需求。