第 5 章 - 属性、索引和查询 (Attributes, Indexing,and Queries)

本章讨论三个密切相关的主题：属性、索引和查询。这三项功能为文件系统增添了强大的能力，并赋予文件系统许多通常只有数据库才具备的特性。本章旨在说明为什么属性、索引和查询是现代文件系统的重要功能。我们将既讨论这些机制的高层次问题，也深入讲解 BFS（Be File System）的具体实现细节。

5.1 属性 (Attributes)

什么是属性？一般来说，属性是一个名称（通常是一个简短的描述性字符串）和一个值，例如数字、字符串，甚至原始二进制数据。例如，一个属性可以有一个名为“年龄”的名称和一个值为 27 的值，或者一个名为“关键字”的名称和一个值为“计算机 文件系统 日志”的值。属性是关于实体的信息。在文件系统的上下文中，属性是关于文件的附加信息，这些信息没有存储在文件本身中。能够将关于文件的信息与文件一起存储但不在文件内部存储是非常重要的，因为通常修改文件的内容来存储这些信息是不可行的——甚至是不可能的。

程序可以在属性中存储许多类型的数据，例如：

• 窗口系统的图标位置和信息
• 已下载 Web 文档的源 URL
• 文件的类型
• 文件的上次备份日期
• 电子邮件的“收件人”、“发件人”和“主题”行
• 文档中的关键字
• 安全系统的访问控制列表
• 富文本编辑器的样式信息（字体、大小等）
• 图像的伽马校正、颜色深度和尺寸
• 关于文件的评论
• 联系人数据库信息（地址、电话/传真号码、电子邮件地址、URL）

这些是关于对象的信息示例，但它们不一定是我们会——甚至能够——存储在对象本身中的信息。这些示例仅仅开始触及我们可能存储在属性中的信息种类。将任意名称/值对附加到文件的能力开启了许多有趣的可能性。

属性的使用示例 (Examples of the Use of Attributes)

考虑管理人员信息的需要。电子邮件程序需要一个人的电子邮件地址，联系人管理器需要一个电话号码，传真程序需要一个传真号码，而文字处理器的邮件合并功能需要一个实际地址。这些程序中的每一个都有特定的需求，通常每个程序都会拥有其所需的关于人的信息的私有副本，尽管许多信息最终会在每个应用程序中重复。如果关于某个人的某条信息应该更改，则需要更新几个不同的程序——这不是理想的情况。

相反，使用属性，文件系统可以将人表示为一个文件。文件的名称将是人的姓名，或者可能是更唯一的标识符。这个“人文件”的属性可以维护关于人的信息：电子邮件地址、电话号码、传真号码、URL 等等。然后，上面提到的每个程序都简单地访问它需要的属性。所有程序都从同一个地方获取信息。此外，需要存储不同信息的程序可以添加和修改其他属性，而不会干扰现有程序。

在这个例子中，属性的强大之处在于许多程序可以轻松地共享信息。因为对属性的访问是统一的，所以应用程序只需要就属性的名称达成一致。这有助于程序协同工作，消除了浪费的数据重复，并使程序不必都实现自己的小型数据库。另一个好处是，需要先前未知属性的新应用程序可以添加新属性，而不会中断使用旧属性的其他程序。在这个例子中，将信息存储为属性也带来了其他好处。从用户的角度来看，存在一个关于人员信息的单一界面。他们可以期望，如果在电子邮件程序中选择一个人，电子邮件程序将使用该人的电子邮件属性并允许用户向他们发送电子邮件。同样，如果用户将“人文件”的图标拖放到传真程序上，很自然地会期望传真程序知道您想向该人发送传真。在这个例子中，属性提供了一种简单的方法来集中存储关于人员的信息，并以一种有助于应用程序之间共享的方式进行存储。

其他不太复杂的例子比比皆是。Web 浏览器可以存储已下载文件的源 URL，以便用户稍后可以询问“返回到此文件来自的站点”。图像扫描程序可以将关于扫描的颜色校正信息作为文件的属性存储。使用字体和样式的文本编辑器可以将关于文本的样式信息作为属性存储，而将原始文本保留为纯 ASCII（这将允许使用多种字体、样式、颜色等编辑源代码）。文本编辑器可以合成文档中包含的主要关键字，并将这些关键字存储为文档的属性，以便以后可以搜索包含某种类型内容的文件。

这些例子都说明了如何使用属性。属性为程序提供了一种存储关于文件的数据的机制，这种方式使得以后很容易检索信息并与其他应用程序共享信息。

属性 API (Attribute API)

可以对属性执行许多操作，但 BeOS 中的文件系统接口保持列表简短。程序可以对文件属性执行以下操作：

• 写入属性
• 读取属性
• 打开属性目录
• 读取属性目录
• 重置属性目录
• 关闭属性目录
• 获取属性状态
• 删除属性
• 重命名属性

毫不奇怪，这些操作与文件的相应操作非常相似，并且它们的行为几乎相同。要访问文件的属性，程序必须首先打开该文件，并使用该文件描述符作为访问属性的句柄。文件的属性没有单独的文件描述符。文件的属性目录类似于常规目录。程序可以打开它并遍历它以枚举文件的所有属性。

值得注意的是，列表中缺少像我们对常规文件那样打开和关闭属性的操作。因为属性不使用单独的文件描述符进行访问，所以打开和关闭操作是多余的。用户级 API 调用以从属性读取和写入数据具有以下原型：

ssize_t fs_read_attr(int fd, const char *attribute, uint32 type, off_t pos, void *buf, size_t count);
ssize_t fs_write_attr(int fd, const char *attribute, uint32 type, off_t pos, const void *buf, size_t count);

每个调用都封装了执行 I/O 所需的所有状态。文件描述符指示要操作哪个文件，属性名称指示要对哪个属性执行 I/O，类型指示正在写入的数据类型，而位置指定在属性中的偏移量以执行 I/O。属性读/写操作的语义与文件读/写操作的语义相同。写操作还有一个额外的语义：如果属性名称不存在，它将隐式创建它。写入现有属性将覆盖该属性（除非位置非零，在这种情况下，如果该属性已经存在，它将扩展该属性）。

列出文件属性的函数与列出目录内容的标准 POSIX 函数非常相似。打开属性目录操作启动对属于文件的属性列表的访问。打开属性目录操作返回一个文件描述符，因为与读取目录相关的状态无法在用户空间中维护。读取属性目录操作返回下一个连续条目，直到没有更多条目为止。重置操作将目录流中的位置重置到目录的开头。当然，关闭操作只是关闭文件描述符并释放相关的状态。

其余的操作（stat、remove 和 rename）是典型的内务管理操作，没有细微之处。stat 操作给定一个文件描述符和属性名称，返回关于属性大小和类型的信息。remove 操作从与文件关联的属性列表中删除指定的属性。rename 操作目前在 BFS 中尚未实现。

属性细节 (Attribute Details)

如前所述，属性是一个字符串名称和一些任意的数据块。在 BeOS 中，属性还声明了与名称一起存储的数据类型。数据类型可以是整数类型（字符串、整数或浮点数），也可以是任意大小的原始数据。类型字段仅在严格意义上是支持索引所必需的。

在决定使用什么数据结构来存储属性时，我们的第一个想法可能是定义一个新的数据结构。但是，如果我们抵制住这种诱惑，并仔细查看属性必须存储的内容，我们会发现其描述与文件的描述惊人地相似。在最基本的层面上，属性是一个命名的实体，它必须存储任意数量的数据。虽然大多数属性很可能都很小，但在属性中存储大量数据非常有用并且需要完全支持。考虑到这一点，重用文件底层的数据结构（即 i 节点）是很有意义的。i 节点表示磁盘上的数据流，因此可以存储任意数量的信息。通过将属性的内容存储在 i 节点的数据流中，文件系统不必管理一组专门用于属性的单独数据结构。

与文件关联的属性列表也需要一个数据结构和存储位置。借鉴我们观察到的属性与文件的相似性，很自然地将属性列表存储为目录。目录正是完成此任务所需的属性：它将名称映射到 i 节点。将所有结构绑定在一起所需的最后一部分是文件 i 节点到属性目录 i 节点的引用。图 5-1 图示了这些结构之间的关系。然后可以从文件 i 节点遍历到列出所有属性的目录。从目录条目中可以找到每个属性的 i 节点，并且访问属性 i 节点使我们能够访问属性的内容。

这种实现是最容易理解和实现的。这种方法的唯一缺点是，虽然理论上很优雅，但实际上其性能将非常糟糕。性能会受到影响，因为每个属性都需要多次磁盘操作才能找到和加载。BFS 的初始设计使用了这种方法。当它第一次呈现给其他工程师时，由于访问属性所需的间接级别，它很快就被否决了（并且这样做是正确的）。

这种性能瓶颈是一个问题，因为在 BeOS 中，窗口系统将文件的图标位置存储为文件的属性。因此，使用这种设计，当显示目录中的所有文件时，每个文件至少需要一次磁盘访问来获取文件 i 节点，一次访问来加载属性目录 i 节点，另一次目录访问来查找属性名称，另一次访问来加载属性 i 节点，最后还需要一次磁盘访问来加载属性的数据。鉴于当前的磁盘驱动器的访问时间约为毫秒级（有时是数十毫秒），而 CPU 速度达到亚 5 纳秒级，很明显，强迫 CPU 等待五次磁盘访问来显示单个文件将严重影响性能。

我们知道文件的许多属性都很小，并且提供对它们的快速访问将使许多程序受益。本质上，问题在于文件的至少一些属性需要更有效的访问。解决方案与大约在同一时间出现的另一个设计问题结合在一起。BFS 需要能够在卷上存储任意数量的文件，并且预先在卷上为 i 节点保留空间被认为不可接受。在文件系统初始化时保留 i 节点的空间是管理 i 节点的传统方法，但这会导致在文件很少的大型驱动器上浪费大量空间，并且总是会成为文件很多但 i 节点不足的文件系统的限制。BFS 只需要消耗磁盘上存储的文件所需的空间——不多也不少。这意味着 i 节点很可能存储为单独的磁盘块。最初看来，将每个 i 节点存储在其自己的磁盘块中会浪费太多空间，因为 i 节点结构的大小只有 232 字节。然而，当这种存储 i 节点的方法与需要存储几个小属性以进行快速访问的需求相结合时，解决方案就很清楚了。i 节点块的剩余空间适合存储文件的小属性。BFS 将 i 节点块末尾的这个空间称为小数据区。从概念上讲，BFS i 节点如图 5-2 所示。

因为并非所有属性都能放入 i 节点的小数据区，所以 BFS 继续使用属性目录和 i 节点来存储额外的属性。访问非常驻属性的成本确实高于小数据区中的属性，但这种权衡是值得的。最常见的情况非常高效，因为一次磁盘读取将检索 i 节点和许多通常最需要的小属性。

小数据区纯粹是 BFS 的实现细节，对程序员完全透明。事实上，不可能请求将属性放入小数据区。暴露这种性能优化的细节会破坏原本清晰的属性 API。

好的，以下是原文的中文翻译：

小数据区域详情 (small data Area Detail)

BFS 用于管理小数据区域空间的结构体定义为：

typedef struct small_data {
    uint32 type;
    uint16 name_size;
    uint16 data_size;
    char name[1];
} small_data;

这个数据结构经过优化，以使其尽可能小，从而可以在 i-node 中封装尽可能多的实例。name_size 和 data_size 这两个大小字段被限制为 16 位整数，因为我们知道 i-node 的大小永远不会超过 8K。type 字段也应该是 16 位，但我们必须保留从更高层软件传递进来的确切类型。

name 字段的内容大小可变，并开始于 small_data 结构体的最后一个字段（结构体中的成员 name 仅仅是一个便于引用构成名称的字节起始位置的方式，而不是一个只有单字符的固定大小名称）。属性的数据部分存储在 name 后面的字节中，没有填充。一个产生指向 small_data 结构体数据部分的指针的 C 宏定义如下：

#define SD_DATA(sd) \
    (void *)((char *)sd + sizeof(*sd) + (sd->name_size-sizeof(sd->name)))

以典型的令人费解的 C 编程风格，这个宏使用了指针算术来生成一个指向可变大小 name 字段后面字节的指针。

图 5-3 展示了小数据区域的使用方式。

所有操作 small_data 结构体的例程都期望一个指向 i-node 的指针，在 BFS 中，这个指针不仅仅是指 i-node 结构体本身，而是 i-node 所在的整个磁盘块。存在以下例程来操作 i-node 的小数据区域：

• 查找具有给定名称的 small_data 结构体
• 创建具有名称、类型和数据的新 small_data 结构体
• 更新现有的 small_data 结构体
• 获取 small_data 结构体的数据部分
• 删除 small_data 结构体

从 i-node 地址开始，第一个 small_data 结构体的地址可以通过将 i-node 结构体的大小添加到其地址轻松计算出来。得到的指针是小数据区域的基址。有了第一个 small_data 结构体的地址，操作小数据区域的例程都期望并维护一个紧密 packed 的 small_data 结构体数组。空闲空间始终是数组中的最后一个项，并被管理为一个 type 为零、名称长度为零、数据大小等于剩余空闲空间大小（不包括结构体本身的大小）的 small_data 项。

由于 BFS 尽可能紧密地 packed small_data 结构体，任何给定的 small_data 结构体实例都不太可能在“好”的内存边界上对齐（即，“好”边界是四或八的倍数的地址）。这可能在某些 RISC 处理器上导致对齐异常。如果将 BeOS 移植到像 MIPS 这样的架构上，BFS 必须先将 small_data 结构体复制到 Properly aligned 的临时变量中，然后从那里进行解引用，这将使代码变得复杂得多。由于 BeOS 当前运行的 CPU（PowerPC 和 Intel x86）没有这个限制，当前的 BFS 代码忽略了这个问题，尽管它是非可移植的。

i-node 的小数据区域非常适合存储一系列紧密 packed 的属性。然而，实现并不完美，BFS 还可以使用其他技术进一步减小小数据结构体的大小。例如，可以使用 C 的 union 类型来消除固定大小属性（如整数或浮点数）的大小字段。或者属性名称可以存储为哈希值，而不是显式字符串，然后在哈希表中查找字符串。尽管这些技术可以节省一些空间，但它们会使代码更加复杂，并且更难以调试。尽管看起来很简单，但 small_data 属性的处理经过了多次迭代才最终正确。

大局：小数据属性及更多 (The Big Picture: small data Attributes and More)

前面的描述详细介绍了使用 small_data 结构体的机制，但没有提供太多关于它如何与 BFS 的通用属性机制联系起来的见解。正如我们之前讨论的，一个文件可以有任意数量的属性，每个属性都是任意大小的名称/值对。文件系统内部必须管理 reside 在小数据区域以及位于属性目录中的属性。

概念上管理这两组属性是直观的。每次程序请求属性操作时，文件系统会检查属性是否在小数据区域中。如果不在，它 then 会在属性目录中查找该属性。然而，在实践中，这增加了代码的复杂性。例如，写属性操作使用了列表 5-1 中所示的算法。

if length of data being written is small
 find the attribute name in the small_data area 
    if found
  delete it from small_data and from any indices
 else
  create the attribute name
 write new data
 if it fits in the small_data area
  delete it from the attribute directory if present
 else
  create the attribute in the attribute directory 
        write the data to the attribute i-node 
        delete name from the small_data area if it exists
else
 create the attribute in the attribute directory 
    write the data to the attribute i-node 
    delete name from the small_data area if it exists

诸如在将属性添加到小数据区域后将其从属性目录中删除之类的微妙之处，在重写现有属性导致属性位置发生变化的情况下是必需的。

操作 reside 在文件属性目录中的属性变得更容易，因为许多操作可以重用适用于文件的现有操作。在属性目录中创建属性使用与在目录中创建文件相同的底层函数。同样，读、写和删除属性的操作使用与文件相同的例程。这些操作所需的 glue code 具有类似于对小数据区域操作的微妙之处（如果在将属性写入属性目录时存在于小数据区域中，则需要从 small_data 区域中删除属性，等等）。

文件系统可重入性是另一个增加复杂性的问题。由于文件系统使用相同的操作访问属性目录和属性，我们必须小心，确保相同的资源永远不会被第二次锁定（这将导致死锁）。幸运的是，像这样的死锁问题如果遇到会非常 catastrophic，从而易于检测（文件系统会锁定）并纠正（很容易检查有问题代码的状态，并从那里回溯到解决方案）。

属性总结 (Attribute Summary)

属性的基本概念是一个名称以及与该名称关联的一些数据块。属性可以是简单的事情：

Keywords = bass, guitar, drums

或者它可以是更复杂的关联数据。与属性关联的数据是自由形式的，可以存储任何内容。在文件系统中，属性通常附加到文件上，并存储关于文件内容的信息。

实现属性并不困难，尽管直接的实现将在性能方面受到影响。为了加速属性访问，BFS 直接在文件的 i-node 中支持一个快速属性区域。快速属性区域显著降低了访问属性的成本。

5.2 索引 (Indexing)

为了理解索引，想象以下场景很有用：假设你去图书馆想找一本书。在图书馆里，你没有找到井井有条的卡片目录，而是一大堆卡片，每张卡片都包含关于特定书籍的完整信息（属性）。如果这堆卡片没有任何顺序，找到你想要的书将非常繁琐。由于图书管理员更喜欢秩序而不是混乱，他们维护了三份关于书籍信息的索引。每个目录都按字母顺序组织，一份按书名，一份按作者姓名，一份按主题领域。这使得通过搜索作者、书名或主题索引卡片来定位特定书籍相当简单。

文件系统中的索引与图书馆中的卡片目录非常相似。文件系统中的每个文件都可以被认为是图书馆中的一本书。如果文件系统没有索引关于文件的信息，那么找到一个特定的文件可能需要遍历所有文件才能找到匹配的文件。当文件很多时，这种详尽的搜索非常缓慢。索引诸如文件名、文件大小和上次修改时间等项目可以显著减少查找文件所需的时间。在文件系统中，索引只是一个按某种标准排序的文件列表。

随着文件可能拥有的附加属性的出现，很自然地允许索引除文件固有的属性之外的其他属性。因此，文件系统可以索引一个人的电话号码属性、电子邮件地址的“发件人”字段或文档的关键字。索引附加属性为用户在文件系统中查找信息的方式带来了相当大的灵活性。

如果文件系统索引了关于文件的属性，用户可以提出复杂的查询，例如“查找过去一周内收到的来自 Bob Lewis 的所有电子邮件”。文件系统可以搜索其索引并生成符合条件的文件列表。虽然电子邮件程序也可以做同样的事情，但在文件系统中使用通用机制进行索引允许所有应用程序都拥有内置的数据库功能，而无需它们各自实现自己的数据库。

支持索引的文件系统突然呈现出传统数据库的许多特性，两者之间的区别变得模糊。虽然支持属性和索引的文件系统与数据库非常相似，但两者并不相同，因为它们的目标将两者推向略微不同的方向。例如，数据库牺牲了一些灵活性（数据库通常具有固定大小的条目，在创建数据库后很难扩展记录等），以换取功能（更高的速度和处理更多条目的能力，更丰富的查询界面）。文件系统以开销为代价提供了更多的通用性：在文件系统中将数百万个 128 字节的记录存储为文件将产生相当大的开销。因此，尽管表面上看，带有索引的文件系统和数据库共享许多功能，但它们各自不同的设计目标使它们保持不同。

通过简化许多细节，上述示例给出了索引可能实现的功能的初步印象。以下各节将讨论涉及的更重要的问题。

什么是索引？ (What Is an Index?)

我们需要回答的第一个问题是：什么是索引？索引是一种允许高效查找输入值的机制。使用我们的卡片目录示例，如果我们查看作者索引中的“Donald Knuth”，我们将找到由 Donald Knuth 撰写的书籍的引用，并且这些引用将允许我们找到该书的实体副本。查找值“Knuth”是高效的，因为目录是按字母顺序排列的。我们可以直接跳到作者姓名以“K”开头的卡片部分，然后从那里跳到姓名以“Kn”开头的卡片，依此类推。

在计算机术语中，索引是一种存储键/值对并允许高效查找键的数据结构。键可以是字符串、整数、浮点数或其他可以比较的数据项。与键一起存储的值通常只是对与该键关联的其余数据的引用。对于文件系统，与键关联的值是与该键关联的文件的 i 节点号。

索引的键必须始终具有一致的顺序。也就是说，如果索引将键 A 与键 B 进行比较，它们必须始终具有相同的关系——A 小于 B、大于 B 或等于 B。除非 A 或 B 的值发生变化，否则它们的关系不能改变。对于字符串和整数等计算机基本类型，这不是问题。比较更复杂的结构会使情况变得不太清楚。

许多教科书阐述了管理排序数据列表的不同方法。通常，每种保持排序数据列表的方法都有一些优点和一些缺点。对于文件系统，索引数据结构必须满足以下几个要求：

• 它必须是一个磁盘上的结构。
• 它必须具有合理的内存占用。
• 它必须具有高效的查找。
• 它必须支持重复条目。

首先，文件系统使用的任何索引方法本质上都必须是磁盘上的数据结构。大多数常见的索引方法仅在内存中工作，这使得它们不适合文件系统。文件系统索引必须存在于永久存储中，以便它们能够在重启和崩溃后幸存下来。此外，由于文件系统仅仅是整个操作系统的一个支持部分，而不是焦点，因此使用索引不能对系统的其余部分施加不适当的要求。因此，不能将整个索引保存在内存中，也不能在每次文件系统访问索引时加载其重要部分。文件系统上可能存在许多索引，并且文件系统需要能够一次加载任意数量的索引，并且能够在需要时在它们之间切换，而每次访问新索引时都不会产生昂贵的性能损失。这些限制排除了商业数据库领域常用的许多索引技术。

索引的主要要求是它可以高效地查找键。查找操作的效率会对文件系统的整体性能产生巨大影响，因为每次访问文件名都必须执行查找。因此，很明显，查找必须是索引上最有效的操作。

最后一个要求，也许也是最困难的要求，是需要在索引中支持重复条目。乍一看，支持重复条目似乎是不必要的，但事实并非如此。例如，如果文件系统索引文件名，则重复条目是必不可少的。因为如果文件位于不同的目录中，则文件可以具有相同的名称，因此会有许多重复的名称。根据文件系统的使用情况，每个索引的重复数量可能从几个到几万个不等。如果这个问题没有得到妥善处理，性能可能会受到严重影响。

数据结构选择 (Data Structure Choices)

尽管存在许多索引数据结构，但文件系统可以考虑的只有少数几种。到目前为止，用于存储磁盘索引最流行的数据结构是 B 树或其任何变体（B*树、B+树等）。哈希表是另一种可以扩展到磁盘数据结构的技术。每种数据结构都有其优点和缺点。我们将简要讨论每种数据结构及其特性。

B 树 (B-trees)

B 树是一种树状数据结构，它将数据组织成节点的集合。与真正的树一样，B 树从根节点（起始节点）开始。从根节点的链接指向其他节点，而这些节点又链接到其他节点，直到链接到达叶节点。叶节点是没有指向其他节点的链接的 B 树节点。

每个 B 树节点存储一定数量的键/值对（键/值对的数量取决于节点的大小）。每个键/值对旁边都有一个指向另一个节点的链接指针。B 树节点中的键保持有序，并且与键/值对关联的链接指向一个其所有键都小于当前键的节点。

图 5-4 显示了一个 B 树的示例。在这里我们可以看到，与单词“cat”关联的链接指向仅包含按字典顺序小于单词“cat”的值的节点。同样，与单词“indigo”关联的链接指向一个包含小于“indigo”但大于“deluxe”的值的节点。底行中的节点（able、ball 等）都是叶节点，因为它们没有链接。

B 树的一个重要特性是它们维护节点之间的相对顺序。也就是说，根节点中来自“man”的链接所指向的所有节点都将包含大于“cat”且小于“man”的条目。B 树搜索例程利用此特性来减少查找特定节点所需的工作量。

了解到 B 树节点是排序的，并且每个条目的链接都指向键值小于当前键值的节点，我们可以对 B 树进行搜索。通常搜索每个节点使用二分搜索，但为了简化讨论，我们将使用顺序搜索进行说明。如果我们想找到单词“deft”，我们将从根节点开始，并在其键中搜索单词“deft”。第一个键“cat”小于“deft”，所以我们继续。单词“deft”小于“man”，所以我们知道它不在这个节点中。“man”有一个链接，所以我们跟随链接到下一个节点。在第二级节点（deluxe indigo）中，我们将“deft”与“deluxe”进行比较。同样，“deft”小于“deluxe”，所以我们跟随相关的链接。我们到达的最后一个节点包含单词“deft”，我们的搜索成功了。如果我们搜索单词“depend”，我们将跟随来自“deluxe”的链接，并发现我们的键大于“deft”，因此我们将停止搜索，因为我们到达了一个叶节点，并且我们的键大于节点中的所有键。

关于搜索算法，需要注意的重要部分是我们进行搜索所需的节点数量很少（10 个节点中的 3 个）。当有成千上万个节点时，节省是巨大的。当 B 树像上面的例子一样保持良好的平衡时，搜索包含 N 个键的树所需的时间与 logk(N) 成正比。对数的底 k 是每个节点的键数。当键很多时，这是一个非常好的搜索时间，这也是 B 树作为一种索引技术流行的主要原因。

B 树性能的关键在于它们保持合理的平衡。B 树的一个重要特性是，树的任何一个分支都不会比任何其他分支高得多。维护此特性是插入和删除操作的要求，这使得它们的实现比搜索操作复杂得多。

向 B 树中插入首先找到所需的插入位置（通过执行搜索操作），然后尝试插入键。如果插入键会导致节点过满（每个节点都有固定的最大大小），则该节点将被拆分为两个节点，每个节点获得一半的键。拆分节点需要修改被拆分节点的父节点。拆分节点的父节点需要更改指向子节点的指针，因为现在有两个子节点。此更改可能会一直向上传播到根节点，甚至可能更改根节点（从而创建一个新的根节点）。

从 B 树中删除的操作方式与插入非常相似。然而，删除操作可能导致成对的节点合并为一个节点，而不是拆分节点。合并相邻节点需要修改父节点，并且可能导致与插入操作类似的重新平衡操作。这些对插入和删除算法的描述并非旨在作为实现指南，而是为了让您了解所涉及的过程。如果您对此主题感兴趣，您应该参考文件结构教科书，例如 Folk、Zoellick 和 Riccardi 的书，以了解实现 B 树的具体细节。

B 树的另一个优点是它们的结构本质上易于存储在磁盘上。B 树中的每个节点通常都是固定大小的，例如 1024 或 2048 字节，这个大小与文件系统的磁盘块大小非常吻合。将 B 树存储在单个文件中非常容易。B 树中节点之间的链接只是文件中其他节点的偏移量。因此，如果一个节点位于文件中的 15,360 位置，那么存储指向它的指针只需存储值 15,360 即可。检索存储在那里的节点需要寻找到文件中的该位置并读取该节点。

当向 B 树添加键时，扩展树所需要做的就是增加包含 B 树的文件的大小。虽然拆分节点和重新平衡树似乎是一个潜在的昂贵操作，但事实并非如此，因为不需要移动大量数据。将一个节点拆分为两个节点涉及在文件末尾分配额外的空间，但其他受影响的节点只需要更新它们的指针；不需要重新排列数据来为新节点腾出空间。

B 树变体 (B-tree Variants)

标准 B 树有几种变体，其中一些甚至比传统的 B 树具有更好的特性。最简单的修改是 B* 树，它增加了节点在分裂之前可以达到的最大填充程度。通过增加每个节点的键数，我们降低了树的高度并加快了搜索速度。B 树的另一个更重要的变体是 B+ 树。B+ 树增加了一个限制，即所有键/值对只能驻留在叶节点中。B+ 树的内部节点仅包含索引值，以引导搜索到正确的叶节点。存储在内部节点中的索引值是叶节点中键的副本，但索引值仅用于搜索，从不用于检索。通过这种扩展，将叶节点从左到右链接在一起很有用（例如，在上面定义的 B 树中，节点 able 将包含指向 ball 的链接，依此类推）。通过链接叶节点，可以轻松地按顺序迭代 B+ 树的内容。另一个好处是内部节点可以具有与叶节点不同的格式，从而可以轻松地将尽可能多的数据打包到内部节点中（这使得树更有效）。

如果被索引的数据是文本字符串，则可以应用另一种技术来压缩树。在前缀 B+ 树中，内部节点仅存储遍历树并仍然到达正确叶节点所需的最小部分的键。此修改可以减少需要在内部节点中存储的数据量。通过减少存储在内部节点中的信息量，前缀 B+ 树比不进行压缩时更短。

哈希 (Hashing)

哈希是另一种在磁盘上存储数据的技术。哈希是一种技术，其中输入键通过一个函数生成该键的哈希值。相同的键值应始终生成相同的哈希值。哈希函数接受一个键并返回一个整数值。通过将哈希值对表大小取模来生成表中的有效索引，键的哈希值用于索引哈希表。存储在表中的项是键/值对，就像 B 树一样。哈希的优点是查找项的成本是恒定的：哈希函数与哈希表中的项数无关，因此查找非常高效。

除非在所有输入值都预先已知这种特殊情况下，否则输入键的哈希值并不总是唯一的。不同的键可能会生成相同的哈希值。处理多个键冲突在同一哈希值上的一种方法是将所有哈希到同一表索引的值链接在一个链表中（也就是说，每个表条目存储一个键/值对的链表，这些键/值对映射到该表条目）。另一种方法是使用第二个哈希函数重新哈希，并继续重新哈希直到找到一个空闲位置。链接是最常用的技术，因为它最容易实现并且具有最容易理解的特性。

哈希表的另一个缺点是哈希不保留键的顺序。这使得按顺序遍历哈希表中的项成为不可能。

作为一种索引方法，哈希的一个问题是，随着插入到表中的键的数量增加，冲突的数量也会增加。如果哈希表对于存储在其中的键的数量来说太小，那么冲突的数量将很高，并且查找条目的成本将显着增加（因为链只是一个链表）。一个大的哈希表减少了冲突的数量，但也增加了浪费的空间量（没有内容的表条目）。虽然可以更改哈希表的大小，但这代价很高，因为所有键/值对都需要重新哈希。调整哈希表大小的成本使其成为通用文件系统索引方法的一个非常困难的选择。

可扩展哈希是常规哈希的一种变体，它将哈希表分为两部分。在可扩展哈希中，有一个文件包含桶指针目录，还有一个包含数据的文件（桶）。可扩展哈希使用键的哈希值来索引桶指针目录。最初并非使用哈希值的所有位。当一个桶溢出时，解决方案是增加用作桶指针目录中索引的哈希值的位数。增加目录文件的大小是一个昂贵的操作。此外，使用两个文件使可扩展哈希在文件系统中的使用更加复杂。

文件系统中的索引不应不必要地浪费空间，并且应适应大小索引。很难提出一组可以满足所有这些标准、仍然保持足够的效率并且不需要冗长的重新哈希或重新索引操作的哈希例程。通过额外的工作，可扩展哈希可以成为文件系统 B 树的可行替代方案。

数据结构总结 (Data Structure Summary)

对于文件系统，在哈希表和 B 树之间进行选择很容易。哈希表存在的问题在使用作为文件系统一部分的通用索引方法时会带来重大困难。调整哈希表的大小可能会在调整表大小和重新哈希元素时长时间锁定整个文件系统，这对于一般使用来说是不可接受的。另一方面，当键很少时，B 树非常适合紧凑的大小，随着键的数量增加而轻松增长，并保持良好的搜索时间（尽管不如哈希表好）。BFS 对其所有索引都使用 B+ 树。

连接：索引与文件系统的其余部分 (Connections: Indexing and the Rest of the File System)

此时最明显的问题是：索引列表是如何维护的？以及各个索引位于何处？也就是说，索引在文件系统上存在的标准目录和文件集中处于什么位置？与属性一样，我们很想定义新的数据结构来维护这些信息，但没有必要。BFS 使用标准的目录结构来维护索引列表。BFS 将每个索引的数据存储在索引目录中的常规文件中。

尽管可以将索引文件放入具有特殊保护的用户可见目录中，但 BFS 却将索引列表存储在文件系统创建时创建的隐藏目录中。超级块存储索引目录的 i 节点号，这建立了与文件系统其余部分的连接。超级块是存储此类隐藏信息的便捷位置。将索引存储在隐藏目录中可以防止意外删除索引或其他可能导致文件系统灾难性情况的意外。将索引存储在隐藏目录中的缺点是需要一个专用的 API 才能访问。这是一个几乎没有或没有影响的可以双向选择的决定。

操作和访问索引的 API 很简单。操作整个索引的操作包括：

• create index
• delete index
• open index directory
• read index directory
• stat index

很容易扩展此操作列表以支持其他常见的文件操作（重命名等）。但是由于对索引的此类操作需求很少，因此 BFS 选择不提供该功能。

创建索引操作仅接受索引名称和索引的数据类型。索引名称将索引与将使用该索引的相应属性连接起来。例如，BeOS 邮件守护程序将其接收到的所有电子邮件消息添加一个名为 MAIL:from 的属性，并且它还创建一个名称为 MAIL:from 的索引。索引的数据类型应与属性的数据类型匹配。BFS 支持以下索引数据类型：

• 字符串 (最多 255 字节)
• 整数 (32 位)
• 整数 (64 位)
• 浮点数
• 双精度浮点数

当然也可能有其他类型，但这组数据类型涵盖了最通用的功能。实际上，几乎所有索引都是字符串索引。

创建索引时的一个“陷阱”是索引的名称可能与已经具有该属性的文件匹配。例如，如果一个文件有一个名为 Foo 的属性，并且一个程序创建了一个名为 Foo 的索引，那么已经具有该属性的文件不会添加到新创建的索引中。困难在于，如果没有遍历所有文件，就没有简单的方法来确定哪些文件具有该属性。由于创建索引是一个相对不常见的操作，因此遍历所有文件以查找那些已经具有该属性的文件可能是可以接受的。BFS 不这样做，而是将责任推给了应用程序开发人员。BFS 的这个缺陷是不幸的，但在开发计划中没有时间解决它。

删除索引是一个简单的操作。从索引目录中删除包含该索引的文件就是所有需要做的。虽然很简单，但删除索引应该是一个很少见的操作，因为重新创建索引不会重新索引所有具有该属性的文件。因此，只有当唯一使用它的应用程序从系统中删除并且索引为空（即，没有文件具有该属性）时，才应该删除索引。

其余的索引操作是简单的内务管理功能。索引目录函数（打开、读取和关闭）允许程序像遍历常规目录一样遍历索引目录。获取索引状态函数允许程序检查索引是否存在并获取有关索引大小的信息。由于所涉及的所有数据结构都与常规目录和文件的数据结构相同，因此这些例程都具有简单的实现。

自动索引 (Automatic Indices)

除了允许用户创建自己的索引外，BFS 还支持对基本文件属性（名称、大小和上次修改时间）的内置索引。文件系统本身必须创建和维护这些索引，因为它才是维护这些文件属性的实体。请记住，文件的名称、大小和上次修改时间不是常规属性；它们是 i 节点的组成部分，而不是由属性代码管理的。

名称索引保留整个系统上所有文件名的列表。每次文件名更改（创建、删除或重命名）时，文件系统还必须更新名称索引。在成功创建文件的所有其他信息（i 节点已分配且目录已更新）之后，才会将新文件名添加到名称索引中。然后将文件名添加到名称索引中。插入到名称索引必须作为文件创建事务的一部分进行，这样如果系统发生故障，整个操作将作为一个事务被撤销。虽然很少发生，但如果文件名无法添加到名称索引中（例如，没有剩余空间），则必须撤销整个文件创建操作。

删除文件名的问题稍微少一些，因为它不太可能失败（驱动器上不需要额外的空间）。但同样，从文件名索引中删除名称应该是最后完成的操作，并且应该作为删除文件的事务的一部分完成，以便整个操作是原子的。

重命名操作是实现起来最棘手的操作（通常以及对于索引的维护）。正如预期的那样，更新名称索引是作为重命名事务的一部分最后完成的操作。重命名操作本身分解为删除原始名称（如果存在）和将新名称插入索引。撤销插入新名称失败的情况尤其成问题。如果新名称已经存在（这是重命名成为原子操作所必需的），则重命名操作可能已经删除了一个文件。然而，由于另一个文件被删除（并且其资源被释放），撤销这样的操作极其复杂。由于所涉及的复杂性以及事件发生的可能性很小，BFS 不尝试处理这种情况。如果重命名操作无法将文件的新名称插入到名称索引中，文件系统仍然是一致的，只是不是最新的（并且磁盘很可能也已 100% 满）。

当文件大小更改时，大小索引会更新。作为一种优化，文件系统仅在文件关闭时更新大小索引。这可以防止文件系统必须为对任何文件的每次写入都锁定和修改全局大小索引。缺点是，对于某些正在积极写入的文件，大小索引可能略微过时。在略微过时与每次写入都更新大小索引之间的权衡是值得的——性能损失相当大。

大小索引可能成为严重瓶颈的另一种情况是存在许多大小相同的文件时。这似乎是一种不寻常的情况，但在运行创建和删除大量文件以测试文件系统速度的文件系统基准测试时，这种情况却出奇地频繁发生。拥有许多大小相同的文件会给索引结构及其处理重复键的方式带来压力。BFS 在这方面表现尚可，但随着重复数量的增加，性能会非线性地下降。目前，超过 10,000 个左右的重复会导致对大小索引的修改性能明显滞后。

上次修改时间索引是 BFS 索引的最后一个固有文件属性。索引上次修改时间使用户可以轻松找到最近创建的文件或不再需要的旧文件。正如预期的那样，上次修改时间索引在文件关闭时接收更新。更新包括删除旧的上次修改时间并插入新的时间。

了解到诸如上次修改时间索引之类的固有索引对于系统性能至关重要，BFS 使用了一种稍微不正当的技术来提高索引的效率。由于上次修改时间只有 1 秒的粒度，并且可能在 1 秒内创建数百个文件，因此 BFS 将标准的 32 位时间变量扩展到 64 位，并添加了一个小的随机分量以减少潜在的重复数量。在进行比较或在用户之间传递信息时，会屏蔽掉随机分量。回想起来，可以使用 64 位微秒分辨率的计时器并对时间值进行类似的屏蔽，但是由于 POSIX API 仅支持 1 秒分辨率的 32 位时间值，因此没有太多意义定义一组新的并行 API 仅用于访问更大的时间值。

除了这三个固有的文件属性外，还有其他属性也可以被索引。早期版本的 BFS 实际上索引了文件的创建时间，但我们认为这个索引不值得它带来的性能损失。通过消除创建时间索引，文件系统在文件创建和删除基准测试中获得了大约 20% 的速度提升。权衡是无法使用索引按创建时间搜索文件，但我们认为这并没有造成太大的损失。类似地，可以索引文件访问权限、所有权信息等等，但我们选择不这样做，因为维护索引的成本超过了它们将提供的收益。具有不同约束的其他文件系统可能会做出不同的选择。

其他属性索引 (Other Attribute Indices)

除了名称、大小和上次修改时间这些固有的索引之外，还可以有任意数量的其他索引。这些索引中的每一个都对应于程序随文件存储的属性。如前所述，BeOS 邮件系统将收到的电子邮件存储在单独的文件中，并使用诸如邮件来自谁、发往谁、发送时间、主题等等属性标记每个文件。首次运行时，邮件系统会为其写入的每个属性创建索引。当邮件守护程序将这些属性之一写入文件时，文件系统会注意到该属性名称具有相应的索引，因此会同时更新索引和包含属性值的文件。

对于每次写入属性的操作，文件系统还必须在索引目录中查找属性名称是否与索引名称相同。虽然这看起来会降低系统速度，但索引的数量往往很少（通常少于 100 个），并且查找属性的成本很低，因为数据几乎总是被缓存的。写入属性时，文件系统还会检查该文件是否已经具有该属性。如果是，则必须首先从索引中删除旧值。然后，文件系统可以将新值添加到文件中，并将该值插入到相应的属性索引中。所有这些操作对用户程序都是透明的。

当用户程序从文件中删除属性时，会发生类似的一系列操作。文件系统必须检查要删除的属性名称是否具有索引。如果有，则必须从索引中删除属性值，然后从文件中删除该属性。

索引的维护使属性处理变得复杂，但这是必要的。索引的自动管理使程序不必处理这个问题，并向程序保证，如果存在属性索引，文件系统将使其与创建索引后写入的所有属性的状态保持一致。

BFS B+树 (BFS B+trees)

BFS 使用 B+ 树来存储目录的内容和所有索引信息。BFS B+ 树的实现是第一版 Folk 和 Zoellick 文件结构教科书中描述的 B+ 树的宽松派生，并且很大程度上借鉴了 Marcus J. Ranum 对该数据结构的公共实现。B+ 树代码支持存储可变大小的键以及单个磁盘偏移量（在 BFS 中是 64 位的值）。存储在树中的键可以是字符串、整数（32 位和 64 位）、浮点数或双精度浮点数。与原始数据结构的最大不同之处在于增加了对在 B+ 树中存储重复键的支持。

API

B+树的接口也相当简单。API 有六个主要函数：

• 打开/创建 B+树
• 插入键/值对
• 删除键/值对
• 查找键并返回其值
• 转到树的开头/结尾
• 遍历树的叶节点（向前/向后）

创建 B+ 树的函数有几个参数，可以指定 B+ 树的节点大小、存储在树中的数据类型以及各种其他内务管理信息。B+ 树的节点大小的选择很重要。无论文件系统的块大小如何，BFS 都使用 1024 字节的节点大小。确定节点大小是一个简单的实验和实用性问题。BFS 支持长度高达 255 个字符的文件名，这使得 512 字节的 B+ 树节点大小太小。较大的 B+ 树往往会浪费空间，因为每个节点永远不会 100% 满。对于小型目录来说，这尤其是一个问题。选择 1024 字节的大小是一个合理的折衷方案。

插入例程接受一个键（其类型应与 B+ 树的数据类型匹配）、键的长度和一个值。该值是一个 64 位的 i 节点号，用于标识哪个文件对应于存储在树中的键。如果该键是现有键的重复项，并且树不允许重复项，则返回错误。如果树支持重复项，则插入新值。在重复项的情况下，该值用作辅助键并且必须是唯一的（两次插入相同的键/值对被认为是错误的）。

删除例程接受一个键/值对作为输入，并将搜索树中是否存在该键。如果找到该键并且它不是重复项，则从树中删除该键及其值。如果找到该键并且它有重复的条目，则在重复项中搜索传入的值并删除该值。

最基本的操作是在 B+ 树中搜索键。查找操作接受一个输入键并返回关联的值。如果该键包含重复的条目，则返回第一个。

其余函数支持树的遍历，以便程序可以遍历树中的所有条目。可以向前或向后遍历树。也就是说，向前遍历返回所有按升序字母或数字顺序排列的条目。向后遍历树返回所有按降序排列的条目。

数据结构 (The Data Structure)

B+ 树 API 的简洁性掩盖了底层数据结构的复杂性。在磁盘上，B+ 树是节点的集合。所有 B+ 树的第一个节点都是一个头节点，其中包含描述 B+ 树其余部分的简单数据结构。本质上，它是 B+ 树的超级块。

long magic;
int node_size;
int max_number_of_levels;
int data_type;
off_t root_node_pointer;
off_t free_node_pointer;
off_t maximum_size;

magic 字段只是一个标识块的魔数。像这样存储魔数有助于在发生损坏时重建文件系统。下一个字段 node_size 是树的节点大小。树中的每个节点的大小始终相同（包括 B+ 树头节点）。下一个字段 max_number_of_levels 指示 B+ 树的深度。树的这个深度是各种内存数据结构所需要的。data_type 字段编码存储在树中的数据类型（可以是 32 位整数、64 位整数、浮点数、双精度浮点数或字符串）。

root_node_pointer 字段是最重要的字段。它包含 B+ 树文件中树的根节点的偏移量。没有根节点的地址，就无法使用该树。必须始终读取根节点才能对树执行任何操作。根节点指针与所有磁盘偏移量一样，是一个 64 位的值。

free_node_pointer 字段包含树中第一个空闲节点的地址。当删除操作导致整个节点变为空时，该节点将链接到一个从文件中的此偏移量开始的列表中。空闲节点列表通过将空闲节点链接在一起进行维护。存储在每个空闲节点中的链接只是下一个空闲节点的地址（最后一个空闲节点的链接地址为 1）。

最后一个字段 maximum_size 记录 B+ 树文件的最大大小，并用于错误检查节点地址请求。当请求一个新节点但没有空闲节点时，也会使用 maximum_size 字段。在这种情况下，只需通过写入文件末尾来扩展 B+ 树文件。新节点的地址是 maximum_size 的值。然后，maximum_size 字段将增加 node_size 变量中包含的量。

B+ 树中内部节点和叶节点的结构相同。有一个简短的头部，后跟打包的键数据、键的长度，最后是与每个键关联的值。头部足以区分叶节点和内部节点，并且与所有 B+ 树一样，只有叶节点包含用户数据。节点的结构如下：

off_t left link;
off_t right link;
off_t overflow link;
short count of keys in the node;
short length of all the keys;
key data;
short key length index;
off_t array of the value for each key;

left_link 和 right_link 用于叶节点将它们链接在一起，以便易于对树进行有序遍历。overflow_link 用于内部节点，并指向有效地延续该节点的另一个节点。count_of_keys_in_node 简单地记录此节点中存在的键数。length_of_all_the_keys 被添加到头部大小，然后向上舍入到 4 的倍数，以得到键长度索引的开头。key_length_index 中的每个条目存储键的结束偏移量（要计算节点中的字节位置，还必须加上头部大小）。也就是说，索引中的第一个条目包含第一个键的结束偏移量。可以通过减去前一个条目的长度来计算键的长度（第一个元素的长度只是索引中的值）。长度索引之后是键值数组（与键一起存储的值）。对于内部节点，与键关联的值是指向包含小于此键的元素的相应节点的偏移量。对于叶节点，与键关联的值是用户传递的值。

重复项 (Duplicates)

除了树的内部节点和叶节点之外，还有存储键的重复项的节点。出于效率原因，重复项的处理相当复杂。BFS 使用的 B+ 树中有两种类型的重复节点：重复片段节点和完整重复节点。重复片段节点包含几个不同键的重复项。完整重复节点仅存储一个键的重复项。

片段节点类型之间的区别在于，一个键的少量重复项比大量重复项更常见。也就是说，如果几个不同的目录中有几个同名文件，则重复名称的数量很可能少于八个。事实上，对各种系统的简单测试表明，高达 35% 的文件名是重复的，并且重复项不超过八个。有效地处理这种情况非常重要。早期版本的 BFS B+ 树没有使用重复片段，我们发现在复制目录层次结构时，所有 I/O 的很大一部分都用于处理名称和大小索引中的重复项。通过添加对重复片段的支持，我们能够显着减少发生的 I/O 量，并将复制文件夹的时间加快了近一倍。

当必须将重复条目插入叶节点时，系统不会存储用户的值，而是存储一个特殊值，该值是指向片段节点或完整重复节点的指针。该值是特殊的，因为它设置了其高位。BFS B+ 树代码保留了值字段的最高 2 位来指示一个值是否引用重复项。一般来说，这是不可接受的，但由于文件系统仅在值字段中存储 i 节点号，我们可以确保这不会成为问题。尽管这种态度在系统扩展时通常会导致各种麻烦，但在这种情况下我们没有负罪感。这种方法的安全性源于 i 节点号是磁盘块地址，因此它们至少比原始磁盘字节地址小 10 位（因为 BFS 中的最小块大小为 1024 字节）。由于 BeOS 中的最大磁盘大小为 2^64 字节，而 BFS 使用至少 1024 字节的块，因此最大 i 节点号为 2^54。值 2^54 足够小，不会干扰 B+ 树代码使用的最高 2 位。

当将重复键插入 B+ 树时，文件系统会查看当前叶节点中的任何其他键是否已具有重复片段。如果存在有空间容纳另一个片段的重复片段节点，我们将重复值插入到该节点中的新片段中。如果当前节点中没有引用其他重复片段节点，我们创建一个新的重复片段节点并将重复值插入其中。如果我们正在添加的键已经有重复项，我们将重复项插入到片段中。如果片段已满（它只能容纳八个条目），我们分配一个完整的重复节点并将现有的重复项复制到新节点中。完整重复节点包含比片段更多的重复项空间，但仍然可能有更多的重复项。为了管理任意数量的重复项，完整重复节点包含指向附加完整重复页面的链接（向前和向后）。重复项列表根据与键关联的值（即，包含此键值作为属性的文件的 i 节点号）按排序顺序保存。当重复项超过 10,000 个左右时，访问此重复项的线性列表可能会变得非常缓慢。不幸的是，在 BFS 的开发过程中，没有时间探索更好的解决方案（例如，存储另一个以 i 节点值为键的 B+ 树）。

集成 (Integration)

从抽象的角度来看，我们描述的结构与文件系统的其余部分没有联系；也就是说，它存在，但尚不清楚它如何与文件系统的其余部分集成。BFS 的基本抽象是存储数据的 i 节点。一切都建立在这个最基本的抽象之上。BFS 用于存储目录和索引的 B+ 树基于 i 节点之上。也就是说，i 节点管理分配给 B+ 树的磁盘空间，而 B+ 树将该磁盘空间的内容组织成系统其余部分用于查找信息的索引。

B+ 树使用两个例程 read data stream() 和 write data stream() 来访问文件数据。这些例程直接操作 i 节点，并提供对 BFS 中文件数据的最低级别访问。尽管它们是低级别的，但 read/write data stream() 具有与大多数程序员熟悉的更高级别的 read() 和 write() 调用非常相似的 API。在这个低级别的 I/O 之上，B+ 树代码实现了前面讨论的功能。文件系统的其余部分围绕 B+ 树功能进行封装，并使用它来提供目录和索引抽象。例如，创建新目录涉及创建一个文件并将一个空的 B+ 树放入该文件中。当程序需要枚举目录的内容时，文件系统会请求对 B+ 树进行有序遍历。打开目录中包含的文件是对 B+ 树的查找操作。查找操作返回的值（如果成功）是命名文件的 i 节点（而 i 节点又用于访问文件数据）。创建文件会将新的名称/i 节点对插入到 B+ 树中。同样，删除文件只是从 B+ 树中删除一个名称/i 节点对。索引以与目录大致相同的方式使用 B+ 树，但允许目录不允许的重复项。

5.3 查询 (Queries)

如果文件系统对索引所做的只是维护它们，那么它们将毫无用处。文件系统费心管理索引的原因是，程序可以发出使用索引来高效获取结果的查询。与检查文件系统中每个文件的蛮力替代方案相比，使用索引可以大大加快搜索速度。

在 BFS 中，查询只是一个包含关于文件属性的表达式的字符串。对于任何给定的文件，该表达式的计算结果为真或假。如果表达式对于某个文件为真，则该文件位于查询结果中。例如，查询

name == "main.c"

仅对名称完全为 main.c 的文件求值为真。文件系统将通过搜索名称索引来查找匹配的文件来评估此查询。对于这种类型的查询，使用名称索引非常高效，因为它是对名称索引 B+ 树的 log(N) 搜索，而不是对所有文件的线性搜索。速度上的差异取决于文件系统上的文件数量，但即使对于一个包含 5000 个文件的小型系统，使用索引的搜索时间也比单独迭代文件快几个数量级。查询的结果是匹配的文件列表。查询 API 遵循 POSIX 目录迭代函数 API。有三个例程：打开查询、读取查询和关闭查询。

open query 例程接受一个表示查询的字符串和一个标志参数，该参数允许任何特殊选项（例如实时查询，我们将在本节稍后讨论）。接下来我们将讨论查询字符串的格式。read query 例程被重复调用；每次它返回下一个匹配查询的文件，直到没有更多匹配的文件为止。当没有更多匹配的文件时，read query 例程返回一个查询结束指示符。close query 例程释放与查询关联的任何资源和状态。

这个简单的 API 隐藏了与处理查询相关的许多复杂性。查询处理是 BFS 中最大的代码块。解析查询、迭代解析树以及决定哪些文件匹配查询需要相当多的代码。现在我们将注意力转向该代码的细节。

查询语言 (Query Language)

BFS 支持的查询语言简单明了，并且非常“C 风格”。虽然可以使用更传统的数据库查询语言（如 SQL），但这似乎不值得付出努力。由于 BFS 不是真正的数据库，因此我们将很难将 SQL 的语义与文件系统的功能相匹配。BFS 查询语言由使用逻辑 AND 或逻辑 OR 连接词连接的简单表达式构成。简单表达式的语法是：

<属性名称> [逻辑运算符] <值>

属性名称 是一个简单的文本字符串，对应于属性的名称。MAIL:from、PERSON:email、name 或 size 都是有效的属性名称的示例。表达式中至少一个属性名称必须对应于具有相同名称的索引。

表达式的 逻辑运算符 部分是以下运算符之一：

= (等于)
!= (不等于)
< (小于)
> (大于)
>= (大于或等于)
<= (小于或等于)

表达式的 值 是一个字符串。如果属性的数据类型是数字，则该字符串可以解释为数字。如果值字段是字符串类型，则该值可以是正则表达式（以允许通配符匹配）。这些简单表达式可以使用逻辑 AND (&&) 或逻辑 OR (||) 连接词进行分组。也可以使用括号对简单表达式进行分组，并覆盖 AND 优先于 OR 的正常优先级。最后，可以通过在整个表达式前加上 ! 运算符来应用逻辑 NOT。运算符的优先级与 C 编程语言中的优先级相同。

查看一些示例查询有助于更好地理解格式。我们将考虑的第一个查询是：

name == "*.c" && size > 20000

此查询要求查找所有名称为 *.c（即，以字符 .c 结尾）且大小大于 20,000 字节的文件。查询

(name == "*.c" || name == "*.h") && size > 20000

将查找所有名称以 .c 或 .h 结尾且大小大于 20,000 字节的文件。括号将 OR 表达式分组，以便 AND 连接词 (size > 20000) 应用于 OR 表达式的两半。最后一个示例演示了一个相当复杂的查询：

(last_modified < 81793939 && size > 5000000) || (name == "*.backup" && last_modified < 81793939)

此查询要求查找所有上次修改日期在特定日期之前且大小大于 500 万字节的文件，或者所有名称以 .backup 结尾且上次修改日期在特定日期之前的文件。日期表示自 1970 年 1 月 1 日以来的秒数（即，它采用 POSIX ctime 格式）。此查询将查找最近未修改的大型文件以及最近未修改的备份文件。当尝试释放完整卷上的磁盘空间时，这样的查询对于查找要删除或移动到磁带存储的候选文件非常有用。

BFS 支持的查询语言足够丰富，可以表达几乎任何关于文件集的查询，但又足够简单，易于阅读和解析。

解析查询 (Parsing Queries)

BFS 的 open query 例程的工作是解析查询字符串（这也决定了它是否有效）并构建一个表示查询的解析树。解析是通过一个简单的递归下降解析器（手写）完成的，该解析器在解析查询时生成树。如果在任何时候解析器检测到查询字符串中的错误，它会将错误向上冒泡到顶层并向用户返回错误。如果解析成功，则生成的查询树将作为与 open query 例程返回的对象关联的状态的一部分保存。

表示查询的解析树以维护整个查询状态的顶层节点开始。从该节点，指针延伸到表示 AND 和 OR 连接词的节点。树的叶子是简单的表达式，这些表达式评估特定属性上的一个值。树的叶子驱动查询的评估。

解析查询后，文件系统必须决定如何评估查询。决定解析树的评估策略使用启发式方法遍历树并找到用于开始评估的最佳叶节点。BFS 使用的启发式方法（像往常一样）可以进行一些改进。从根节点开始，BFS 尝试通过选择将导致最少匹配数的路径向下遍历到叶节点。例如，在查询

name == "*.c" && size > 20000

中有两个节点，一个表示左半部分 (name == "*.c")，另一个表示右半部分 (size > 20000)。在选择这两个表达式时，右半部分是一个“更严格”的表达式，因为它比左半部分更容易评估。查询的左半部分更难评估，因为它涉及正则表达式。由于 B+ 树是为精确匹配而组织的，因此使用正则表达式使得无法利用名称索引的任何快速搜索。另一方面，查询的右半部分 (size > 20000) 可以利用 B+ 树找到第一个大小为 20,000 字节的节点，然后按顺序迭代树中其余的项（大于值 20,000 的项）。

评估策略还查看索引的大小以帮助其做出决定。如果一个索引的大小明显小于另一个索引，那么迭代较小的索引更有意义，因为它固有地比更大的索引具有更少的条目。控制此评估的逻辑相当复杂。然而，这种复杂性是值得的，因为选择树中的最佳路径可以显着节省评估查询所需的时间。

读取查询——真正的工作（Read Query—The Real Work）

open query 例程创建解析树并选择一个初始叶节点（即查询片段）开始评估。查找哪些文件匹配查询的真正工作由 read query 例程完成。read query 例程从 open query 例程选择的第一个叶节点开始迭代。检查叶节点时，读取例程调用知道如何迭代给定数据类型的索引并查找与叶节点表达式匹配的文件的函数。

由于查询语言支持不同类型的逻辑运算，因此迭代索引变得复杂。对 B+ 树的小于或等于比较与小于比较略有不同，并且与大于查询相反。逻辑比较的数量（六个）和文件系统支持的数据类型数量（五个）产生了大量相似但略有不同的代码。

迭代所有匹配特定查询片段的值（例如，像 size < 500 这样的简单表达式）的过程首先在与查询片段关联的索引中找到第一个匹配的项。对于像 size < 500 这样的表达式，迭代例程首先找到值 500，然后向后遍历索引 B+ 树的叶子项以找到第一个小于 500 的值。如果遍历到达树的开头，则没有小于 500 的项，并且迭代器返回一个错误，指示此查询片段中没有更多条目。对一个查询片段的所有匹配项的迭代很复杂，因为每次迭代只返回一个项。这需要在调用之间保存状态以便能够重新开始搜索。

一旦为给定的查询片段找到匹配的文件，查询引擎必须向上遍历解析树以查看该文件是否匹配查询的其余部分。如果所讨论的查询是 name == *.c && size > 35000，则生成的解析树如图 5-5 所示。

查询引擎首先会向下遍历解析树的右半部分，因为评估 size > 35000 查询片段的成本远低于 name = *.c 一半。对于每个匹配表达式 size > 35000 的文件，查询引擎还必须确定它是否匹配表达式 name = *.c。确定文件是否匹配解析树的其余部分不使用其他索引。评估只是通过从文件中读取必要的属性，直接对特定文件执行每个查询片段中指定的比较。

不等于 (!=) 比较运算符给查询迭代器带来了一个有趣的难题。“不等于”的含义通常没有讨论的余地：要么某个特定值不等于另一个值，要么等于。然而，在查询的上下文中，其含义变得不太清楚。

考虑以下查询：

MAIL:status == New && MAIL:reply_to != mailinglist@noisy.com

这是一个典型的过滤器查询，用于仅显示所有非来自邮件列表的电子邮件。问题是并非所有常规电子邮件消息在消息中都有 Reply-To: 字段，因此不会有 MAIL:reply to 属性。即使电子邮件消息没有 Reply-To: 字段，它仍然应该匹配查询。BFS 的原始版本要求文件必须存在该属性才能匹配，这导致了此类电子邮件过滤器出现不希望的行为。

为了更好地支持这种查询风格，BFS 更改了其对不等于比较的解释。现在，如果 BFS 遇到不等于比较，并且所讨论的文件没有该属性，则该文件仍然被认为是匹配的。当不等于比较是唯一的查询片段时，这种行为的改变使处理不等于查询变得复杂。现在，具有单个查询片段且该片段具有不等于比较运算符的查询必须遍历所有文件，并且无法使用任何索引来加快搜索速度。所有没有该属性的文件都将匹配查询，而那些具有该属性的文件只有在该属性的值不等于查询片段中的值时才会匹配。尽管遍历所有文件非常缓慢，但为了查询引擎的一致性，这是必要的。

字符串查询和正则表达式匹配 (String Queries and Regular Expression Matching)

默认情况下，BFS 中的字符串匹配是区分大小写的。这使得利用同样区分大小写的 B+ 树搜索例程变得容易。搜索精确字符串的查询非常快，因为这正是 B+ 树的设计目标。遗憾的是，从人机界面角度来看，必须记住确切的文件名（包括所有字母的大小写）是不可接受的。为了允许更灵活的搜索，BFS 支持使用正则表达式的字符串查询。

BFS 支持的正则表达式匹配很简单。正则表达式比较函数支持：

• — 匹配任意数量的字符（包括零个）
• ? — 匹配任意单个字符
• [...] — 匹配 [] 中的字符范围/类
• [^...] — 匹配不在 [] 中的字符范围/类

字符类表达式允许匹配特定的字符范围。例如，所有小写字母将指定为 [a-z]。否定范围表达式 [^] 允许匹配除该范围/类字符之外的所有内容。例如，[^0-9] 匹配所有非数字字符。

Tracker（BeOS 的 GUI 文件浏览器）发出的典型查询是不区分大小写的子字符串查询。也就是说，使用 Tracker 的查找面板搜索名称“slow”会转换为以下查询：

name = "*[sS][lL][oO][wW]*"

这样的查询必须遍历名称索引的所有叶子节点，并对名称索引中的每个名称执行正则表达式比较。不幸的是，这消除了 B+ 树的任何优势，并且比执行普通的 B+ 树搜索慢得多。然而，这是最终用户所期望的，这比使用优雅的 B+ 树搜索算法更重要。

读取查询的附加职责 (Additional Duties for Read Query)

read query 例程还维护额外的状态，因为它被重复调用以返回结果。read query 例程必须能够在每次调用时重新开始迭代查询。这需要保存查询树中评估的位置以及查询正在迭代的 B+ 树中的位置。

一旦特定的叶节点耗尽了该索引中的所有文件，read query 例程就会备份解析树，以查看是否必须下降到另一个叶节点。在以下查询中：

name == Query.txt || name == Indexing.txt

解析树将有两个叶子，如图 5-6 所示。

read query 例程将迭代查询的左半部分，当左半部分耗尽所有匹配项（很可能只有一个文件）时，read query 将备份到 OR 节点并下降到树的右半部分。当树的右半部分耗尽所有匹配项时，查询完成，read query 返回其查询结束指示符。

一旦查询引擎确定某个文件与查询匹配，就必须将其返回给调用 read query 例程的程序。查询引擎的文件匹配结果是一个 i 节点（回想一下，索引只在索引中存储文件的 i 节点号）。将查询结果转换为适合用户程序的某种内容的过程需要文件系统将 i 节点转换为文件名。通常这是不可能的，但 BFS 将文件名（不是完整路径，只是名称）作为文件的属性存储。此外，BFS 在文件 i 节点中存储一个指向包含该文件的目录的链接。这使我们能够将 i 节点地址转换为文件的完整路径。将文件名存储在文件 i 节点中非常不寻常，但 BFS 明确地这样做是为了支持查询。

实时查询 (Live Queries)

实时查询是围绕 BFS 查询引擎构建的另一个特性。实时查询是一个持久查询，它监视所有文件操作并报告匹配文件集的添加和删除。也就是说，如果我们发出以下实时查询：

name = *.c

文件系统将首先向我们返回所有名称以 .c 结尾的现有文件。查询的实时方面意味着当创建任何与查询匹配的新文件，或者删除或重命名任何与查询匹配的现有文件时，文件系统将继续通知我们。一个更有用的实时查询示例是监视新电子邮件的查询。具有谓词 MAIL:status = New 的实时查询将监视新收到的电子邮件，而不需要轮询。系统管理员可能希望发出实时查询 size > 50000000 来监视增长过大的文件。实时查询减少了系统中的不必要轮询，并且不像轮询那样滞后于实际事件。

为了支持此功能，文件系统会在解析查询时标记它遇到的所有索引。与每个索引关联的标签是指向查询的原始解析树的链接。每次文件系统修改索引时，它还会遍历对索引修改感兴趣的实时查询列表，并针对每个查询检查新文件是否与查询匹配。虽然这听起来非常简单，但存在许多细微的锁定问题需要正确处理，才能从索引遍历到解析树，然后再返回。

5.4 总结 (Summary)

这个冗长的章节涉及了与 Be 文件系统中的索引相关的众多主题。我们看到索引提供了一种高效访问具有特定属性的所有文件的机制。索引的名称对应于属性名称。每当写入属性且其名称与索引匹配时，文件系统也会更新该索引。属性索引以写入属性的值为键，文件的 i 节点地址与该值一起存储。存储包含该属性的文件的 i 节点地址允许文件系统从索引中的条目映射到原始文件。

文件系统维护三个文件固有的索引（名称、大小和上次修改时间）。这些索引需要稍微特殊的处理，因为它们与用户程序添加的属性在同一意义上不是真正的属性。对于添加到文件的其他属性，索引可能存在也可能不存在。

我们讨论了几种索引数据结构的可选方法：B 树、它们的变体和哈希表。B 树优于哈希表，因为 B 树更具可扩展性，并且 B 树上没有像调整哈希表大小那样意外的昂贵操作。

然后，本章讨论了 BFS 实现的 B+ 树的细节、它们在磁盘上的布局以及它们如何处理重复项。我们观察到，BFS 中重复项的管理是足够的，尽管可能没有我们希望的那样高性能。然后，我们简要介绍了 BFS 中的 B+ 树如何连接到文件系统的其余部分。

最后一节讨论了查询，涵盖了什么是查询、一些解析问题、查询如何迭代索引以生成结果以及结果的处理方式。讨论还涵盖了实时查询以及当创建新文件或删除旧文件时，它们如何设法向查询发送更新。

本章的实质内容——属性、索引和查询——是 BFS 有趣的本质原因。在 BeOS 中广泛使用这些特性在其他系统中是看不到的。