索引构建

简介: 搜索引擎如何为万亿网页构建索引?通过分治与多路归并,将文档拆分为小集合,在内存中生成倒排索引后写入磁盘,再合并多个有序临时文件,最终生成全局倒排文件。词典可加载至内存或用B+树管理,实现高效检索。该过程类似MapReduce,支持分布式扩展。

索引构建:索引构建:搜索引擎如何为万亿级别网站生成索引?
对基于内容或者属性的检索场景,我们可以使用倒排索引完成高效的检索。但是,在一些超大规模的数据应用场景中,比如搜索引擎,它会对万亿级别的网站进行索引,生成的倒排索引会非常庞大,根本无法存储在内存中。这种情况下,我们能否像 B+ 树或者 LSM 树那样,将数据存入磁盘呢?
如何生成大于内存容量的倒排索引?
我们先来回顾一下,对于能够在内存中处理的小规模的文档集合,我们是如何生成基于哈希表的倒排索引的。步骤如下:
给每个文档编号,作为它们的唯一标识,并且排好序;
顺序扫描每一个文档,将当前扫描的文档中的所有内容生成 < 关键字,文档 ID,关键字位置 > 数据对,并将所有的 < 关键字,文档 ID,关键字位置 > 这样的数据对,都以关键字为 key 存入倒排表(位置信息如果不需要可以省略);
重复第 2 步,直到处理完所有文档。这样就生成一个基于内存的倒排索引。
内存中生成倒排索引
对于大规模的文档集合,如果我们能将它分割成多个小规模文档集合,是不是就可以在内存中建立倒排索引了呢?这些存储在内存中的小规模文档的倒排索引,最终又是怎样变成一个完整的大规模的倒排索引存储在磁盘中的呢?这两个问题,你可以先思考一下,然后我们一起来看工业界是怎么做的。
首先,搜索引擎这种工业级的倒排索引表的实现,会比我们之前学习过的更复杂一些。比如说,如果文档中出现了「极客时间」四个字,那除了这四个字本身可能被作为关键词加入词典以外,「极客」和「时间」还有「极客时间」这三个词也可能会被加入词典。因此,完整的词典中词的数量会非常大,可能会达到几百万甚至是几千万的级别。并且,每个词因为长度不一样,所占据的存储空间也会不同。
所以,为了方便后续的处理,我们不仅会为词典中的每个词编号,还会把每个词对应的字符串存储在词典中。此外,在 posting list 中,除了记录文档 ID,我们还会记录该词在该文档中出现的每个位置、出现次数等信息。因此,posting list 中的每一个节点都是一个复杂的结构体,每个结构体以文档 ID 为唯一标识。完整的倒排索引表结构如下图所示:
倒排索引(哈希表实现)
那么,我们怎样才能生成这样一个工业级的倒排索引呢?
首先,我们可以将大规模文档均匀划分为多个小的文档集合,并按照之前的方法,为每个小的文档集合在内存中生成倒排索引。
接下来,我们需要将内存中的倒排索引存入磁盘,生成一个临时倒排文件。我们先将内存中的文档列表按照关键词的字符串大小进行排序,然后从小到大,将关键词以及对应的文档列表作为一条记录写入临时倒排文件。这样一来,临时文件中的每条记录就都是有序的了。
而且,在临时文件中,我们并不需要存储关键词的编号。原因在于每个临时文件的编号都是局部的,并不是全局唯一的,不能作为最终的唯一编号,所以无需保存。
生成磁盘中的临时文件
我们依次处理每一批小规模的文档集合,为每一批小规模文档集合生成一份对应的临时文件。等文档全部处理完以后,我们就得到了磁盘上的多个临时文件。
那磁盘上的多个临时文件该如何合并呢?这又要用到我们熟悉的 多路归并技术 了。每个临时文件里的每一条记录都是根据关键词有序排列的,因此我们在做多路归并的时候,需要先将所有临时文件当前记录的关键词取出。如果关键词相同的,我们就可以将对应的 posting list 读出,并且合并了。
如果 posting list 可以完全读入内存,那我们就可以直接在内存中完成合并,然后把合并结果作为一条完整的记录写入最终的倒排文件中;如果 posting list 过大无法装入内存,但 posting list 里面的元素本身又是有序的,我们也可以将 posting list 从前往后分段读入内存进行处理,直到处理完所有分段。这样我们就完成了一条完整记录的归并。
每完成一条完整记录的归并,我们就可以为这一条记录的关键词赋上一个编号,这样每个关键词就有了全局唯一的编号。重复这个过程,直到多个临时文件归并结束,这样我们就可以得到最终完整的倒排文件。
多个临时文件归并生成完整的倒排文件
这种 将大任务分解为多个小任务,最终根据 key 来归并 的思路,其实和分布式计算 Map Reduce 的思路是十分相似的。因此,这种将大规模文档拆分成多个小规模文档集合,再生成倒排文件的方案,可以非常方便地迁移到 Map Reduce 的框架上,在多台机器上同时运行,大幅度提升倒排文件的生成效率。那如果你想了解更多的内容,你可以看看 Google 在 2004 年发表的经典的 map reduce 论文,论文里面就说了使用 map reduce 来构建倒排索引是当时最成功的一个应用。
如何使用磁盘上的倒排文件进行检索?
那对于这样一个大规模的倒排文件,我们在检索的时候是怎么使用的呢?其实,使用的时候有一条核心原则,那就是 内存的检索效率比磁盘高许多,因此,能加载到内存中的数据,我们要尽可能加载到内存中。
我们知道,一个倒排索引由两部分构成,一部分是 key 集合的词典,另一部分是 key 对应的文档列表。在许多应用中,词典这一部分数据量不会很大,可以在内存中加载。因此,我们完全可以将倒排文件中的所有 key 读出,在内存中使用哈希表建立词典。
词典加载在内存中,文档列表存在磁盘
那么,当有查询发生时,通过检索内存中的哈希表,我们就能找到对应的 key,然后将磁盘中 key 对应的 postling list 读到内存中进行处理了。
说到这里,你可能会有疑问,如果词典本身也很大,只能存储在磁盘,无法加载到内存中该怎么办呢?其实,你可以试着将词典看作一个有序的 key 的序列,那这个场景是不是就变得很熟悉了?是的,我们完全可以用 B+ 树来完成词典的检索。
这样一来,我们就可以把检索过程总结成两个步骤。
第一步,我们使用 B+ 树或类似的技术,查询到对应的词典中的关键字。
第二步,我们将这个关键字对应的 posting list 读出,在内存中进行处理。
如何为万亿级别网站生成索引?
对基于内容或者属性的检索场景,我们可以使用倒排索引完成高效的检索。但是,在一些超大规模的数据应用场景中,比如搜索引擎,它会对万亿级别的网站进行索引,生成的倒排索引会非常庞大,根本无法存储在内存中。这种情况下,我们能否像 B+ 树或者 LSM 树那样,将数据存入磁盘呢?
如何生成大于内存容量的倒排索引?
我们先来回顾一下,对于能够在内存中处理的小规模的文档集合,我们是如何生成基于哈希表的倒排索引的。步骤如下:
给每个文档编号,作为它们的唯一标识,并且排好序;
顺序扫描每一个文档,将当前扫描的文档中的所有内容生成 < 关键字,文档 ID,关键字位置 > 数据对,并将所有的 < 关键字,文档 ID,关键字位置 > 这样的数据对,都以关键字为 key 存入倒排表(位置信息如果不需要可以省略);
重复第 2 步,直到处理完所有文档。这样就生成一个基于内存的倒排索引。
内存中生成倒排索引
对于大规模的文档集合,如果我们能将它分割成多个小规模文档集合,是不是就可以在内存中建立倒排索引了呢?这些存储在内存中的小规模文档的倒排索引,最终又是怎样变成一个完整的大规模的倒排索引存储在磁盘中的呢?这两个问题,你可以先思考一下,然后我们一起来看工业界是怎么做的。
首先,搜索引擎这种工业级的倒排索引表的实现,会比我们之前学习过的更复杂一些。比如说,如果文档中出现了「极客时间」四个字,那除了这四个字本身可能被作为关键词加入词典以外,「极客」和「时间」还有「极客时间」这三个词也可能会被加入词典。因此,完整的词典中词的数量会非常大,可能会达到几百万甚至是几千万的级别。并且,每个词因为长度不一样,所占据的存储空间也会不同。
所以,为了方便后续的处理,我们不仅会为词典中的每个词编号,还会把每个词对应的字符串存储在词典中。此外,在 posting list 中,除了记录文档 ID,我们还会记录该词在该文档中出现的每个位置、出现次数等信息。因此,posting list 中的每一个节点都是一个复杂的结构体,每个结构体以文档 ID 为唯一标识。完整的倒排索引表结构如下图所示:
倒排索引(哈希表实现)
那么,我们怎样才能生成这样一个工业级的倒排索引呢?
首先,我们可以将大规模文档均匀划分为多个小的文档集合,并按照之前的方法,为每个小的文档集合在内存中生成倒排索引。
接下来,我们需要将内存中的倒排索引存入磁盘,生成一个临时倒排文件。我们先将内存中的文档列表按照关键词的字符串大小进行排序,然后从小到大,将关键词以及对应的文档列表作为一条记录写入临时倒排文件。这样一来,临时文件中的每条记录就都是有序的了。
而且,在临时文件中,我们并不需要存储关键词的编号。原因在于每个临时文件的编号都是局部的,并不是全局唯一的,不能作为最终的唯一编号,所以无需保存。
生成磁盘中的临时文件
我们依次处理每一批小规模的文档集合,为每一批小规模文档集合生成一份对应的临时文件。等文档全部处理完以后,我们就得到了磁盘上的多个临时文件。
那磁盘上的多个临时文件该如何合并呢?这又要用到我们熟悉的 多路归并技术 了。每个临时文件里的每一条记录都是根据关键词有序排列的,因此我们在做多路归并的时候,需要先将所有临时文件当前记录的关键词取出。如果关键词相同的,我们就可以将对应的 posting list 读出,并且合并了。
如果 posting list 可以完全读入内存,那我们就可以直接在内存中完成合并,然后把合并结果作为一条完整的记录写入最终的倒排文件中;如果 posting list 过大无法装入内存,但 posting list 里面的元素本身又是有序的,我们也可以将 posting list 从前往后分段读入内存进行处理,直到处理完所有分段。这样我们就完成了一条完整记录的归并。
每完成一条完整记录的归并,我们就可以为这一条记录的关键词赋上一个编号,这样每个关键词就有了全局唯一的编号。重复这个过程,直到多个临时文件归并结束,这样我们就可以得到最终完整的倒排文件。
多个临时文件归并生成完整的倒排文件
这种 将大任务分解为多个小任务,最终根据 key 来归并 的思路,其实和分布式计算 Map Reduce 的思路是十分相似的。因此,这种将大规模文档拆分成多个小规模文档集合,再生成倒排文件的方案,可以非常方便地迁移到 Map Reduce 的框架上,在多台机器上同时运行,大幅度提升倒排文件的生成效率。那如果你想了解更多的内容,你可以看看 Google 在 2004 年发表的经典的 map reduce 论文,论文里面就说了使用 map reduce 来构建倒排索引是当时最成功的一个应用。
如何使用磁盘上的倒排文件进行检索?
那对于这样一个大规模的倒排文件,我们在检索的时候是怎么使用的呢?其实,使用的时候有一条核心原则,那就是 内存的检索效率比磁盘高许多,因此,能加载到内存中的数据,我们要尽可能加载到内存中。
我们知道,一个倒排索引由两部分构成,一部分是 key 集合的词典,另一部分是 key 对应的文档列表。在许多应用中,词典这一部分数据量不会很大,可以在内存中加载。因此,我们完全可以将倒排文件中的所有 key 读出,在内存中使用哈希表建立词典。
词典加载在内存中,文档列表存在磁盘
那么,当有查询发生时,通过检索内存中的哈希表,我们就能找到对应的 key,然后将磁盘中 key 对应的 postling list 读到内存中进行处理了。
说到这里,你可能会有疑问,如果词典本身也很大,只能存储在磁盘,无法加载到内存中该怎么办呢?其实,你可以试着将词典看作一个有序的 key 的序列,那这个场景是不是就变得很熟悉了?是的,我们完全可以用 B+ 树来完成词典的检索。
这样一来,我们就可以把检索过程总结成两个步骤。
第一步,我们使用 B+ 树或类似的技术,查询到对应的词典中的关键字。
第二步,我们将这个关键字对应的 posting list 读出,在内存中进行处理。

相关文章
|
存储 SQL 分布式计算
数据湖 VS 数据仓库之争?阿里提出大数据架构新概念:湖仓一体
随着近几年数据湖概念的兴起,业界对于数据仓库和数据湖的对比甚至争论就一直不断。有人说数据湖是下一代大数据平台,各大云厂商也在纷纷的提出自己的数据湖解决方案,一些云数仓产品也增加了和数据湖联动的特性。但是数据仓库和数据湖的区别到底是什么,是技术路线之争?是数据管理方式之争?二者是水火不容还是其实可以和谐共存,甚至互为补充?本文作者来自阿里巴巴计算平台部门,深度参与阿里巴巴大数据/数据中台领域建设,将从历史的角度对数据湖和数据仓库的来龙去脉进行深入剖析,来阐述两者融合演进的新方向——湖仓一体,并就基于阿里云MaxCompute/EMR DataLake的湖仓一体方案做一介绍。
30185 2
数据湖 VS 数据仓库之争?阿里提出大数据架构新概念:湖仓一体
|
机器学习/深度学习 算法 PyTorch
【PyTorch实战演练】Fast R-CNN中的RoI(Region of Interest)池化详解
【PyTorch实战演练】Fast R-CNN中的RoI(Region of Interest)池化详解
868 1
|
5月前
|
安全 开发工具 数据安全/隐私保护
CI/CD流水线凭据泄露分析:从GitHub密钥扫描到企业级凭据管理方案
2026年GitHub遭恶意VS Code扩展攻击,致3800+内部仓库凭据泄露。本文剖析CI/CD凭据泄露五大路径(硬编码、明文配置、镜像残留等),实战演示Gitleaks、TruffleHog、GitHub Secret Scanning扫描方案,并提出三层凭据管理架构与动态凭据最佳实践。(239字)
883 0
|
8月前
|
存储 数据采集 人工智能
什么是数据湖?一文搞懂数据湖、数据仓库、湖仓一体
本文用通俗语言解析数据湖、数据仓库与湖仓一体三大核心概念:数仓专注结构化、高性能分析;数据湖支持多源原始数据低成本存储;湖仓一体则融合二者优势,实现统一存储、灵活探索与可靠分析。附实战方案与工具推荐。
|
7月前
|
缓存 前端开发 定位技术
Flutter for OpenHarmony 实战之基础组件:第三篇 Stack 层叠布局详解
本文详解 Flutter for OpenHarmony 中 Stack 层叠布局:涵盖 Z 轴堆叠原理、Alignment 对齐与 Positioned 精准定位,实战 Badge 角标、新闻 Banner 及 IndexedStack 页面状态保持,助你高效构建跨端复杂 UI。(239字)
697 1
Flutter for OpenHarmony 实战之基础组件:第三篇 Stack 层叠布局详解
|
SQL 运维 安全
场景化经验复用工具深度分析:在多项目并行中如何实现高频经验沉淀与复用?
在团队协作中,问题重复发生、经验难以复用是常见痛点。本文提出“场景化经验复用”方法,通过结构化沉淀、智能推荐与流程嵌入,让经验在需要时自动浮现,提升团队效率与新人成长速度,构建“问题→经验→行动”的闭环,打造真正可复用的知识资产。
|
9月前
|
人工智能 运维 网络安全
2026年OpenClaw/Clawdbot、Moltbot指南:零基础一键部署+skills拓展实战
2026年,OpenClaw(曾用名Clawdbot、Moltbot)凭借“自然语言驱动任务执行、多场景适配、开源免费”的核心优势,成为AI智能体赛道的现象级项目,GitHub星标数快速突破18万+。它并非传统聊天机器人,而是能自主完成文件处理、代码调试、网页抓取、跨平台交互的“全能数字助理”,既能帮普通人解放重复办公负担,也能为开发者节省大量调试时间。
803 18
Jetson学习笔记(二):TensorRT 查看模型的输入输出
这篇博客介绍了如何使用TensorRT查看模型的输入输出,并通过代码示例展示了如何获取和验证模型的输入输出信息。
915 5
|
10月前
|
监控 Windows
Windows笔记本打游戏卡顿掉帧?一招教你解决!
笔记本玩游戏卡顿?可能是显卡设置出了问题。本文分享如何通过NVIDIA控制面板强制使用高性能显卡,轻松将《原神》《星穹铁道》帧率稳定至60FPS,提升游戏体验。排查思路清晰,操作简单,值得一试。
2613 0
|
数据采集 存储 JavaScript
基于Python 爬书旗网小说数据并可视化,通过js逆向对抗网站反爬,想爬啥就爬啥
本文介绍了如何使用Python编写网络爬虫程序爬取书旗网上的小说数据,并通过逆向工程对抗网站的反爬机制,最后对采集的数据进行可视化分析。
1464 109
基于Python 爬书旗网小说数据并可视化,通过js逆向对抗网站反爬,想爬啥就爬啥