php编码 [精选] Elasticsearch 是如何做到快速检索的？
OK，现在我们能得到 lucene 倒排索引大致是个什么样子的了。
关于 postings list 的一些巧技
在实际使用中，postings list 还需
OK，现在我们能得到 lucene 倒排索引大致是个什么样子的了。
关于 postings list 的一些巧技 在实际使用中，postings list 还需要解决几个痛点： 对于如何压缩，可能会有人觉得没有必要，”posting list 不是已经只存储文档 id 了吗？还需要压缩？”，但是如果在 posting list 有百万个 doc id 的情况，压缩就显得很有必要了。 比如按照朝代查询古诗，至于为啥需要求交并集，ES 是专门用来搜索的，肯定会有很多联合查询的需求吧 （AND、OR）。按照上面的思路，我们先将如何压缩。 ①压缩 Frame of Reference：在 lucene 中，要求 postings lists 都要是有序的整形数组。 这样就带来了一个很好的好处，可以通过 增量编码（delta-encode）这种方式进行压缩。 比如现在有 id 列表[73, 300, 302, 332, 343, 372]，转化成每一个 id 相对于前一个 id 的增量值（第一个 id 的前一个 id 默认是 0，增量就是它自己）列表是 [73, 227, 2, 30, 11, 29]。 在这个新的列表里面，所有的 id 都是小于 255 的，所以每个 id 只需要一个字节存储。 实际上 ES 会做的更加精细：
它会把所有的文档分成很多个 block，每个 block 正好包含 256 个文档，然后单独对每个文档进行增量编码。 计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id，并且把这个位数作为头信息（header）放在每个 block 的前面。这个技术叫 Frame of Reference。 上图也是来自于 ES 官方博客中的一个示例（假设每个 block 只有 3 个文件而不是 256）。 FOR 的步骤可以总结为：
进过最后的位压缩之后，整型数组的类型从固定大小（8，16，32，64 位）4 种类型，扩展到了 [1-64] 位共 64 种类型。 通过以上的方式可以极大的节省 posting list 的空间消耗，提高查询性能。不过 ES 为了提高 filter 过滤器查询的性能，还做了更多的工作，那就是缓存。 Roaring Bitmaps (for filter cache)：在 ES 中，可以使用 filters 来优化查询，filter 查询只处理文档是否匹配与否，不涉及文档评分操作，查询的结果可以被缓存。 对于 filter 查询，es 提供了 filter cache 这种特殊的缓存，filter cache 用来存储 filters 得到的结果集。 缓存 filters 不需要太多的内存，它只保留一种信息，即哪些文档与 filter 相匹配。同时它可以由其它的查询复用，极大地提升了查询的性能。 我们上面提到的 Frame Of Reference 压缩算法对于 postings list 来说效果很好，但对于需要存储在内存中的 filter cache 等不太合适。 filter cache 会存储那些经常使用的数据，针对 filter 的缓存就是为了加速处理效率，对压缩算法要求更高。 对于这类 postings list，ES 采用不一样的压缩方式。那么让我们一步步来。首先我们知道 postings list 是 Integer 数组，具有压缩空间。 假设有这么一个数组，我们第一个压缩的思路是什么？用位的方式来表示，每个文档对应其中的一位，也就是我们常说的位图，bitmap。 它经常被作为索引用在数据库、查询引擎和搜索引擎中，并且位操作（如 and 求交集、or 求并集）之间可以并行，效率更好。
但是，位图有个很明显的缺点，不管业务中实际的元素基数有多少，它占用的内存空间都恒定不变。 也就是说不适用于稀疏存储。业内对于稀疏位图也有很多成熟的压缩方案，lucene 采用的就是 roaring bitmaps。 我这里用简单的方式描述一下这个压缩过程是怎么样：
将 doc id 拆成高 16 位，低 16 位。对高位进行聚合 (以高位做 key，value 为有相同高位的所有低位数组)，根据低位的数据量 (不同高位聚合出的低位数组长度不相同)，使用不同的 container(数据结构) 存储。 分界线的来源：value 的最大总数是为2^16=65536. 假设以 bitmap 方式存储需要 65536bit=8kb，而直接存值的方式，一个值 2 byte，4K 个总共需要2byte*4K=8kb。 所以当 value 总量
空间压缩主要体现在： 缺点就在于位操作的速度相对于原生的 bitmap 会有影响。这就是 trade-off 呀。平衡的艺术。 ②联合查询讲完了压缩，我们再来讲讲联合查询。先讲简单的，如果查询有 filter cache，那就是直接拿 filter cache 来做计算，也就是说位图来做 AND 或者 OR 的计算。 如果查询的 filter 没有缓存，那么就用 skip list 的方式去遍历磁盘上的 postings list。
以上是三个 posting list。我们现在需要把它们用 AND 的关系合并，得出 posting list 的交集。 首先选择最短的 posting list，逐个在另外两个 posting list 中查找看是否存在，最后得到交集的结果。 遍历的过程可以跳过一些元素，比如我们遍历到绿色的 13 的时候，就可以跳过蓝色的 3 了，因为 3 比 13 要小。
用 skip list 还会带来一个好处，还记得前面说的吗，postings list 在磁盘里面是采用 FOR 的编码方式存储的。 会把所有的文档分成很多个 block，每个 block 正好包含 256 个文档，然后单独对每个文档进行增量编码，计算出存储这个 block 里面所有文档最多需要多少位来保存每个 id，并且把这个位数作为头信息（header）放在每个 block 的前面。 因为这个 FOR 的编码是有解压缩成本的。利用 skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的 block 的过程，从而节省了 cpu。 总结 下面我们来做一个技术总结：①为了能够快速定位到目标文档，ES 使用倒排索引技术来优化搜索速度，虽然空间消耗比较大，但是搜索性能提高十分显著。 ②为了能够在数量巨大的 terms 中快速定位到某一个 term，同时节约对内存的使用和减少磁盘 io 的读取。 lucene 使用 "term index→term dictionary→postings list" 的倒排索引结构，通过 FST 压缩放入内存，进一步提高搜索效率。 ③为了减少 postings list 的磁盘消耗，lucene 使用了 FOR（Frame of Reference）技术压缩，带来的压缩效果十分明显。 ④ES 的 filter 语句采用了 Roaring Bitmap 技术来缓存搜索结果，保证高频 filter 查询速度的同时降低存储空间消耗。 ⑤在联合查询时，在有 filter cache 的情况下，会直接利用位图的原生特性快速求交并集得到联合查询结果，否则使用 skip list 对多个 postings list 求交并集，跳过遍历成本并且节省部分数据的解压缩 cpu 成本。 Elasticsearch 的索引思路 将磁盘里的东西尽量搬进内存，减少磁盘随机读取次数 (同时也利用磁盘顺序读特性)，结合各种压缩算法，用及其苛刻的态度使用内存。 所以，对于使用 Elasticsearch 进行索引时需要注意: 最后说一下，技术选型永远伴随着业务场景的考量，每种数据库都有自己要解决的问题（或者说擅长的领域），对应的就有自己的数据结构，而不同的使用场景和数据结构，需要用不同的索引，才能起到最大化加快查询的目的。 这篇文章讲的虽是 Lucene 如何实现倒排索引，如何精打细算每一块内存、磁盘空间、如何用诡谲的位运算加快处理速度。 但往高处思考，再类比一下 MySQL，你就会发现，虽然都是索引，但是实现起来，截然不同。笼统的来说，B-tree 索引是为写入优化的索引结构。 当我们不需要支持快速的更新的时候php编码，可以用预先排序等方式换取更小的存储空间，更快的检索速度等好处，其代价就是更新慢，就像 ES。 原文链接：以上就是本篇分钟的全部内容，希望各位程序员们努力提升个人技术。最后，小编温馨提示：每天阅读5分钟，每天学习一点点，每天进步一点点。
点个赞 再走吧 （编辑：晋中站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
