索引

索引基础

索引文件

主文件保存完整记录，索引文件保存关键码与记录位置之间的联系。索引项通常写成 (key, pointer)，指针可能指向一条记录、一个数据块，或更低一级的索引块。

索引比主文件窄得多。假设一条完整记录占 256 字节，而键与指针合计 16 字节，同一磁盘页中能装入的索引项数量约为记录数量的十六倍。查询先在小而密集的索引中缩小范围，再读取对应的数据页。

一份主文件可以按不同字段建立多份索引。索引不会改变记录本身，只增加新的访问路径；代价是插入、删除或修改字段时，相应索引也要同步更新。

线性索引项通过关键码指针定位主文件中的记录

主码与辅码

主码能唯一标识记录，例如学号或订单编号。主码索引中的一个键只对应一条记录位置。

辅码允许重复，例如院系、城市或状态。辅码索引中的一个键要对应多条记录，常见表示是让索引项指向一条位置表。

1
计算机学院 -> [record 3, record 18, record 29, ...]

位置表本身也可能很长，需要分块、压缩或继续建立索引。正文倒排索引中的倒排表就是这种结构。

稠密与稀疏

稠密索引为每条记录建立索引项。主文件可以无序，因为索引项直接给出目标位置。索引体积较大，新增记录也要插入一条索引项。

稀疏索引只为一组连续记录建立一项，通常保存该组的首键或最大键以及数据块地址。定位到块后，还要在块内继续检索。它要求主文件按索引键有序，否则同一键范围可能散落在任意块中。

三个数据块保存的键为

1
2
3
block 0:  3  7  11  18
block 1: 24 29  35  41
block 2: 48 53  60  72

以首键建立稀疏索引时，只需保存 (3, block 0)、(24, block 1) 和 (48, block 2)。查询 35 时，找到不大于它的最大索引键 24，再在 block 1 内检索。

数据块分裂或边界键变化时，稀疏索引仍要调整，只是更新频率和占用空间都低于稠密索引。

多级线性索引

有序索引可以二分检索，但索引大到无法常驻内存时，每次比较可能读取一个不同磁盘块。为一级索引的每个块再建立一条稀疏索引项，就得到二级索引；最高层仍装不下时可以继续向上建立。

假设磁盘块为 1024 字节，每个 (key, pointer) 占 8 字节，一块能放 128 条索引项。一级稠密索引若有 10000 项，需要

$$ \left\lceil\frac{10000}{128}\right\rceil=79 $$

个块。二级索引只需为这 79 个块各存一项，能够完整放入一个块。

二级线性索引先定位一级索引块，再进入对应磁盘块

查询过程分三步：

读入二级索引块，确定目标应落在哪个一级索引块。
读入该一级索引块，确定具体数据块或记录位置。
读入目标数据块。

索引项内部比较发生在内存中，成本远低于额外读取一页。多级索引的高度由页面分支数决定，通常远低于二叉索引的高度。

静态索引与 ISAM

静态索引在文件初次装载或整体重组时建立，日常操作不改变主要层次和块边界。它适合批量写入后长期查询的数据。

索引顺序存取方法（Indexed Sequential Access Method，ISAM）在有序主文件上建立固定的多级索引。早期磁盘结构可按主索引、柱面索引和磁道索引逐级定位；现代实现虽然不再依赖相同物理术语，仍保留逐层缩小范围的结构。

ISAM 由主索引、柱面索引和磁道索引逐级定位记录

静态结构的查询路径稳定，索引页可以紧凑排布。插入记录时却不能随意移动后方全部数据，通常会把新记录放入溢出区，并从原数据块链接过去。

溢出记录不断增加后，一个逻辑块可能拖着很长的溢出链，查询和顺序扫描都会变慢。ISAM 需要定期重组主文件，把溢出记录重新并入有序块；动态 B+ 树可以通过分裂与合并就地调整索引。

倒排索引

普通记录从文档映射到属性，倒排索引则从属性值映射到文档集合。对于教师记录，可以从职称映射到教师编号；对于正文，可以从词项映射到包含它的文档编号。

正文索引通常包含两层：

词典保存所有不同词项，并给出对应倒排表位置。
倒排表保存文档编号，还可附带词频和词在文档中的位置。

建立索引时，先把文档分词并规范化，再生成 (term, document, position) 记录。大批记录按词项排序后，相同词项连续出现，可以一次扫描形成倒排表。

正文中的词项被整理为文档编号与位置组成的倒排表

1
algorithm -> [(2, [5, 18]), (7, [3]), (11, [9, 21])]

这条表表示词项 algorithm 出现在文档 2、7 和 11 中，方括号保存它在各文档里的位置。只保留文档编号能做布尔检索；加入位置后才能判断短语和邻近关系。

倒排表运算

倒排表按文档编号递增排列。查询 tree AND index 时，用两个指针求两条表的交集。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
std::vector<int> intersect(
    const std::vector<int>& left,
    const std::vector<int>& right) {
    std::vector<int> result;
    int i = 0;
    int j = 0;

    while (i < static_cast<int>(left.size()) &&
           j < static_cast<int>(right.size())) {
        if (left[i] == right[j]) {
            result.push_back(left[i]);
            ++i;
            ++j;
        } else if (left[i] < right[j]) {
            ++i;
        } else {
            ++j;
        }
    }
    return result;
}

时间与两条表长度之和成正比。多个词项求交时，先处理最短倒排表，通常能更早缩小候选集合。长度差异很大时，短表中的每个编号也可以在长表中跳跃或二分定位。

文档编号常保存相邻差值。递增编号 120, 125, 141, 142 可以写成 120, 5, 16, 1，小差值再使用变长整数编码，能显著减少倒排文件体积。

文档不断加入时，直接修改大型有序倒排表代价很高。搜索系统通常先建立小型增量索引，再定期把多个索引段归并；删除则可记录删除位图，合并时再清理旧项。

动态索引

动态索引允许记录插入和删除后立即保持可检索状态。索引结点与数据块都有容量上下限；装满后分裂，过空时借位或合并。B 树与 B+ 树通过局部调整维持所有叶结点同层，不需要周期性重建整棵索引。

外存索引的结点大小通常贴合一页。一个结点中的键很多，页内可以顺序或二分查找；树高很小，主要代价是从根到叶读了多少页。

B 树

结构

B 树是平衡多路搜索树。这里约定 $m$ 阶结点最多有 $m$ 个孩子，因此最多保存 $m-1$ 个键。令最小度数为

$$ t=\left\lceil\frac{m}{2}\right\rceil $$

除根外，每个内部结点至少有 $t$ 个孩子和 $t-1$ 个键。非叶根至少有两个孩子，所有叶结点位于同一深度。

若结点键为

$$ k_1它有 $q+1$ 个孩子。第零个孩子保存小于 $k_1$ 的键，第 $i$ 个孩子保存 $k_i$ 与 $k_{i+1}$ 之间的键，最后一个孩子保存大于 $k_q$ 的键。

B 树结点中的关键码划分孩子指针所覆盖的键值区间

阶可能指最小度数，也可能指最大键数。使用公式前要先核对定义，不能仅凭三阶判断结点容量。

检索

在当前结点中寻找第一个不小于目标的键。相等则检索成功；若不等，沿该位置对应的孩子继续下降。抵达叶结点仍未找到时，目标不存在。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
SearchResult search(BTreeNode* node, int key) {
    int position = std::lower_bound(
        node->keys.begin(), node->keys.end(), key
    ) - node->keys.begin();

    if (position < static_cast<int>(node->keys.size()) &&
        node->keys[position] == key) {
        return {node, position};
    }
    if (node->leaf) return {nullptr, -1};
    return search(node->child[position], key);
}

页内二分需要 $O(\log m)$ 次比较，但通常不增加 I/O。根页和上层页还可能长期驻留缓冲池，使一次查询实际只读取接近叶层的少数页面。

插入

新键总是插入叶结点。若叶结点未满，只需在页内保持有序；若插入后超过最大键数，则以中间键为界分裂。

中间键提升到父结点。
较小键留在原结点。
较大键移入新结点。
若是内部结点，孩子指针也随键区间分开。

三阶 B 树叶结点溢出后向父结点提升分隔键

以最多三个键的结点为例，叶结点 [10, 20, 30] 插入 25 后得到 [10, 20, 25, 30]。可把 20 或 25 作为中间键提升，具体选择取决于实现约定；两边都必须满足最小占用率。

父结点接收提升键后也可能溢出，分裂会沿祖先路径传播。根溢出时，新建一个只含提升键的根，原根分成两个孩子，树高增加一。

B 树根结点溢出后分裂并产生新的根

工程实现常在下降前就分裂已满孩子，使递归永远进入非满结点。这种自顶向下插入省去回溯处理；先插入再向上分裂的写法表达的是同一组结构变化。

删除

删除叶结点中的键最直接。若删除后仍有至少 $t-1$ 个键，结构不变；少于下限时产生下溢。

目标位于内部结点时，可以用左子树最大键或右子树最小键替换，再到叶层删除替代键。若相邻两个孩子都处于最小容量，也可以先把目标键下移并合并两边，再到合并后的结点继续删除。

叶层下溢有两种修复方式

相邻兄弟多于最小键数时，从兄弟借一项。父分隔键下移，兄弟边界键上移到父亲。
两侧兄弟都在最小容量时，把当前结点、一个兄弟和父分隔键合并。

B 树删除发生下溢时，兄弟结点与父分隔键合并

例如父结点含分隔键 40，左孩子为 [10, 20, 30]，右孩子删除后只剩 [50]。若最少要两个键，可以把父键 40 下移到右孩子，再把左孩子最大键 30 提升为新的父分隔键，得到左 [10, 20]、父 30、右 [40, 50]。

合并会让父结点少一个键，父亲也可能下溢并继续向上传播。根若删到空且只剩一个孩子，就让该孩子成为新根，树高降低一。

自顶向下删除也可以在下降前保证目标孩子至少有 $t$ 个键。这样删除叶键时不会出现无法处理的下溢，但分类仍包括借位与合并。

高度

设根的深度为零，叶深度为 $h$ 。当 $h>0$ 时，根至少有两个孩子，之后每层结点数至少扩大 $t$ 倍。最少关键码数满足

$$ n\ge 2t^h-1 $$

因此

$$ h\le\log_t\frac{n+1}{2} $$

页面能容纳数十到数百个孩子时，即使记录数很大，树高也只有几层。B 树通过高分支数压低树高。一个结点对应一个页面，每层只需读取一次页面。

B+ 树

结构

B+ 树把完整记录或记录指针全部放在叶结点，内部结点只保存导航用的分隔键。叶结点按键有序，并通过链表相连。

三阶 B+ 树及其叶结点链

B+ 树与 B 树的差别集中在数据位置：

内部结点遇到相等键仍继续下降，因为真实记录只在叶层。
内部页只保存键和孩子地址，分支数通常更大。
每次成功查询都到达叶层，路径长度一致。
叶链支持从一个边界开始连续读取范围。

检索

检索从根结点开始，在每个内部结点中确定下一棵子树。内部结点中的关键码只是叶层关键码的复写，遇到相等值时仍要继续下降，直到叶结点才能判断记录是否存在。

查询区间 $[L,R]$ 时，先沿索引定位第一个不小于 $L$ 的叶项，然后沿叶链顺序扫描，遇到大于 $R$ 的键停止。叶链让后半程不必返回内部结点，适合连续读取一段键值。

插入

新记录先插入叶结点。叶结点还有空位时，插入后只需更新受影响的边界关键码。图中的三阶 B+ 树采用子树最大键复写方式。例如，把 28 插入 [25, 30] 后得到 [25, 28, 30]，最大键仍为 30，父结点无需修改。

叶结点溢出时，将关键码分到相邻的两个叶结点，并把新叶接入叶链。继续插入 32 后，[25, 28, 30, 32] 可以分成 [25, 28] 和 [30, 32]。父结点原来只保存这个孩子的最大键 30，分裂后改为两个孩子的最大键 28 和 32。若采用右孩子最小键作为分隔键，则在父结点中加入 30。

父结点多出一个孩子后也可能溢出，此时分裂内部结点，并把新边界写入上一层。分裂传到根时建立新根，树高增加一。记录始终留在叶层，内部结点只增加导航项。

B+ 树插入记录后在叶层分裂并更新父结点分隔键

删除

B+ 树中的记录都在叶结点，删除也从叶层开始。找到目标记录并移除后，先检查叶结点是否仍满足最低装载量。

上图的三阶 B+ 树采用子树最大键复写方式，每个普通结点最多保存 3 个关键码，非根结点至少保存 2 个。内部结点中的每个关键码等于对应孩子的最大关键码。另一种常见实现保存右孩子的最小关键码，调整方法相同，只是父结点中需要改写的位置不同。

删除后仍有 2 个关键码时不会下溢。例如，从 [5, 10, 20] 删除 10 后得到 [5, 20]，父结点中的最大键 20 不变；若删除的是 20，叶结点变为 [5, 10]，父结点中对应的复写值要由 20 改为 10。有些实现允许旧值继续充当分界，只要它仍能把查询导向正确的叶结点；若规定父结点始终保存精确边界，就必须立即更新。

从 [25, 30] 删除 25 后只剩 [30]，叶结点发生下溢。同一父结点下的左兄弟 [5, 10, 20] 有 3 个关键码，可以借出 20。调整后两个叶结点分别为 [5, 10] 和 [20, 30]，父结点由 [20, 30, 40] 更新为 [10, 30, 40]。借位只移动一条记录，不改变父结点的孩子数。

若兄弟也处在最低装载量，就只能合并。从 [35, 40] 删除 35 后只剩 [40]，左兄弟 [25, 30] 无法再借，两者合并为 [25, 30, 40]。叶链跳过被移除的结点，父结点删去一个孩子并由 [20, 30, 40] 变为 [20, 40]。父结点仍有 2 个孩子，修复到此结束。

合并也可能让父结点下溢。右侧内部结点 [80, 90] 的两个叶孩子是 [75, 80] 和 [85, 90]。删除 85 后，右叶与左叶合并为 [75, 80, 90]，该内部结点只剩一个孩子。它的左兄弟 [50, 60, 70] 有 3 个孩子，可以把最右侧叶结点 [65, 70] 移给它。两个内部结点随后变为 [50, 60] 和 [70, 90]，根结点由 [40, 70, 90] 更新为 [40, 60, 90]。

若相邻内部结点也只有最低数量的孩子，就合并两个内部结点，并从它们的父结点删除一个孩子。这个过程沿路径向上重复。根结点不受普通下限约束；当根只剩一个孩子时，删除旧根，让唯一的孩子成为新根，树高减一。

B+ 树内部结点不保存记录，同一页通常可以容纳更多分支，树高也往往比 B 树低。数据库索引、文件系统目录和键值存储常使用 B+ 树或它的变体。

混合型 B 树

结构

混合型 B 树的内部结点按 B 树组织，叶层按 B+ 树组织。两层分别规定阶数：叶结点保存记录并串成链表，内部结点保存分隔键和孩子指针。

图中的叶结点阶为 5，每个叶结点最多保存 5 个关键码，非根叶结点至少保存 3 个。内部结点阶为 4，最多拥有 4 个孩子，非根内部结点至少拥有 2 个。一个内部结点若有 $k$ 个分隔键，就有 $k+1$ 个孩子。

叶结点阶为 5、内部结点阶为 4 的混合型 B 树

检索

查找仍要走到叶层。内部结点只根据分隔键选择孩子，即使遇到相等关键码也不能直接返回；范围查询定位到第一个叶项后，继续沿叶链扫描。

插入

新记录先插入叶结点。叶结点未满时，只需保持关键码有序；插入后超过叶层容量时，把叶项分到两个结点，接好叶链，再把右侧新叶的最小关键码复制到父结点。

图中的 [18, 19, 20, 21, 23] 已经占满。插入 22 后，可以分成 [18, 19, 20] 和 [21, 22, 23]，再把新右叶的最小关键码 21 写入父结点。原记录没有提升到内部层，只是多出一个指向新叶的导航项。

父结点按内部阶判断容量。内部阶为 4 时，一个结点最多拥有 4 个孩子；加入新孩子后若超过上限，就按 B 树的方式分裂，并把中间分隔键提升到上一层。叶层按 5 阶分裂，内部层按 4 阶分裂，两层不能混用同一个容量上限。

删除

以下删除过程的叶结点阶为 5，内部结点阶为 4。两层的容量下限要分别检查。

记录 33 位于叶结点 [33, 45, 47]。删去它后只剩 [45, 47]，低于叶层下限，只能与右兄弟 [48, 50, 52] 合并。

混合型 B 树删除 33 时的叶层合并位置

两个叶结点合并为 [45, 47, 48, 50, 52]，并重新接入叶链。右侧内部结点随之只剩一个孩子，低于内部层下限。左侧内部结点仍有三个孩子，可以把最右侧的 [23, 30, 31] 移给右侧。根分隔键由 33 调整为 23，右侧内部结点保留 33 作为两个叶结点之间的分界。

混合型 B 树删除 33 并完成内部结点借位后的结构

若内部兄弟也没有多余孩子，就合并内部结点，并继续检查它们的父结点。根只剩一个孩子时，唯一的孩子成为新根。叶层和内部层各用自己的阶数判断下溢，不能把叶结点的关键码下限直接套到内部结点上。

位图索引

低基数属性只有少量取值，例如状态、地区或布尔标记。位图索引为每个取值建立一条长度等于记录数的位向量，第 $i$ 位表示第 $i$ 条记录是否拥有该值。

假设四条记录的状态依次为 待处理、完成、完成、失败，可以建立

1
2
3
待处理 1000
完成   0110
失败   0001

数据库低基数属性按取值拆成多条位向量

筛选状态为 完成 或 失败 时，只需把后两条位图按位或。再与地区为 A 的位图按位与，就能组合多个筛选条件。一次机器字运算可以同时处理几十条记录。

位图适合读多写少、低基数的数据仓库。高基数列为每个值建立位图会产生大量稀疏向量；频繁插入还会扩展所有位图。游程编码与压缩位图能降低长零段和长一段的存储成本，同时保留按位运算能力。

红黑树

红黑树是用于内存动态索引的平衡二叉搜索树。把空孩子视为黑色哨兵时，它满足

每个结点为红色或黑色。
根结点为黑色。
所有空叶结点为黑色。
红结点的孩子均为黑色。
从任一结点到其后代空叶的所有路径包含相同数量的黑结点。

第五条中的黑结点数称为黑高。红结点不能连续，所以根到叶的最长路径至多在每两个黑结点之间插入一个红结点，长度不超过最短路径的两倍。

红黑树用结点颜色和黑色空叶约束路径长度

黑高为 $b$ 的子树至少含 $2^b-1$ 个内部结点，因此含 $n$ 个结点的红黑树高度满足

$$ h\le 2\log_2(n+1) $$

检索、插入与删除都有 $O(\log n)$ 的最坏时间。

旋转

旋转改变局部父子关系，却保持中序序列。左旋把右孩子提升为子树根，右旋对称进行。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Node* rotateLeft(Node* root) {
    Node* child = root->right;
    root->right = child->left;
    child->left = root;
    return child;
}

Node* rotateRight(Node* root) {
    Node* child = root->left;
    root->left = child->right;
    child->right = root;
    return child;
}