检索的空间速度矛盾
全文检索要同时解决存储空间(靠压缩)和检索速度(靠索引)两个问题,二者存在张力——索引本身占空间,一味追求压缩率又会牺牲随机访问速度。难点不是把某一项做到极致,而是让两者配合:把索引和正文一起压缩到不足原文一半大小,仍能在有限磁盘访问内完成任意关键词组合检索。这正是压缩与索引必须当作同一个设计问题、而非两个独立子系统的原因。
主题对照
比较全文检索的索引粒度、倒排列表压缩、签名文件与位图、布尔查询加速与索引构造算法,以及压缩索引如何同时省空间和提速。
全文检索要同时解决存储空间(靠压缩)和检索速度(靠索引)两个问题,二者存在张力——索引本身占空间,一味追求压缩率又会牺牲随机访问速度。难点不是把某一项做到极致,而是让两者配合:把索引和正文一起压缩到不足原文一半大小,仍能在有限磁盘访问内完成任意关键词组合检索。这正是压缩与索引必须当作同一个设计问题、而非两个独立子系统的原因。
“as”“of”这类高频停用词的引用列表极其庞大,早期索引编撰者倾向直接排除以省空间。但是否索引停用词不该由存储成本决定,而应由检索完整性决定——排除意味着预先替使用者判断”这个词不会被检索”,这种预判常常是错的。压缩技术成熟后矛盾消解:停用词引用虽占索引条目三成左右,压缩后只让索引膨胀约4%。这是用工程手段消除产品设计两难的典型案例。
传统数据库靠一小部分预先选定的键(如账号)定位记录,查询能力被限定在建索引时设计好的字段范围内。全文检索把记录的每个组成部分都当作可查询的键——任何词都可能是未来查询的入口,这是理念上的根本区别,而非只是”索引更多字段”。这解释了为什么全文检索常面对设计时完全无法预见的查询组合,也是全文索引规模远大于传统数据库索引的原因。
索引要记录到多细的位置精度是可自由选择的设计参数,从”只标记文本组”到”精确到每个单词”是一条连续谱系。粒度越粗,索引越小,但命中后要读出整段原文逐字确认,多词查询易错配;粒度越细能直接支持短语查询、无需读原文确认匹配,但索引体积膨胀2~3倍。经验结论:邻近查询若是少数情况,先用粗粒度(文档级)索引筛出候选,再对候选做一次扫描确认,通常更划算。
倒排索引由字典(记录每个词对应的磁盘地址)和倒排列表(对每个词按文档号升序存放包含它的文档指针)组成。这个”升序排列”约定直接决定了布尔查询能被高效实现——AND是对多个倒排列表求交集,OR求并集,NOT求补集,升序列表求交并集只需像归并排序那样各自维护指针线性扫描。这把”检索”这个复杂问题转化成了对有序列表做归并这个已被研究透的基础操作。
建索引前通常做三种转换,本质都是”主动模糊化”以扩大查全率,但都要承担误伤代价。大小写折叠让”Data”和”data”能被同一查询命中,但会混淆本该区分的专有名词。词根化把单词归约到词干,让不同词形能被命中,但会引入语境不同的匹配。停用词过滤把高频词剔除以省空间,代价是彻底丧失查询这些词的能力。这也是为什么作者更倾向保留停用词、只在查询侧按需忽略——不可逆决策应尽量往后推。
一个词的倒排列表本身是升序文档号,直接存储每个文档号需要能表达最大文档号的位数,看起来无法压缩。但只要把”存文档号”换成”存相邻文档号之间的差值”(文档间隔),信息不丢失(可累加还原),却打开压缩空间:常见词间隔普遍很小,罕见词间隔可能很大但次数少,小间隔概率远高于大间隔。只要用变长编码给小数值分配更短码字,平均编码长度就能显著低于固定位数方案。
按香农信息量公式反推,任何给整数分配变长码字的编码方案都等价于假设一个特定的概率分布:编码越短,就相当于认定该数值概率越高。普通二进制编码假设所有值均匀分布;一元编码让编码长度随数值线性增长,隐含概率按2的负幂次陡峭衰减;γ编码隐含概率与数值平方成反比。选编码方式本质是选一个先验假设去匹配数据的真实分布,这也是为何后续要引入贝努里模型等更贴近真实分布的模型。
压缩倒排列表时可以用同一套参数处理全部词(全局模型),也可以让每个词的参数按自己出现频率单独调整(局部模型)。全局模型(如γ、δ编码)实现简单、解码快;局部模型(如Golomb编码,用每个词自身频率算最优参数b)能更精确贴合”高频词间隔小、低频词间隔大”的规律,但要为每个列表额外存参数、解码多算一步。经验结论是局部模型收益通常超过额外开销,Golomb编码因此成为默认选择。
贝努里模型假设一个词在每篇文档中出现的概率独立且均匀,但真实语料并非如此——像”切尔诺贝利”这类专有名词常因讨论同一事件的文档挨在一起存放,在倒排列表里表现为一连串很小的文档间隔紧密聚集,而非均匀撒开。有偏贝努里模型和局部双曲模型正是为了捕捉这种偏斜而设计的:把编码的第一个”桶”设得更小(用间隔中位数而非平均数作参数),让聚集出现的小间隔被更经济编码。
普通文档间隔编码是单向的——只用”前一个数是多少”推算当前数的编码范围。插值编码换了顺序:先编码列表中间位置的数,再递归对左右两半分别编码,这样编码某数时它的左右两侧都已有确定边界,能用的编码位数由这个区间宽度决定。存在聚类时,双向夹逼能把区间收窄到只剩一两个可能值,理论上可用不到1比特表示一个数,代价是实现更复杂(需维护端点栈递归处理)。
签名文件给每篇文档生成固定长度比特串”签名”:文档里每个词经哈希算出几个比特位置全部置1,文档内所有词的置位结果按位或叠加成文档级签名。查询某词时检查该词哈希出的位置在文档签名里是否都为1——只要有一位是0就能确定绝对不包含该词,直接排除;但即使全为1也只能说”可能包含”(哈希冲突),必须回读原文档做错配检查确认。它能快速确定地说”不在”,但永远无法单靠自身确定地说”在”。
把”哪些文档包含哪些词”想象成词×文档的二维矩阵,倒排索引、位图、签名文件是同一份信息的三种存储方式,区别只在如何处理稀疏性。位图逐行存完整0/1向量,等价于对文档间隔做一元编码;倒排索引只记录值为1的位置,换成更紧凑的变长编码;签名文件反过来在列方向压缩,用哈希把多词叠加进有限几个伪行,用可控错配概率换更小体积。三者没有本质信息差异,只是存储换空间或速度这一维度上的不同取舍点。
未压缩的倒排文件里,去掉最高频的一百多个停用词能省下四分之一空间。但一旦索引本身被压缩,这笔账就变了:高频词恰恰是压缩编码处理得最好的部分——文档间隔极小,用Golomb编码几乎能压到极限,去掉它们省下的空间早被编码阶段吃掉大半。TREC实测:停用词占未压缩索引四分之一体积,压缩后合计不到10MB,而整个压缩索引才93MB左右,省下空间不成比例地小,却要付出丧失查询这些词的代价。
字典按字母序排序后,相邻词大概率共享前缀(如jerusalem、jerusalemites),前端编码只存”共享前缀长度”加”剩余后缀”,不重复存公共部分。字典越大,公共前缀期望越长,真实语言前缀分布比随机假设更集中,经验值能省约40%字典空间。代价是牺牲了直接二分查找的能力,折中方案是每隔几个词保留一个完整未压缩词作跳转锚点,这是[[分块压缩与随机访问的权衡]]在字典结构里的重演。
普通哈希表几乎注定遇到冲突——即使装载因子保守,冲突概率也高得反直觉(生日悖论:365个槽,23个键值冲突概率就超过50%),因此常规哈希表要额外设计冲突处理机制。最小完美哈希函数换个思路:若字典词条提前已知且固定,可针对该集合预先计算专属哈希函数,让每个词精确映射到互不重复的位置,从数学上根除冲突。代价是换一批词就要重新构造,只适合字典基本静态、查询远比更新频繁的场景。
处理带通配符的模糊查询(如lab*r)时,若通配符不在词尾,前缀二分查找就失效。n-gram索引把字典每个词拆成固定长度片段建索引,查询时取出模式中的片段找候选词——这一步允许错配,候选词只是”包含这些片段”不保证顺序一致。真正决定答案的是随后的精确匹配校验,n-gram索引的价值是把暴力匹配缩小成对候选做精确匹配,是信息检索里常见的粗筛高召回、精确校验补齐精度的两阶段模式。
处理多词AND查询时,应先取频率最低(倒排列表最短)的词作初始候选集,再按频率从低到高依次用其余词过滤,而非按查询里出现的顺序处理。这样候选集从一开始就最小,之后只会越筛越小,内存峰值被最小化;一旦候选集变空可提前结束(实际查询中”无匹配”比例出乎意料地高)。这把”归并两个大列表”变成了”用一个小候选集去查一个大列表”,是多个过滤条件应让选择性最强的最先起作用这一通用原则的具体体现。
压缩倒排列表能大幅省空间,但也破坏了随机访问——列表本身有序理论上可二分查找,但压缩编码下无法直接跳到”中间”解码,因为每个数的位置依赖前面所有间隔累加。解决办法是牺牲一点压缩率换回随机访问:把列表切成若干等长块,每块开头文档号不压缩、直接存储作为”关键值”,查询先对未压缩关键值二分定位到块,再对块内线性解码——查找复杂度从解压整个列表降到对数级比较加解压一小块,代价是关键值本身占用空间较大。
当文档集合分散在多个节点、没有一台机器掌握全局视角时,布尔查询好办——把查询广播给每个节点,各自返回结果取并集即可。排名查询麻烦得多,因为余弦相似度依赖IDF这类全局统计量,每个节点只掌握本地词频统计,局部相似度分值在节点间不可比。解决办法是拆成两轮:第一轮各节点上报本地词频统计,中央协调节点汇总算出全局IDF权重再广播回去;第二轮各节点用全局权重计算本地排名前r的文档,再汇总做一次全局归并排序。
建索引在数学上等价于把”文档×词”频率矩阵转置成”词×文档”倒排矩阵——原始文本按文档顺序写,倒排索引却要按词序读。若在内存里摊开整个矩阵再转置,几万文档的语料就要超1GB,上百万文档会膨胀到TB级;退而用虚拟内存,因为转置要按列访问,几乎每读一个指针都触发缺页中断,实测处理规模语料要跑数小时甚至两个月。这个”数学正确、工程不可行”的落差,正是本章所有索引构造技巧要解决的核心问题。
[[建索引即转置矩阵]]的病灶是访问模式和存储介质不匹配——原始数据按文档顺序写入,倒排索引却要按词序读出,直接转换意味着大量随机磁盘寻道。基于排序的算法先把文本解析成三元组⟨词,文档号,词频⟩顺序写入临时文件,再用外部归并排序按词排序,相同词的记录自然聚在一起,顺序扫一遍就能生成倒排列表。这把随机I/O问题改造成了顺序I/O可解决的经典排序问题,代价是需要两倍最终索引大小的临时磁盘空间。
外部归并排序每趟都要完整读写整个临时文件,直觉上压缩会增加CPU开销。但实测反直觉:压缩后文件体积缩小到不足1/8,磁盘传输时间从每趟一小时降到十分钟量级,而解压+再压缩增加的CPU时间不过一个多小时——I/O节省的时间远超压缩计算多花的时间,总耗时反而更短。原因是磁盘顺序传输速度和CPU处理速度存在数量级落差,压缩本质是用CPU周期换磁盘I/O量,只要CPU比磁盘快得多这笔交易就划算。
内存内倒排要在扫描文本前为每个词的倒排列表预先分配固定大小内存,写入过程中一旦超出就无法扩展。这把Golomb编码参数选择从”求平均码长最短”变成”求最坏情况码长上界最小”——让平均情况最优的参数b未必能让最坏情况膨胀可控,必须专门推导(即Rice码)。代价是平均压缩率略微下降,换来”绝不溢出”这个硬约束——资源必须提前一次性分配且无法追加时,优化目标就要从”平均最优”切换成”最坏情况有界”。
本章的索引构造算法本质上是同一问题在三个资源维度(内存、临时磁盘、扫描次数)之间的不同取舍点,没有哪种方法三者同时最优。内存越小越需多批次处理、多扫描几遍;磁盘越宽裕越能减少归并趟数。最终结论:处理GB级文本,基于排序的原地多路归并和基于文本切分的内存内压缩两种方法胜出,额外磁盘开销压到最终索引大小的10%~35%以内。资源维度多于两个相互制约时,最优算法本身没有意义,只有给定约束下最优才有意义。
静态索引构造技巧假设数据一次性写定,但真实文档集合持续增删会暴露两个问题:压缩模型基于旧文本统计,新词只能用”逃逸”标记退化成不压缩存储;倒排列表变长后定长磁盘块可能装不下。解法是用可预测的浪费换可控的更新成本:压缩模型等文本累积膨胀到原来数倍才重建一次,重建次数是对数级、可预先估算;索引磁盘块预留约5%空闲空间吸收记录增长,配合内存更新缓存把频繁小规模磁盘操作合并成少量大块读写。
直觉上压缩要付出解压计算代价,用在查询路径应该会拖慢响应——但实测数据推翻了这个直觉。同样的TREC查询集,未压缩倒排文件处理10词查询要传输600000个指针共3.6MB数据,磁盘传输就要2秒;换成压缩倒排文件配合跳跃索引,传输数据量降到几十分之一,解码增加但远小于省下的I/O时间,查询响应反而快5到6倍,存储只多约6%。压缩本质是用磁盘带宽换CPU周期,这在磁盘远慢于CPU的年代必然划算。
海量数据里的关键词查询不能靠逐行扫描,核心是先分词,再建立关键词到文档的倒排关系。搜索系统把“临时查找”变成“预先建索引后查询”,用额外存储和索引维护成本换取查询速度。
全文检索要解决的问题是在大量非结构化文档里,根据任意一段文字内容快速定位包含它的文档。最原始的办法是顺序扫描:逐个打开每个文件、从头看到尾判断是否包含目标字符串,对小数据量可行,但面对大量文件会慢到不可用。顺序扫描慢的根本原因在于:非结构化数据天然保存的是”文件→字符串”的映射(已知文件求它包含哪些字符串很容易),而要搜索的信息恰恰相反,是”字符串→文件”的映射(已知字符串求哪些文件包含它)。全文检索的核心突破就是提前构建一份反向的索引——对每个词记录一份包含它的文档链表(倒排表),这样搜索时直接查倒排表就能拿到结果,不再需要逐个扫描原文档。这个索引构建过程只需做一次,之后可以反复搜索复用,这正是”一次索引、多次使用”相对于”每次都要重新顺序扫描”的核心优势,代价是索引本身的构建也需要时间和存储空间。
结构图:
flowchart LR
A["非结构化数据天然存储:文件→字符串映射<br/>(已知文件求含哪些词,容易)"]
A --> B["但检索需求相反:字符串→文件映射<br/>(已知词求含它的文件,难)"]
B --> C["解法:提前构建倒排索引<br/>词典→每个词对应的文档链表(倒排表)"]
C --> D["检索时直接查倒排表<br/>一次索引,多次使用,免去逐文件顺序扫描"]
Lucene 是 Java 全文检索库,需开发者自行集成,门槛高。Solr 基于 Lucene 做成独立检索服务,SolrCloud 借 ZooKeeper 管理集群、拆分大索引。Elasticsearch 同样以 Lucene 为核心,用 RESTful API 隐藏复杂性,天生分布式,可扩展到上百台服务器,且扩展对使用者透明。
点击箭头逐层展开,点击卡片标题查看详情。路径上下文仅用于连接层级,不计入主题卡片数。
来源书籍
系统架构类
书籍类型:未标注
清单覆盖 7/7
52 张卡片
来源书籍
书籍类型:经典原理
142 张卡片
来源书籍
书籍类型:经典原理
125 张卡片
来源书籍
企业大数据建设类
书籍类型:工程实践
清单覆盖 7/7
102 张卡片
来源书籍
系统架构类
书籍类型:工程实践
清单覆盖 5/6
39 张卡片
来源书籍
分布式存储系统类
书籍类型:未标注
清单覆盖 5/5
75 张卡片
来源书籍
大数据与机器学习平台工程类
书籍类型:工程实践
清单覆盖 7/7
34 张卡片
来源书籍
可观测性/监控类
书籍类型:经典原理
清单覆盖 8/8
189 张卡片
来源书籍
分布式系统类
书籍类型:工程实践
清单覆盖 3/6
125 张卡片
来源书籍
书籍类型:未标注
424 张卡片
来源书籍
实时流计算系统类
书籍类型:未标注
清单覆盖 8/8
172 张卡片
来源书籍
分布式系统类
书籍类型:经典原理
类别清单尚未核对
194 张卡片
来源书籍
系统架构类
书籍类型:未标注
类别清单尚未核对
317 张卡片
来源书籍
系统架构类
书籍类型:工程实践
清单覆盖 5/7
106 张卡片
来源书籍
书籍类型:未标注
357 张卡片
来源书籍
信息检索/搜索引擎类
书籍类型:经典原理
清单覆盖 7/7
58 张卡片
来源书籍
书籍类型:工程实践
39 张卡片
来源书籍
系统架构类
书籍类型:工程实践
清单覆盖 7/7
424 张卡片
来源书籍
书籍类型:工程实践
30 张卡片
主题索引
比较 GFS、HDFS、BigTable、MongoDB、RabbitMQ 等系统的租约、写确认、副本同步、选主与脑裂处理。
主题索引
比较渐近复杂度、摊销分析、基准测试以及以抽象换空间、局部性等时间与空间效率的权衡。
主题索引
比较在不确定性下做架构决策的方法:以风险而非结果评价决策、期望值与决策树、认知偏差、根因追问与避免不必要的决策。
主题索引
比较数据交换格式的简洁性、互通性与安全解析要求。
主题索引
比较多层防护、分段拦截与故障/入侵影响范围限制的设计方法。
主题索引
比较大数据在用户画像、个性化营销、程序化广告与实时竞价、大数据征信中的方法、数据来源与风险。
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 3 张主题卡片存在结构化链接;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;共享 1 个其他主题;来自相同书籍;属于相同分类
与 2 张主题卡片存在结构化链接;来自相同书籍;属于相同分类