#第一性原理 花五到十倍的更大存储空间来换时间 要理解倒排，首先要知道啥是正排，正就是拿着 list，然后 contains 某个词，会非常慢，而倒排就是提前统计好某个词在哪些文档里出现，从而缩小查找范围，加快查找速度。 对于一个包含多个词汇的文档，倒排索引会将每个词汇作为一个关键字（Term），然后记录下该词汇所在的文档编号（Document ID）及该词汇在文档中的位置（Term Position）。这样，当用户输入一个关键字时，就可以快速地查找到包含该关键字的文档编号，然后通过文档编号再查找到对应的文档内容。 # Notes ## 本质 要理解倒排，首先要知道啥是正排，正就是拿着 list，然后 contains 某个词，会非常慢，而倒排就是提前统计好某个词在哪些文档里出现，从而缩小查找范围，加快查找速度。 ### **原始文档（1个文档）** ```json { "title": "北京三日游攻略", "description": "深度游览故宫、长城和颐和园，体验古都文化魅力" } ``` **存储空间**：约 100 字节 ### **倒排索引（分词后）** ```Java "北京" → [文档1:位置0] "三日" → [文档1:位置1] "游" → [文档1:位置2] "攻略" → [文档1:位置3] "深度" → [文档1:位置4] "游览" → [文档1:位置5] "故宫" → [文档1:位置6] "长城" → [文档1:位置7] "和" → [文档1:位置8] "颐和园" → [文档1:位置9] "体验" → [文档1:位置10] "古都" → [文档1:位置11] "文化" → [文档1:位置12] "魅力" → [文档1:位置13] ``` **存储空间**：约 300-500 字节（3-5倍增长） ## 时间与空间 ### 实际存储空间对比 **小规模数据** ```Java 原始文档：1MB 倒排索引：3-5MB 空间增长：3-5倍 ``` **大规模数据** ```Java 原始文档：1GB 倒排索引：5-10GB 空间增长：5-10倍 ``` **超大规模数据** ```Java 原始文档：100GB 倒排索引：500GB-1TB 空间增长：5-10倍 ``` ### 存储空间增长的原因 **1. 词汇重复存储** ```Java 原始文本："北京三日游攻略" 分词结果：["北京", "三日", "游", "攻略"] 每个词汇都要单独存储，包括： - 词汇本身 - 文档ID - 位置信息 - 频率信息 ``` **2. 位置信息开销** ```Java "故宫" → [文档1:位置6, 文档2:位置12, 文档3:位置8] 每个词汇在每个文档中的位置都需要记录： - 文档ID - 位置编号 - 偏移量 - 长度信息 ``` **3. 元数据开销** ```Java 每个词汇的索引信息包括： - 词汇本身 - 文档频率（DF） - 总词频（TF） - 位置列表 - 偏移量列表 ``` ## 为什么值得这样做？ **1. 查询性能提升** ```Java 原始查询：需要扫描所有文档 倒排索引：直接定位到包含关键词的文档 性能提升：从 O(n) 提升到 O(log n) 或 O(1) ``` **2. 用户体验改善** ```Java 搜索响应时间： - 原始方式：秒级 - 倒排索引：毫秒级 提升：100-1000倍 ``` **3. 业务价值** ```Java 电商搜索：快速找到商品 内容搜索：快速找到文章 地理位置：快速找到地点 ``` ## 存储空间优化策略 **1. 压缩技术** ```Java - 词汇压缩：使用字典编码 - 位置压缩：使用增量编码 - 文档ID压缩：使用排序和差值编码 ``` **2. 索引优化** ```Java - 只索引重要字段 - 使用 stop words 过滤 - 设置合理的字段权重 ``` **3. 存储策略** ```Java - 热数据：SSD存储 - 冷数据：HDD存储 - 分层存储：根据访问频率 ```