知识卡片
分块索引：给压缩后的倒排列表找回二分查找能力
内容
压缩倒排列表能大幅省空间，但也破坏了随机访问——列表本身有序理论上可二分查找，但压缩编码下无法直接跳到”中间”解码，因为每个数的位置依赖前面所有间隔累加。解决办法是牺牲一点压缩率换回随机访问：把列表切成若干等长块，每块开头文档号不压缩、直接存储作为”关键值”，查询先对未压缩关键值二分定位到块，再对块内线性解码——查找复杂度从解压整个列表降到对数级比较加解压一小块，代价是关键值本身占用空间较大。
参考来源
- 位置：第4章《查询》「分块索引」小节（源文件：_chapter-text/ch04.txt）
- 结论依据：原文明确说明压缩倒排列表无法直接二分查找，分块索引通过未压缩存储每块首个文档号（关键值）实现对关键值的二分定位再线性解码块内数据，直接支持卡片论点。
- 原始内容："假定每块的第1个文档号（块的关键值）以非压缩的形式存储，那么在一个压缩的倒排列表中找到候选项就可以使用二分查找的方法只检查关键值，因为这些关键值不依赖于解压其他值……不利的一面是不再可能顺序地解码倒排列表。"