索引结构

数据库管理器使用 B+ 树结构来存储索引。

B + 树具有多个级别，如 图 1中所示; rid 是指记录标识 (RID)。

顶层称为根节点。 底层由叶节点组成，这些节点存储索引键值，并通过指针指向包含相应数据的表行。 根节点层与叶节点层之间的那些层称为中间节点。

当索引管理器查找特定的索引键值时，它从根节点开始搜索索引树。 根节点对于下一层中的每个（中间）节点都包含一个键。 每个键的值都是下一层的相应节点的最大现有键值。 例如，假定索引包含三层（如上图所示）。 为了查找特定的索引键值，索引管理器将搜索根节点，以查找第一个大于或等于搜索键值的键值。 根节点键指向特定的中间节点。 索引管理器将按照此过程遍历每个中间节点，直到找到包含所需索引键的叶节点为止。

假设在 图 1 中查找的键是 I。 根节点中大于或等于 I 的第一个键是 N，它指向下一级别的中间节点。 该中间节点中大于或等于 I 的第一个键是 L，它反过来指向一个特定的叶节点，在该叶节点上可以找到 I 的索引键及其对应的 RID。 RID 标识基本表中相应的行。

叶节点层也可以包含指向上一层叶节点的指针。 这些指针使索引管理器能够在找到范围内的某个值之后按任一方向扫描叶节点以检索某个范围内的值。 只有在创建索引时指定了 ALLOW REVERSE SCANS 选项的情况下，才可能有按任一方向执行扫描的能力。

对于多维集群 (MDC) 表或插入时间集群 (ITC) 表而言，将为您对表指定的每个集群维自动创建块索引。 还将创建一个组合块索引；此索引包含每一列中涉及任何表维的键部分。 这种索引包含指向块标识 (BID) 而不是 RID 的指针，并有助于改进数据访问。

为索引的叶子页中每个 RID 存储的单字节 ridFlag 用于将该 RID 标记为“已被以逻辑方式删除”，以便稍后以物理方式将其移除。 在落实更新或删除操作之后，可以将已标记为“已删除”的键移除。 对于索引中的每个可变长度列，将有另外两个字节存储列值的实际长度。