返回主题:倒排索引与查询处理

知识卡片

普通读书笔记卡 · 1227

建索引即转置矩阵

理解等级:未标注

建索引在数学上等价于把”文档×词”频率矩阵转置成”词×文档”倒排矩阵——原始文本按文档顺序写,倒排索引却要按词序读。若在内存里摊开整个矩阵再转置,几万文档的语料就要超1GB,上百万文档会膨胀到TB级;退而用虚拟内存,因为转置要按列访问,几乎每读一个指针都触发缺页中断,实测处理规模语料要跑数小时甚至两个月。这个”数学正确、工程不可行”的落差,正是本章所有索引构造技巧要解决的核心问题。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    原书出处

    参考来源

    - 位置:第5章《索引构造》5.1节前导(源文件:_chapter-text/ch05.txt,对应_epub-src/OEBPS/text00011.html) - 结论依据:原文用《圣经》和TREC文档集的具体矩阵大小(1GB和1.4TB)以及700000次页错误的实测数据,说明朴素转置矩阵法在工程上不可行,直接支持卡片论点。 - 原始内容:"假定需要将《圣经》进行这样的倒排……这相当于略比1GB多一些的空间……对于更大一些的TREC文档集合,矩阵的大小将惊人地达到……1.4TB……创建《圣经》的索引将会出现700000次页错误"