倒排索引构建SPIMI算法

可视化演示

倒排索引基础：图书馆的主题卡片柜

每个图书馆深处都藏着一排抽屉柜，标签按字母排列得整整齐齐。读者问“哪些书提到了恐龙？”，管理员走到“D“区，抽出”恐龙“卡片，背面写着”3号书架、7号书架、12号书架“——一秒钟就能作答。这套卡片柜就是图书馆的检索灵魂，也是我们理解倒排索引最好的起点。它回答了一个核心问题：如何从”词“迅速找到”书”。

搜索引擎把这套逻辑原封不动搬进了计算机。卡片上的“主题词”被称为词项（term），书架编号被称为文档ID（docID）。所有词项合在一起叫词典（dictionary），每张卡片背面的位置列表叫倒排表（posting list）。因为查找方向是“从词到文档”，与普通书架“从文档到词”刚好相反，所以这套结构叫倒排索引（inverted index）。

当用户输入一个查询时，系统把查询拆成若干词项，然后在词典中定位每个词项，取出各自的倒排表，最后把这些倒排表合并成结果集。这个动作可以写成一个简洁的数学表达：

明白了卡片柜长什么样，下一个问题自然浮现：图书馆有上万本书，管理员怎样才能在一天内把这套卡片柜又快又省地建起来？这正是SPIMI算法要解决的难题。

SPIMI核心思想：边读边建卡，一次翻完所有书

老师傅传授的第一条铁律是“每本书只翻一遍”——这叫单遍扫描。他从第一本书开始，边翻边抽卡片：遇到一个卡片柜上没有的新主题词，就立刻抽一张新卡片写上主题；如果卡片已经存在，就在卡片背后追加一个书架编号。整个过程中，他绝不为任何一本书回头翻第二次，也绝不事先把所有抽屉按字母重排。

这种策略的核心叫做就地更新（in-place update）：每处理一个文档，就立刻把词项插进词典、把文档ID追加进对应的倒排表，而不是把“词项-文档ID”二元组全部收集起来再去排序。与此同时，工作台（内存）的容量是有限的，所以他把所有藏书分成若干批，每处理完一批，就把当前工作台上的卡片盒完整搬进仓库（磁盘），形成一个硬盘段（segment），然后清空工作台继续下一批。

从数学上看，SPIMI把整个索引构建拆成了“分块构建 + 块间合并”。每个内存块独立产出一个局部索引 \(I_k\)，覆盖该块对应的那批文档。最终，把 \(k\) 个局部索引合并成全局索引 \(\mathcal{I}\)：

这位管理员的聪明之处，在于不追求一次性把所有卡片放在工作台上，而是分批建造、最后合并。这正是SPIMI的全部秘密：用“单遍扫描”换掉“反复读盘”，用“就地更新”换掉“全局排序”。

字典动态扩展：可伸缩的卡片标签盒

管理员最怕的一件事，是卡片盒上事先贴好的标签不够用。他灵机一动，发明了一种可伸缩标签盒：每遇到一个没见过的新主题词，就先查一本速查小册子（哈希桶），确认它不存在，然后立刻在标签盒中插入一张新标签和一张新卡片，标签盒自动向后挤出空位。整个过程不需要重新整理所有标签，也不需要预留一大片空白区。

这个可伸缩标签盒在计算机里就是动态哈希表。SPIMI每读一个词项，先计算它的哈希值，定位到对应的桶；如果桶里没有这个词项，就在词典中新增条目，并分配一个指向空倒排表的指针；如果词项已存在，只需在倒排表末尾追加文档ID。哈希表的平均查找时间是 \(O(1)\)，这让“单遍扫描”真正跑得起来。

但哈希表不可能无限膨胀，它有一个关键指标叫装载因子（load factor），即已用条目数与桶数的比值。当装载因子超过阈值时，哈希表需要扩容，通常是把桶数翻倍，再把所有词项重新哈希：

动态扩展意味着管理员的卡片盒永远不会“爆掉”。无论新增多少本藏书、冒出多少生僻主题词，盒子都能自动长大，这正是SPIMI能在亿级文档上稳定运行的原因。

倒排表压缩：在卡片上写更小的字

卡片空间总是宝贵的。老师傅发现，如果一张卡片上要写“135、145、162“，数字又大又占地方。他改用一种巧妙的记法：只写第一个页码”135“，后面只写相邻差值”+10“和”+17”。这样每个数字都小得多，卡片上能挤下更多信息。更妙的是，这套记法完全可逆——恢复时把数字逐项累加，就能还原原始页码。

计算机里的做法几乎一模一样，称为差值编码（delta encoding）。由于倒排表中的文档ID严格升序排列，相邻ID的差值往往远小于ID本身。把大整数变成小整数之后，再配合变长编码（variable-byte encoding）：小整数只占1个字节，大整数占2个或多个字节。这样，原先固定4字节的文档ID，平均可能只需1~2字节，压缩率常常超过50%。

用公式表示，假设倒排表中有 \(n\) 个文档ID \(d_1 < d_2 < \cdots < d_n\)，那么存储的将是：

压缩让管理员能在更小的卡片上写下更多信息。内存里能装下更多卡片，SPIMI的“分块”就能设得更大，写盘的次数自然更少，构建速度也就更快。

磁盘归并流程：把抽屉合成总柜

分馆的同事送来了几抽屉卡片，总馆要如何把它们合并成一套总索引柜？老师傅的做法是“并排比大小”：把两个抽屉的标签列并排放在桌上，谁的字母靠前就先把谁抽出来；如果两张卡片的主题词相同，就把它们背后的书号合并到一张新卡片上，然后继续比较下一对。整个过程像拉链一样，一格格咬合前进。

计算机里的这个过程叫多路归并（k-way merge）。磁盘上的每个段都按词典序排列，归并器为每个段维护一个“当前词项”指针。每一轮，它比较这 \(k\) 个指针指向的词项，选出字典序最小的那个，将它的整条倒排表与被合并段中相同词项的倒排表拼接，然后向前移动该段指针。为了避免每轮都做 \(k\) 次比较，归并器通常用一个最小堆来维护指针，使每次取最小值只需 \(O(\log k)\)。

如果所有段的倒排表条目总数为 \(n\)，那么整个归并过程的时间复杂度是：

归并是“分而治之”的最后一步收尾。它把无数张零散的小卡片精炼成一套优雅的总索引柜，从此读者查询时只需一次抽取。

BSBI对比：先抄再排的旧方法

老派管理员的风格完全不同。他先准备了一叠空白便签，把每本书的每个主题词连同书架编号抄成一张张便签，堆成一座小山。等便签攒够一批，他就把所有便签按主题词排序，整理成卡片柜。问题在于，便签堆满了工作台，他不得不时常把半成品搬进仓库，下次再搬回来继续排，来回多走了一轮冤枉路。

这种方法在信息检索里叫BSBI（基于块的排序索引构建，Block-based Sort-based Indexing）。它把文档集分成若干块，每块加载所有“词项-文档ID”二元组，在内存中排序后写盘，生成一个中间文件；最后把所有有序中间文件归并成最终索引。BSBI本质上仍是“先收集、再排序、后建索引”的路线。

两种方法每块构建的复杂度差异很明显。设块内词条数为 \(B\)，BSBI每块要排序，而SPIMI借助哈希表就地追加，整体上近似线性：

复杂度差异之外，两者更现实的差距在磁盘I/O：BSBI要额外写出“排序后的中间文件”，SPIMI则直接把内存块作为段写出，少了一整轮磁盘往返。因此SPIMI在内存利用率和构建速度上双双胜出，这也是现代搜索引擎（如Lucene）优先选择SPIMI式构建的原因。

分布式扩展：分馆同时开工

当藏书量大到一家图书馆堵得水泄不通时，馆长决定开分馆。每家分馆负责一批书架，使用完全相同的卡片规则，边读边建，互不打扰；最后总馆把各分馆送来的卡片盒统一合并。因为各家用的规则一致，合并时只需按主题归位，完全不需要跨馆通信。

这就是分布式索引构建的思路。在工程上通常借助MapReduce框架：先把海量文档按某种策略分片（shard），每个Mapper独立地在自己的分片内执行SPIMI式构建，输出局部索引；Reducer负责把相同词项的倒排表合并到一起。分片策略可以按文档ID范围切分，也可以按哈希分桶，目的是让词项尽量不跨节点shuffle，减少网络传输。

理论上，并行带来的加速比不可能无限增长。设串行构建时间为 \(T_1\)，用 \(p\) 台机器并行的时间为 \(T_p\)，则加速比：

SPIMI的“分块-归并”基因天然适配分布式。每位分馆管理员只需按同一套本地逻辑工作，最终汇总出的总索引柜依然完整无缺，查询端看到的只是一个无缝的整体。

---

AI 应用场景

Python 演示

import jsonimport osimport tempfile DOCS = [    (1, "苹果 香蕉 苹果"),    (2, "苹果 樱桃"),    (3, "香蕉 苹果 香蕉"),    (4, "樱桃 香蕉"),] class DocStream:    """模拟单遍扫描的文档流, 每次取一个块"""    def __init__(self, docs):        self.items = list(docs)        self.cursor = 0     def next_chunk(self, size):        chunk = self.items[self.cursor:self.cursor+size]        self.cursor += size        return chunk  def build_local_index(chunk):    """在一个内存块内就地构建局部倒排表"""    index = {}    for doc_id, text in chunk:        for term in set(text.split()):            if term not in index:                index[term] = []            index[term].append(doc_id)    return index  def merge_indexes(segments):    """多路归并: 相同词项的倒排表拼接成全局索引"""    final = {}    for seg in segments:        for term, postings in seg.items():            if term not in final:                final[term] = []            final[term].extend(postings)    return final  def spimi(docs, block_size):    stream = DocStream(docs)    tmp_dir = tempfile.mkdtemp()    segments = []    while True:        chunk = stream.next_chunk(block_size)        if not chunk:            break        local = build_local_index(chunk)        seg_path = os.path.join(tmp_dir, "seg_%d.json" % len(segments))        with open(seg_path, "w", encoding="utf-8") as f:            json.dump(local, f)        segments.append(seg_path)    loaded = []    for seg in segments:        with open(seg, "r", encoding="utf-8") as f:            loaded.append(json.load(f))    return merge_indexes(loaded)  if __name__ == "__main__":    index = spimi(DOCS, block_size=2)    for term in sorted(index):        print("%s -> %s" % (term, index[term]))

1. class DocStream:模拟SPIMI的单遍扫描文档流，每次只取出一个块。
2. chunk = self.items[self.cursor:self.cursor+size]用切片切出一个内存块，游标顺序前进。
3. for term in set(text.split()):先分词再用集合去重，保证每篇文档在一个词项下只出现一次。
4. if term not in index:字典动态扩展：遇新词立即新建倒排表。
5. index[term].append(doc_id)就地更新：词项已存在则直接追加文档ID。
6. json.dump(local, f)内存块写盘，生成一个磁盘段。
7. merge_indexes(loaded)多路归并：把各段相同词项的倒排表拼接成全局索引。

常见误区

面试题