08 | 索引构建：搜索引擎如何为万亿级别网站生成索引？
该思维导图由 AI 生成，仅供参考
如何生成大于内存容量的倒排索引？
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了在超大规模数据应用场景中，如何使用倒排索引来高效地进行检索。对于小规模文档集合，可以使用基于哈希表的倒排索引，但对于大规模文档集合，需要将其分割成多个小规模文档集合，并在内存中生成倒排索引，然后将其存入磁盘，最终通过多路归并技术生成完整的倒排文件。这种思路与分布式计算Map Reduce的思路相似，可以方便地迁移到Map Reduce的框架上，提升倒排文件的生成效率。文章还提到了Google在2004年发表的经典的map reduce论文，指出使用map reduce来构建倒排索引是当时最成功的一个应用。文章内容涉及技术细节，对于对搜索引擎索引生成感兴趣的读者具有一定的参考价值。文章还介绍了如何使用磁盘上的倒排文件进行检索，强调了内存的检索效率比磁盘高许多，提出了将倒排文件中的词典加载到内存中，以及对长度过大的posting list进行类似B+树的索引的方法。总的来说，本文通过介绍倒排索引的生成和使用过程，展示了在大规模数据应用场景中的高效检索技术，对于搜索引擎开发和大数据处理领域的从业者具有一定的参考意义。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(13)
- 最新
- 精选
无形评论里提到用数组来存储字典，不太清楚这个字典的key和value是什么，这个涉及怎么存储，如果是ID到key，我想到用连续空间来存储，按这种结构id|length|value，先对ID排好序，length是key的长度，value是key的值，这样存储紧凑，没有浪费空间，这样查找key就可以根据ID找key，不匹配可以跳过length的长度，提高效率，如果对这片连续空间创建索引，用数组实现，数组里存储的是ID|偏移量，偏移量是相对连续空间地址的距离，可以实现二分查找；如果是key到ID的映射，类似上面的结构，按照length、key字典序排序好……有点复杂还没完全想好作者回复: 其实你想的已经很接近了。 首先，词典的查询，是以字符串为key的(因为应用入口并不知道每个字符串对应的ID是什么，它只能以字符串为key来查询，看看这个key是否存在)。 那如果是将字符串按照字典序在数组中排序好，并且是紧凑存储的(存string|length)，那么就可以和你说的一样，使用遍历的方式查找。 但是遍历的效率不高，因此我们需要加上一个索引数组来进行二分查找。 索引数组很简单，就一个元素，存每个词项在字符串数组中的偏移量。比如[0，5，18]这样。 二分查找时，从数组中间开始，读出偏移量，然后从str数组中取出这个词项，和查询的词对比，看看是否相等。如果不等，那么就继续二分查找，往左或往右，取出下一个字符串比较。 因此，我们使用两个数组，就能实现所有数据的紧凑存储。从而提升了内存的使用率。
2020-04-1313
峰存储效率优化想象中就两条路，第一是压缩，像老师说到的fst，对关键字集合的压缩。第二就是除了要存的数据，尽量别存些有的没的，比如我就用连续内存空间存词典中的每一项，是不是最省空间的，是但是变长怎么找，那再加个数组存词典中每一项的地址( 当然注意有序，当然稀疏索引也不是不能接受)。那你更新代价很高呀，那就把上述两个结构分成块存。这查找效率又不行了，那我多加几层索引，树就来啦，得出结论tradeoff真可怕。。。。作者回复: 你的思考过程非常好！这也是我这次课后题出这个问题的初衷，希望大家能从具体实现的角度出发，去推演系统的实现方案和后续演化。 我来根据你的思路补充一些细节: 1.使用数组存每个词项，这个需要解决每个词项长度不同的问题，一个思路是使用最长的词项作为数组每个元素的大小(比如说每个元素都是20个字节)。这样就可以用数组存储和查找了。 2.第一种方法空间会浪费，因此，改进方案可以另外开一个char数组，将所有字符串挨个紧凑存入；然后索引数组每个元素都是int 32类型，指向char数组中对应词项的初始位置。这样空间就都是紧凑的了。 这就是使用数组的方案。 其实如果再深入思考，你会发现char数组中好多字符都是重复的，这时候压缩重复字符的前缀树就出来了。
2020-04-13211
aoe今天才知道“前缀树”是一种压缩算法，原来只知道有这样一个数据结构……有兴趣小伙伴可以自己实现一下https://leetcode-cn.com/problems/implement-trie-prefix-tree/ 占用内存空间更小的数据结构：可以采用类似“布隆过滤器”的设计，创建一个bit型的数组，1GB内存大约可以存放85亿的key。 实现思路： 1. 创建一个bit数组 2. 需要搜索的关键字通过Hash算法映射到数组的索引位置 2.1. 索引位置 已使用值 = 1，未使用值 = 0 （缺点：根据“鸽巢原理”未能解决Hash冲突） 2.2. Hash算法简单实现（使用余数定理）：（搜索关键字 转 数字）% 数组长度（约85亿） 1GB存85亿的key计算推导： bit: 计算机中的最小存储单元 1byte包含8bits 1KB=1024Byte KB是千字节 1MB=1024KB MB是兆 1GB=1024MB GB是千兆 1TB=1024GB TB是千千兆 1GB = 1024MB = 1024 * 1024KB = 1024 * 1024 * 1024Byte = 1024 * 1024 * 1024 * 8bit = 8,589,934,592 ≈ 85亿 也可以使用工具直接转换：https://www.bejson.com/convert/filesize/作者回复: 和哈希表这种o(1)级别的检索技术相比，前缀树的检索效率不算高，因为它需要逐个字符比较，但是它有自己的特点，可以用在不同的场合中。 这篇文章中的用法，是利用了前缀树的压缩特性，将它当做压缩算法。 此外，在没有分词的场景下，前缀树其实还可以完成前缀匹配的检索功能。 还有在第14讲中，我也介绍了前缀树的另一种用法，你可以去看看。 至于你说的布隆过滤器的方案，这的确是压缩方案，不过在第四讲中，我们也说了它适合用来检索一个对象“是否存在”，而不适合检索具体的值是什么。因此在这一讲的场景中，布隆过滤器无法发挥作用。毕竟我们不仅仅要判断关键词是否存在，而是要读出关键词对应的posting list。
2020-04-2735
KL3请问老师，对倒排文件的检索，为了提高效率将词典加载到内存，并用哈希表组织，那哈希表的key是String，value是pos（文档列表在硬盘中的位置）吗？作者回复: 这个细节我在文章中没有详细描述，这里可以补充一下。 对于字典的检索，我们想查询的对象其实是关键词，因此，哈希表的key，应该是关键词的哈希值，value则是字符串。当然，由于我们还需要得到pos，因此，value其实应该是一个结构体，即保存了字符串，又保存了pos。具体结构看我下面的表示: key: 字符串的哈希值 value:[字符串，pos]
2020-05-014
天草二十六es倒排索引铺垫到现在差不多讲完了，真棒的梳理思路作者回复: 看得出来你有对每一篇的知识点进行比较和组织，这一点非常好！ “铺垫”这个词说到了我写这个专栏的一个核心思路:我希望能从场景出发，一步一步升级知识体系，让你能明白“为什么”，而不仅仅是“怎么做”。 尽管我没有专门去写es具体是怎么建立倒排索引的，但是相信你只要知道了“为什么”，那么再去看es的实现就会轻松许多，甚至你也可以根据自己的需求，写一个自己的es出来😀
2020-04-144
qinsi不是很明白存储关键词对应的字符串的作用。 1. 配图里的word是指关键字，string是指关键字所在的字符串吗？string是否可以理解为word所处的context？能否有些具体的例子呢？ 2. 存入磁盘上的临时文件时只存了string而没有存word？那么在合并文件时word的信息是从哪来的呢？ 3. 如果不存string，而只是根据word来做排序与合并的话，会有什么不好的后果吗？作者回复: 这里可能是我没有强调清楚。word指的是关键词的ID，也就是关键词的唯一标识。而string指的是关键词的具体内容。比如说一个关键词是“重启系统”，它的string有四个字符，但是Word ID只需要一个int32就够了。 这样做的好处，是用统一长度的ID在后续处理中(比如说去查posting list时，以及后面进行相关性打分时)来代替关键词本身，这样无论是存储代价还是处理代价都会更小。 而string才是关键词本身字符串，因此在“字典查询”这个过程中，string才是主体。 解释清楚了这些以后，再来看你的第二个问题和第三个问题，应该就清楚了。 由于Word ID需要全局唯一编号，因此临时文件不需要存；而如果不存入string，那么“词典查询”就无法执行，因为用户输入的原始查询就是字符串，而不是Word ID。
2020-04-1334
范闲在无压缩的情况下: 对于Hash表的存储而言，数据量大的是value，是内容。 数组当然可以直接存储，但是内容太大的情况下，占用的连续内存太大了，可能会导致内存申请失败。 对于二叉树而言，内容的内存占用并没有减少，但是求交集的操作比链表复杂些。作者回复: 有一点你说得很好，数据量大的是value，也就是词项字符串，因此，使用数组存储，最大的问题是如何存储这些字符串。 我来补充一些使用数组存储字符串的细节: 1.使用数组存每个词项，这个需要解决每个词项长度不同的问题，一个思路是使用最长的词项作为数组每个元素的大小(比如说每个元素都是20个字节)。这样就可以用数组存储和查找了。 2.第一种方法空间会浪费，因此，改进方案可以另外开一个char数组，将所有字符串挨个紧凑存入；然后索引数组每个元素都是int 32类型，指向char数组中对应词项的初始位置。这样空间就都是紧凑的了。 这就是使用数组的方案。 针对你说的char数组可能无法申请连续空间的事情，那么我们可以将char数组分段即可。 其实如果再深入思考，你会发现char数组中好多字符都是重复的，这时候压缩重复字符的前缀树就出来了。这就是用非连续的空间，用树来组织和压缩的方案。
2020-04-134- 无形看到评论里有提到前缀树，我有点疑问，如果字典的key只英文字母，如abcd可以用0123来表示，但是key如果还包含各种中英文符号、中文、韩文以及特殊字符等，怎么处理？ 我还有两个问题， 1.对于根据关键词检索出来的文档，假如结果集达到百万千万级，怎么实现快速对结果集的排序？ 2.对于已有的文档已经生成了key及对应的全量的文档列表，现在又有了新的文档，生成新的文档列表，全量的和新的文档列表怎么去合并？什么时候去合并？
作者回复: 你的这几个问题都很好。 首先，倒排索引中的key，是经过筛选的，在索引构建的过程中，会使用分词等技术，将有意义的关键词提取出来，作为key。因此不会过于无意义。 然后，即使key是中英文混合带符号的，其实都是字符串，使用前缀树依然有效。比如说“重启2020”，“重启系统”，这可以是两个key，可以用前缀树。 至于你的问题: 1.如何快速排序，我在11篇和12篇会讲，在课程上线前，你可以自己先想想，然后个课程内容对比一下。 2.索引更新问题，下一课就马上讲，敬请期待。
2020-04-1363 
明翼首先老师说hash表比较大，我们无法加入到内存中，hash表一般来说key比较小，那么假如我们hash表是按照拉链法来解决冲突，在持久化磁盘中，按照槽位的顺序保存 ，每一行即一个 [ 槽位，key，list(value)] ，由于不是每个槽位都有值，没有值的槽位key空着。我们可以在内存中，保存key和槽位的对应，以一个和槽位一样大小的数组，这样槽位和大hash表里面的槽位对应，值保存这个槽位的行在文件中的位置，来查询的时候，对要查询的数据计算hash值%槽位，得到的结果去内存中的数组中对应的位去找，找到再到文件找，找不到，就没有；如果key仍然很多，也无法用内存保存起来，可以只保存有值的key，数组中为结构体，里面含有有值的槽位，还有这个槽位在文件中的位置，查找的时候，用二分法查找；如果保留key也保存不下，那就试试用B+树，可以只保留几层，那就不用文件了，非叶子节点保存的是有值的槽位，用二分法很容易搜索，叶子节点为真正的槽位对应的值的list，不过这样的性能要差些，这样一变还是哈希表吗，哈哈作者回复: 哈哈，你这样改变以后，使用了二分查找，自然不是哈希表了。 不过你要注意一点，我们现在先不考虑posting list，而是仅仅考虑“词典太大，能否紧凑地装入内存中”。 这个时候，哈希表中的key应该是每个词项的hash值，而value是这个词项的字符串，而不是list。你可以再想想怎么做。 这个课后题的目的，其实是想让大家思考，为了将内存空间充分利用，能有哪些紧凑存储甚至压缩存储的方案。实际上，许多真实的系统中就是这么实现的。 因此，你思考过了这些问题以后，以后如果看到某些系统的索引实现很折腾，那么不要奇怪，它可能只是想把数据都放入内存中而已。
2020-04-13
ifelse
学习了，干货满满2023-04-10归属地：浙江1