特别加餐 | 倒排检索加速（一）：工业界如何利用跳表、哈希表、位图进行加速？
该思维导图由 AI 生成，仅供参考
跳表法加速倒排索引
荧光笔
直线
曲线- 深入了解
- 翻译
- 解释
- 总结
本文介绍了工业界如何利用跳表、哈希表和位图对倒排索引进行加速。首先介绍了跳表法加速倒排索引，通过跳表实现posting list，利用相互二分查找和可变长数组进行归并，提高检索效率。其次，讨论了哈希表法加速倒排索引，通过将posting list转为哈希表，实现O(1)级别的查找能力，但需要提前分析和保留原始posting list。最后，介绍了位图法加速倒排索引，通过位图的位运算进行检索加速，但存在适用场景限制和空间消耗问题。文章还介绍了Roaring Bitmap的设计思想和优化，以及在实际应用中的交集求解过程。总结指出，基础的数据结构和算法组合在一起，能提供更强大的检索能力，而且这也是大量的工程系统中广泛使用的设计方案。深入理解每一种基础数据结构和算法的特点和适用场景，并且能将它们灵活应用，能帮助更好地学习和理解复杂的数据结构和算法，以及更好地学会如何设计复杂的高性能检索系统。
《检索技术核心 20 讲》，新⼈⾸单¥59
全部留言(25)
- 最新
- 精选
每天晒白牙思考题 1.位图和位图求交集 要对两个位图的交集做预判，如果预判数据大于 4096 就用位图，如果小于 4096 就用数组，当然预判肯定会有误判率，不过没关系，即使误判错多做一次转换就行了 2.数组和数组求交集 数据和数据求交集结果肯定还是用数组存 3.位图和数组求交集 位图和数组求交集也是用数组 问题请教： 对 Roaring Bitmap 这儿看的不是很明白，也不知道自己哪里不明白，可能就是不明白吧，请问老师这块有啥好的学习方法吗？ 还有就是对于 Lucene 采用 RoaringDocIdSet 实现的 Roaring Bitmap，要想学好这里，是不是还要学些相关的源码呢？如果要学 ES 和 Lucene 的源码，老师有啥好的建议吗？作者回复: 讨论题思考得很清楚！ 关于roaring bitmap（简写RBM），你其实可以把它看做是一个倒排索引。对于一个32位的数，RBM将这个数的高16位当做key，然后将这个数存入对应的posting list中。posting list用位图表示（长度为2^16）。这样思考，会不会更好理解一些? 这也是我说的学习知识点要多对比，多拆解。 至于如何学好es和lucene的源码，一般来说有两种学习方式:一种是你先学好一个高效检索引擎的各种核心技术，然后这时候你去看es和Lucene的代码，你就会发现，其实这些代码就是为了实现这些设计而写的；另一种方式呢，就是从代码出发，遇到不明白的地方再去查资料，去弄明白为什么要这么实现。 这两种方式，我个人比较倾向先了解了大致原理，再去看代码。这样往往效率会更高。其实就像你自己写代码，先设计好以后再实现会更高效一样。
2020-04-06216
奕思考题： 数组和数组求交集、位图和数组求交集 这两种情况可以很容易的想到是使用数组 这里解释一下 位图与位图交集的预判的情况，一般是怎么进行预判的： 假设位图1有 n1 个值， 位图1 有 n2 个值，位图的空间位 2 ** 16 = 65536 这里进行预判的时候可以认为是均匀分布的： 那么对于位图1 可以认为间隔 65536 / n1 个位有个值，位图2 可以认为间隔 65536 / n2个位有个值， 那么同时存在 n1和n2 的间隔为 t = （ 65536 / n1 ） * （65536 / n2），那么交集出来的个数为 m = 65536 / t = n1 * n2 / 65536 , 载拿 m 和 4096 进行比较 预判即可作者回复: 分析得很清晰！在系统面临多种后续情况时，一种常见的处理方式就是预判一种概率最大的情况，先按这种情况处理。这样系统的整体统计性能会最好。
2020-04-0659- 奕仔细算了 一下 Roaring bitmap 压缩后使用的空间，发现压缩率非常大 在一个正常的 32位的 bitmap 占的空间位 2 ** 32 bit ---> 2 ** 29 byte ---> 2 ** 19k---> 2 ** 9 M 也就是512 M 在使用Roaring bitmap 后一个键位图占的空间位（不考虑高16位的数组空间动态申请，和底16位使用数组存储）： 提前申请好高16位的空间为 2 ** 16 * 2 byte = 2 ** 17 byte --> 2 ** 7 k, 一个位图的空间为 2 ** 16 bit --> 2 ** 13 byte --> 2 ** 3 k， 所以需要的总空间位 2 ** 7 k * 2 ** 3 k = 1 M 从 512 M 降到 1M 这个效率，所以设计好的数据存储结构是写好程序的第一步
作者回复: 你很好地理解了roaring bitmap的思路。不过空间不会无缘无故变出来的，在极端情况下（高16位都有，低16位都是位图），那么roaring bitmap不会比原始位图小。你可以仔细算一下，每个位图是8k，如果高16位每个数都存在，那么就有2^16个位图，2^16*8k = 2^9 M = 512M
2020-04-0636 
微思老师好，对于文章中说哈希表没有遍历能力我很疑惑，我的理解：哈希表底层基于数组实现，也是可以遍历的，比如以Java语言的HashMap为例，就可以遍历读取hash表中的元素的。还请老师解惑，谢谢作者回复: 此“遍历”非彼“遍历”。我所说的遍历，严格意义上是指“元素接元素的，时间代价是o(n)级别的遍历”。 你可以想一想这样一个例子: 一个哈希表数组长度为10000，然后我们在里面存入a和b两个元素。 那我们要遍历哈希表时，需要去穷举整个长度为10000的数组的每个位置，才能找出里面有两个元素a和b。这个其实不是“o(n)级别的元素接元素的遍历”。 因此，尽管许多容器都有类似的函数接口，比如containsKey，next等，但是它们的效率差距非常大。这也是为什么我们要熟悉它们的底层实现的原因，这样才能保证你的程序是高效的。
2020-04-09114
牛牛原来roaring bitmap是这么设计出来的, 上次觉得太高大上就跳过去了~~~, 今天细细的看了下, 稍微写了点笔记: 1. 设计思想: 将32位整数分成高16位和低16位, 高16位、存储到一个有序数组中, 每一个值都是一个`桶`; 低16位, 存储在2^16的位图中, 相应位置1, 查找时, 先判断桶是否存在, 若存在、再check位图相应位 如何节省空间的 若所有元素高16位都是相同的, 在有序数组部分, 只需要一个2字节的桶(高16位-2字节), 若提前分配好了2^16个桶, 那就需要128k的空间. 低16位, 因为长度是固定的, 都是2^16个bit、即8字节. (若使用普通位图, id范围是int32的话、则需要512M的空间), 因此可以很大的节省空间. 其实核心思想就是: 将不存在的桶的位图空间全部省去 2. 优化: Roaring bitmap还对低16位的位图进行了优化: 若桶中存储的数据少于4096(容量的1/16), 就使用short型的有序数组来存储, 上限是4096(4k)个, short占用两个字节, 这样存储空间就小于位图占用的空间了. 3. 有序数组和位图转换时机(与hashmap类似) a. 刚插入时、数量少, 默认数组容器 b. 桶中数据增多时, 大于4096个, 则转为位图容器 c. 随数据删除, 元素个数小于4096个, 则退化为数组容器 4. 怎么快速求交集 比较高16位, 将所有相同的桶保留 对相同桶里的元素求交集, 3种情况: 数组&数组: 相互二分查找; 位图&位图: 直接位运算; 位图&数组: 遍历数组、在位图中查找.作者回复: 总结得很好。你会发现，看上去高大上的东西，其实拆开来看，也是由更基础的知识组成。相信经过这样的学习，你以后看到了高大上的新知识，会更有信心去拆解和研究了。
2020-05-193
Roger宇各位，问一个可能很低级的数学问题呀，id范围是int32类型的bitmap，怎么算出大小约为512m呢？int32取值范围是-2^31 到2^31-1。为什么一个bitmap大小约为512m呢？作者回复: 计算方如下: int32能表示2^32个数，如果用bitmap表示，每个数需要占1个bit，因此共需要2^32个bit。 2^32个bit = 2^29个 byte (8个bit为一个byte) 而2^10 = 1024 = 1k，2^20 = 1024 k = 1m 故2^29个byte = 2^9 * 2^20 个byte = 512m byte。
2020-08-0722
峰今天竟然是两篇加餐，表示老师很努力，很nice！ 讨论题： 主要考虑的点就是1. 怎么计算交之后该桶的元素个数 2. 新建continer，还是说原地计算。（先只考虑新建吧） 位图和位图 可能最后的结果是数组也可以是位图，可以根据两个位图本身的数量（n1 n2），并假设其均匀分布，n1 * n2/65536 大于等于 4096 则用位图，否则用数组，得到结果发现不是对应的continer，就要转换了。 数组和位图 ，数组和数组 这两个就相对简单了， 结果必然是数组。 问题: hash 表不能遍历这个问题，和链表结合不就可以了吗？为什么还要存一份原始的posting list。作者回复: 讨论题:分析得很好！先做预判再操作，如果预判错误了，那么就需要多做一次转换。先做预判是计算机系统中经常会涉及的一种设计和实现思想。在第二篇加餐中，是否要做集合分配律拆分也是基于预判的。包括数据库查询时，对SQL语句的优化也是会基于预判。 问题:哈希表+链表的结构的确可以（类似LinkedHashMap这样的结构）。不过链表的遍历效率不高，在链表较长的情况下，链表和哈希表求交不如用跳表法。因此，保留原始posting list最大的好处，是原始posting list可以是用跳表实现，也可以是用链表实现。有更多的适用性。（当然，如果原posting list是链表实现，其实就是你说的哈希表+链表了）
2020-04-062- Geek_d62be1求交集以后的数据，是需要还原成id然后获取文档返回的吧，那如果低16位交集结果用位图存储，怎么去获取位图中的值，遍历吗？还是有什么快速的方法可以获取？
作者回复: 要知道位图中有多少个位是1，常规的办法是遍历，如果只有低16位，遍历的代价是可接受的。但如果位图很大(比如有1024位)，而被置为1的位很少的话，我们可以用位运算的思想，按32位或者64位为单位去与位图当前的范围做and运算，如果结果是0就快速跳过往后继续查找，这样就可以加速了。
2021-04-161 - 杨焱老师，问下，位图如何获取里面存的所有id，是需要遍历每一位吗？
作者回复: 位图你其实可以看做是特殊的哈希表，因此它和哈希表一样，如果想获得里面存的所有id，需要低效地遍历每一位。
2020-07-051 
青鸟飞鱼老师你好，这是第n次刷压缩位图了，总算看明白了。有个问题想请教一下，高16用数组存，低16用位图，为什么不是高16位用位图，低16位用数组实现压缩位图呢。我想到的原因是因为高16位相同概率高吗？还是有其他原因呢？作者回复: 多问为什么是一种很好的学习方法。我们一起来分析一下，为什么不是高16位用位图，低16位用数组呢？ 你可以先考虑这样一种情况:如果高16位用位图，低16位也是位图，那么这和原先一个完整的位图表示是否有区别?你会发现，这样的结构，空间一点都没有节省。高16位有2^16个桶，每个桶有一个位图(大小是2^16)，那么总空间还是2^16 * 2^16 = 2^32。如果再加上索引本身的开销，那么会比原始位图还更占空间。 那我们要怎么做才会省空间呢？你会发现，如果位图中的元素很稀疏，那么将位图转为数组，会更省空间。因此，在初始的时候，我们应该把高16位和低16位都变成数组，这就是为什么高16位是数组的原因。 那么，按照这个思路，如果高16位的元素越来越多，那么其实当它达到一定数量的时候(和低16位的处理方案相似，大于8k时数组转为位图)，我们是可以将它转为位图的，这样效率的确会更高。 当然，一般来说，高16位是比较稀疏的，因此默认用数组就好。 通过这样的分析，相信你也会更好地理解，roaring bitmap也并不是万能的银弹，在数据稠密的情况下，其实直接使用位图是更好的选择。
2020-06-091