1.Lucene解析 - IndexWriter
2.Elasticsearch之存储原理
3.Elasticsearch学习总结之二：lucene的源码segment
4.lucene 全文检索原理和流程
5.Lucene SegmentReader：深入分析 I
6.Elasticsearch为啥这么快

Lucene解析 - IndexWriter

       在上篇文章我们介绍了Lucene的基本概念，接下来本文将深入探讨Lucene的源码核心组件之一，即IndexWriter，源码让我们一起来探索数据写入和索引构建的源码过程。

       IndexWriter作为Lucene中用于数据写入的源码核心类，提供了数据写入的源码wglswapbuffers源码简洁流程，主要分为三个步骤。源码通过这个类，源码我们可以轻松地将数据写入并构建索引，源码其设计理念在于为普通用户提供了低门槛的源码使用体验，同时高级用户也能通过配置参数实现性能优化和功能定制。源码

       IndexWriter配置提供了关键参数，源码供高级用户进行性能调优和功能定制。源码这些核心参数包括但不限于缓存大小、源码分段策略、源码写入模式等，为用户提供灵活性。

       为了更深入理解IndexWriter，本节将介绍其提供的主要操作接口。这些接口包括添加文档、箱顶判断源码更新文档、删除文档和提交操作，它们构成IndexWriter的核心功能。接下来，我们将通过一系列图示和解释，解析IndexWriter的内部数据处理流程。

       在IndexWriter内部，数据处理流程被高度优化，以支持多线程并发写入。通过引入DocumentsWriterPerThread（DWPT）机制，每个线程都有独立的空间进行数据处理，这大大提高了并发性能。DWPT内部包含一个内存缓冲区，缓冲区内的数据最终会被flush到不同的独立segment文件中。

       并发模型的设计使得多线程写入性能显著提升，尤其是针对新增文档的场景，提高了数据写入效率。对于删除文档操作，Lucene采用了一种特殊的wmp.dll源码交互方式来降低锁的开销，使得整个流程更加高效。

       在搜索场景中，全量构建索引时，数据写入主要为新增文档；而在增量索引阶段，会涉及大量更新和删除操作。最佳实践是将具有相同唯一主键Term的文档分配给相同的线程进行处理，以避免跨线程冲突。

       添加和更新操作涉及将文档写入内存缓冲区，随后通过特定流程进行处理。删除操作则通过构建全局和独立的删除队列，以及更新live docs位图来实现，确保数据的有效管理和回收。

       flush操作用于将内存缓冲区中的数据持久化到文件，该过程由FlushPolicy自动触发或通过IndexWriter手动执行。commit动作则强制执行数据flush，并生成commit点，确保在搜索时可以访问已提交的数据。

       merge操作则用于合并segment文件，提高查询效率和回收已被删除的淘宝wap网站源码文档。此过程在segment flush时自动触发或通过IndexWriter强制执行。

       IndexingChain概念揭示了Lucene内部索引构建的链式流程。它涉及多个不同类型的索引构建，如倒排、store fields、doc values和point values。这些索引类型根据其功能和需求，使用不同的数据结构和存储方式。

       通过Codec配置，用户可以为不同类型的索引选择不同的编码和解码实现，支持了索引构建的灵活性和可扩展性。Codec参数的配置允许用户优化索引构建性能，满足特定应用需求。

       总结而言，本文从全局视角深入探讨了IndexWriter的配置、接口、并发模型、核心操作的数据路径以及索引链的概念。接下来的新浪床图源码文章将继续深入研究索引链中每种不同类型索引的构建流程，包括memory-buffer的实现、索引算法以及数据存储格式等。

Elasticsearch之存储原理

        倒排索引被写入磁盘后是不可变的，ES解决不变性和更新索引的方式是使用多个索引，利用新增的索引来反映修改，在查询时从旧的到新的依次查询，最后来一个结果合并。

        ES底层是基于Lucene，最核心的概念就是Segment(段)，每个段本身就是一个倒排索引。

        ES中的Index由多个段的集合和commit point(提交点)文件组成。

        提交点文件中有一个列表存放着所有已知的段，下面是一个带有1个提交点和3个段的Index示意图：

        Doc会先被搜集到内存中的Buffer内，这个时候还无法被搜索到，如下图所示：

        每隔一段时间，会将buffer提交，在flush磁盘后打开新段使得搜索可见，详细过程如下：

        下面展示了这个过程完成后的段和提交点的状态：

        通过这种方式，可以使得新文档从被索引到可被搜索间的时间间隔在数分钟，但是还不够快。因为磁盘需要 fsync ，这个就成为性能瓶颈。我们前面提到过Doc会先被从buffer刷入段写入文件系统缓存（很快），那么就自然想到在这个阶段就让文档对搜索可见，随后再被刷入磁盘（较慢）。

        Lucene支持对新段写入和打开，可以使文档在没有完全刷入硬盘的状态下就能对搜索可见，而且是一个开销较小的操作，可以频繁进行。

        下面是一个已经将Docs刷入段，但还没有完全提交的示意图：

        我们可以看到，新段虽然还没有被完全提交，但是已经对搜索可见了。

        引入refresh操作的目的是提高ES的实时性，使添加文档尽可能快的被搜索到，同时又避免频繁fsync带来性能开销，依靠的就是文件系统缓存OS cache里缓存的文件可以被打开(open/reopen)和读取，而这个os cache实际是一块内存区域，而非磁盘，所以操作是很快的，这就是ES被称为近实时搜索的原因。

        refresh默认执行的间隔是1秒，可以使用 refreshAPI 进行手动操作，但一般不建议这么做。还可以通过合理设置 refresh_interval 在近实时搜索和索引速度间做权衡。

        index segment刷入到os cache后就可以打开供查询，这个操作是有潜在风险的，因为os cache中的数据有可能在意外的故障中丢失，而此时数据必备并未刷入到os disk，此时数据丢失将是不可逆的，这个时候就需要一种机制，可以将对es的操作记录下来，来确保当出现故障的时候，已经落地到磁盘的数据不会丢失，并在重启的时候可以从操作记录中将数据恢复过来。elasticsearch提供了translog来记录这些操作，结合os cached segments数据定时落盘来实现数据可靠性保证（flush）。

        文档被添加到buffer同时追加到translog：

        进行 refresh 操作，清空buffer，文档可被搜索但尚未 flush 到磁盘。translog不会清空：

        每隔一段时间（例如translog变得太大），index会被flush到磁盘，新的translog文件被创建，commit执行结束后，会发生以下事件：

        下面示意图展示了这个状态：

        translog记录的是已经在内存生成(segments)并存储到os cache但是还没写到磁盘的那些索引操作（注意，有一种解释说，添加到buffer中但是没有被存入segment中的数据没有被记录到translog中，这依赖于写translog的时机，不同版本可能有变化，不影响理解），此时这些新写入的数据可以被搜索到，但是当节点挂掉后这些未来得及落入磁盘的数据就会丢失，可以通过trangslog恢复。

        当然translog本身也是磁盘文件，频繁的写入磁盘会带来巨大的IO开销，因此对translog的追加写入操作的同样操作的是os cache，因此也需要定时落盘（fsync）。translog落盘的时间间隔直接决定了ES的可靠性，因为宕机可能导致这个时间间隔内所有的ES操作既没有生成segment磁盘文件，又没有记录到Translog磁盘文件中，导致这期间的所有操作都丢失且无法恢复。

        translog的fsync是ES在后台自动执行的，默认是每5秒钟主动进行一次translog fsync，或者当translog文件大小大于MB主动进行一次fsync，对应的配置是 index.translog.flush_threshold_period 和 index.translog.flush_threshold_size 。

        当 Elasticsearch 启动的时候， 它会从磁盘中使用最后一个提交点去恢复已知的段，并且会重放 translog 中所有在最后一次提交后发生的变更操作。

        translog 也被用来提供实时 CRUD 。当你试着通过ID来RUD一个Doc，它会在从相关的段检索之前先检查 translog 中最新的变更。

        默认 translog 是每5秒或是每次请求完成后被 fsync 到磁盘（在主分片和副本分片都会）。也就是说，如果你发起一个index, delete, update, bulk请求写入translog并被fsync到主分片和副本分片的磁盘前不会反回状态。

        这样会带来一些性能损失，可以通过设为异步fsync，但是必须接受由此带来的丢失少量数据的风险：

        flush 就是执行commit清空、干掉老translog的过程。默认每个分片分钟或者是translog过于大的时候自动flush一次。可以通过flush API手动触发，但是只会在重启节点或关闭某个索引的时候这样做，因为这可以让未来ES恢复的速度更快(translog文件更小)。

        满足下列条件之一就会触发冲刷操作：

        整体流程：

        删除一个ES文档不会立即从磁盘上移除，它只是被标记成已删除。因为段是不可变的，所以文档既不能从旧的段中移除，旧的段也不能更新以反映文档最新的版本。

        ES的做法是，每一个提交点包括一个 .del 文件（还包括新段），包含了段上已经被标记为删除状态的文档。所以，当一个文档被做删除操作，实际上只是在 .del 文件中将该文档标记为删除，依然会在查询时被匹配到，只不过在最终返回结果之前会被从结果中删除。ES将会在用户之后添加更多索引的时候，在后台进行要删除内容的清理。

        文档的更新操作和删除是类似的：当一个文档被更新，旧版本的文档被标记为删除，新版本的文档在新的段中索引。

        该文档的不同版本都会匹配一个查询，但是较旧的版本会从结果中删除。

        通过每秒自动刷新创建新的段，用不了多久段的数量就爆炸了，每个段消费大量文件句柄，内存，cpu资源。更重要的是，每次搜索请求都需要依次检查每个段。段越多，查询越慢。

        ES通过后台合并段解决这个问题。ES利用段合并的时机来真正从文件系统删除那些version较老或者是被标记为删除的文档。被删除的文档（或者是version较老的）不会再被合并到新的更大的段中。

        可见，段合并主要有两个目的：

        ES对一个不断有数据写入的索引处理流程如下：

        合并过程如图：

        从上图可以看到，段合并之前，旧有的Commit和没Commit的小段皆可被搜索。

        段合并后的操作:

        合并完成后新的段可被搜索，旧的段被删除，如下图所示：

        注意：段合并过程虽然看起来很爽，但是大段的合并可能会占用大量的IO和CPU，如果不加以控制，可能会大大降低搜索性能。段合并的optimize API 不是非常特殊的情况下千万不要使用，默认策略已经足够好了。不恰当的使用可能会将你机器的资源全部耗尽在段合并上，导致无法搜索、无法响应。

Elasticsearch学习总结之二：lucene的segment

       在深入学习Elasticsearch之后，我们继续探讨其底层关键技术之一：lucene的segment。首先，我们要理解LSM（Log Structured Merge Trees）的原理，它是一种被广泛应用在HBase、Cassandra等产品中的文件结构策略，旨在提高写操作的吞吐量，通过消除随机更新来优化性能。

       LSM的核心思想在于将数据写入过程转化为顺序操作，避免随机写入的性能瓶颈。LSM树包含三个关键组件：内存中的MemTable，它有序存储最近更新的数据，通过WAL保证数据可靠性；当MemTable达到一定大小，会变为Immutable MemTable，继续写操作并为持久化做准备；最后是SSTable（Sorted String Table），磁盘上的有序数据结构，通过索引和布隆过滤器提高查找效率。

       LSM树的设计虽然极大地提高了写性能，但可能导致冗余存储和读取时的复杂性。为此，Elasticsearch中的Segment借鉴了LSM的思想，但对查询性能有所妥协。Segment是Lucene中独立的索引单元，包含完整的正向和反向索引，可以独立搜索，但数据一旦写入就不可更改，提供的是近实时而非实时查询。

       Elasticsearch的Segment设计是为了平衡数据处理和搜索速度，它将数据缓冲在内存中，直到达到刷新周期才写入Segment。这样可以减少IO操作，但可能导致数据丢失。为保证数据可靠性，Elasticsearch使用Translog记录所有操作，但只有在配置的条件满足时才将数据同步到磁盘，因此需要理解Translog和fsync参数的配置以确保数据持久性。

lucene 全文检索原理和流程

       Lucene, 作为Java的高效全文检索库，其核心原理是通过创建索引和搜索索引两个流程，实现对非结构化数据的快速查找。在大数据背景下，索引技术至关重要，它将数据结构化，通过分词、语言处理和索引构建，提高查找效率。

       索引创建流程包括：将文档导入Lucene，分词器对文档进行处理，去除停用词并生成词元；接着，词元通过语言处理组件进行词形还原等操作，形成词(Term)。这些词(Term)被传给索引组件，构建字典并进行排序，形成倒排索引。

       存储方面，Lucene支持将索引数据存储在本地，且具有层次结构，包含正向信息（文档中的词频）和反向信息（词与文档的关系）。段(Segment)控制策略通过设置MaxMergeDocs和MinMergeDocs影响性能，而搜索过程则涉及查询分析、语言处理、在倒排索引中查找相关文档、权重计算和向量空间模型的应用，以找出与查询语句最相关的结果。

       具体来说，搜索流程包括：解析用户输入的查询语句，通过词法分析和语法处理转化为搜索请求；在索引中找到与查询词相关的文档链表，合并并排除无关文档；根据词的权重和向量空间模型计算文档间的相关性，最后按照相关性排序返回结果。

Lucene SegmentReader：深入分析 I

       Lucene的SegmentReader深入解析中，核心是理解和管理索引的多个段（segment_N文件）及其元数据（segments.gen）。索引通常由多个小段组成，这些段会在后台通过merge操作合并成大段以优化查询效率。每个段文件（如segment_3）代表了某个索引提交时刻的状态，其内容由SegmentInfo中的文件列表定义。

       在IndexWriter#flush后，新的文档会被添加到一个新的segment_N文件中，并将所有相关段的元信息写入该文件。同时，segments.gen文件会更新最大段号。选择哪个段进行查询时，通常会选择包含最多文档的段，且其元信息中包含了其他段的信息。

       SegmentReader的创建流程分为两种情况：如果只有一个段，会直接实例化SegmentReader；若有多段，则会创建MultiSegmentReader，内部包含多个SegmentReader实例。每个SegmentInfo都会生成一个SegmentReader对象，负责读取段的文件信息。SegmentReader的初始化过程虽然对于大索引可能耗时，因此建议尽量减少索引的频繁打开和关闭。下面是这部分的详细过程：

       Lucene索引通过segments.gen和segment_N文件管理多个段，每个段文件记录一个提交时刻的状态。flush操作时，新文档会增加到新的segment_N，同时更新元信息和最大段号。选择段时，倾向于选择包含最多文档的。

       SegmentReader的创建涉及单段或多段场景：单段直接实例化，多段则用MultiSegmentReader聚合。每个SegmentInfo对应一个SegmentReader，负责读取文件信息。SegmentReader初始化是耗时操作，应避免频繁打开关闭索引。

Elasticsearch为啥这么快

       æ€è€ƒå‡ ä¸ªé—®é¢˜ï¼š

        这里有篇 文章 讲解的很形象：

        这是集群cluster。

        这是节点Node：就是个机器。

        由一个或者多个节点，多个绿色小方块组合在一起形成一个ElasticSearch的索引。

        在一个索引下，分布在多个节点里的绿色小方块称为分片：Shard。

        一个分片就是一个Lucene Index。

        在Lucene里面有很多小的Segment，即为存储的最小管理单元。

        我们分别从Node维度、Shard维度、Segment维度来阐明为啥Elasticsearch这么快。

        多节点的集群方案，提高了整个系统的并发处理能力。

        路由一个文档到一个分片中：当索引一个文档的时候，文档会被存储到一个主分片中。 Elasticsearch 如何知道一个文档应该存放到哪个分片中呢？实际上，这个过程是根据下面这个公式决定的：

        routing 是一个可变值，默认是文档的 _id ，也可以设置成一个自定义的值。这就解释了为什么我们要在创建索引的时候就确定好主分片的数量，并且永远不会改变这个数量：因为如果数量变化了，那么所有之前路由的值都会无效，文档也再也找不到了。

        确定了在哪个分片中，继而可以判定其在哪个节点上。

        那么主分片数确定的情况下，如果做集群扩容呢？下图是一种主分片的扩容办法，开始设置为5个分片，在单个节点上，后来扩容到5个节点，每个节点有一个分片。也就是说单个分片的容量变大了，但是数量并不增加。

        节点分为主节点 Master Node、数据节点 Data Node和客户端节点 Client Node（单纯为了做请求的分发和汇总）。每个节点都可以接受客户端的请求，每个节点都知道集群中任一文档位置，所以可以直接将请求转发到需要的节点上。当接受请求后，节点变为「协调节点」。从这个角度，整个系统可以接受更高的并发请求，当然搜索的就更快了。

        以更新文档为例：

        Elasticsearch 中使用的这种方法假定冲突是不可能发生的，并且不会阻塞正在尝试的操作。因为没有阻塞，所以提升了索引的速度，同时可以通过 _version 字段来保证并发情况下的正确性：

        控制在我们索引中的文档只有现在的 _version 为 1 时，本次更新才能成功。

        可以设置分片的副本数量来提升高并发场景下的搜索速度，但是同时会降低索引的效率。

        在底层采用了分段的存储模式，使它在读写时几乎完全避免了锁的出现，大大提升了读写性能。

        怎样在保留不变性的前提下实现倒排索引的更新？即用上文提到的 _version ，创建更多的索引文档。实际上一个 UPDATE 操作包含了一次 DELETE 操作（仅记录标志待Segment Merge 的时候才真正删除）和一次 CREATE 操作。

        为了提升写索引速度，并且同时保证可靠性，Elasticsearch 在分段的基础上，增加了一个 translog ，或者叫事务日志，在每一次对 Elasticsearch 进行操作时均进行了日志记录。

        Segment在被refresh之前，数据保存在内存中，是不可被搜索的，这也就是为什么 Lucene 被称为提供近实时而非实时查询的原因。

        但是如上这种机制避免了随机写，数据写入都是 Batch 和 Append，能达到很高的吞吐量。同时为了提高写入的效率，利用了文件缓存系统和内存来加速写入时的性能，并使用日志来防止数据的丢失。

        LSM-Tree 示意图如下，可见 Lucene 的写入思想和 LSM-Tree 是一致的：

        终于说到倒排索引了，都说倒排索引提升了搜索的速度，那么具体采用了哪些架构或者数据结构来达成这一目标？

        如上是Lucene中实际的索引结构。用例子来说明上述三个概念：

        ID是文档id，那么建立的索引如下:

        Name：

        Age：

        Sex：

        可见为每个 field 都建立了一个倒排索引。Posting list就是一个int的数组，存储了所有符合某个term的文档id。实际上，除此之外还包含：文档的数量、词条在每个文档中出现的次数、出现的位置、每个文档的长度、所有文档的平均长度等，在计算相关度时使用。

        假设我们有很多个 term，比如：

        如果按照这样的顺序排列，找出某个特定的 term 一定很慢，因为 term 没有排序，需要全部过滤一遍才能找出特定的 term。排序之后就变成了：

        这样我们可以用二分查找的方式，比全遍历更快地找出目标的 term。这个就是 term dictionary。有了 term dictionary 之后，可以用 logN 次磁盘查找得到目标。

        但是磁盘的随机读操作仍然是非常昂贵的（一次 random access 大概需要 ms 的时间）。所以尽量少的读磁盘，有必要把一些数据缓存到内存里。但是整个 term dictionary 本身又太大了，无法完整地放到内存里。于是就有了 term index。term index 有点像一本字典的大的章节表。比如：

        A 开头的 term ……………. Xxx 页

        C 开头的 term ……………. Yyy 页

        E 开头的 term ……………. Zzz 页

        如果所有的 term 都是英文字符的话，可能这个 term index 就真的是 个英文字符表构成的了。但是实际的情况是，term 未必都是英文字符，term 可以是任意的 byte 数组。而且 个英文字符也未必是每一个字符都有均等的 term，比如 x 字符开头的 term 可能一个都没有，而 s 开头的 term 又特别多。实际的 term index 是一棵 trie 树：

        例子是一个包含 "A", "to", "tea", "ted", "ten", "i", "in", 和 "inn" 的 trie 树。这棵树不会包含所有的 term，它包含的是 term 的一些前缀。通过 term index 可以快速地定位到 term dictionary 的某个 offset，然后从这个位置再往后顺序查找。

        现在我们可以回答“为什么 Elasticsearch/Lucene 检索可以比 mysql 快了。Mysql 只有 term dictionary 这一层，是以 b-tree 排序的方式存储在磁盘上的。检索一个 term 需要若干次的 random access 的磁盘操作。而 Lucene 在 term dictionary 的基础上添加了 term index 来加速检索，term index 以树的形式缓存在内存中。从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。

        实际上，Lucene 内部的 Term Index 是用的「变种的」trie树，即 FST 。FST 比 trie树好在哪？trie树只共享了前缀，而 FST 既共享前缀也共享后缀，更加的节省空间。

        一个FST是一个6元组 (Q, I, O, S, E, f):

        例如有下面一组映射关系：

        可以用下图中的FST来表示：

        这篇文章讲的很好： 关于Lucene的词典FST深入剖析

        想想为啥不用 HashMap，HashMap 也能实现有序Map？耗内存啊！牺牲了一点性能来节约内存，旨在把所有Term Index都放在内存里面，最终的效果是提升了速度。如上可知，FST是压缩字典树后缀的图结构，她拥有Trie高效搜索能力，同时还非常小。这样的话我们的搜索时，能把整个FST加载到内存。

        总结一下，FST有更高的数据压缩率和查询效率，因为词典是常驻内存的，而 FST 有很好的压缩率，所以 FST 在 Lucene 的最新版本中有非常多的使用场景，也是默认的词典数据结构。

        Lucene 的tip文件即为 Term Index 结构，tim文件即为 Term Dictionary 结构。由图可视，tip中存储的就是多个FST，

        FST中存储的是<单词前缀，以该前缀开头的所有Term的压缩块在磁盘中的位置>。即为前文提到的从 term index 查到对应的 term dictionary 的 block 位置之后，再去磁盘上找 term，大大减少了磁盘的 random access 次数。

        可以形象地理解为，Term Dictionary 就是新华字典的正文部分包含了所有的词汇，Term Index 就是新华字典前面的索引页，用于表明词汇在哪一页。

        但是 FST 即不能知道某个Term在Dictionary(.tim)文件上具体的位置，也不能仅通过FST就能确切的知道Term是否真实存在。它只能告诉你，查询的Term可能在这些Blocks上，到底存不存在FST并不能给出确切的答案，因为FST是通过Dictionary的每个Block的前缀构成，所以通过FST只可以直接找到这个Block在.tim文件上具体的File Pointer，并无法直接找到Terms。

        回到上面的例子，给定查询过滤条件 age= 的过程就是先从 term index 找到 在 term dictionary 的大概位置，然后再从 term dictionary 里精确地找到 这个 term，然后得到一个 posting list 或者一个指向 posting list 位置的指针。然后再查询 sex=Female 的过程也是类似的。最后得出 age= AND sex=Female 就是把两个 posting list 做一个“与”的合并。

        这个理论上的“与”合并的操作可不容易。对于 mysql 来说，如果你给 age 和 gender 两个字段都建立了索引，查询的时候只会选择其中最 selective 的来用，然后另外一个条件是在遍历行的过程中在内存中计算之后过滤掉。那么要如何才能联合使用两个索引呢？有两种办法：

        Elasticsearch 支持以上两种的联合索引方式，如果查询的 filter 缓存到了内存中（以 bitset 的形式），那么合并就是两个 bitset 的 AND。如果查询的 filter 没有缓存，那么就用 skip list 的方式去遍历两个 on disk 的 posting list。

        用一个例子来说明如何使用 skip list 的思路来做合并（参考 Lucene学习总结之七：Lucene搜索过程解析(5) ）：

        Advance操作是什么？就是 skip list 提供的快速跳跃的特性。

        另外一方面，对于一个很长的 posting list，比如：

        [1,3,,,,,,,]

        我们可以把这个 list 分成三个 block：

        [1,3,] [,,] [,,]

        然后可以构建出 skip list 的第二层：

        [1,,]

        1,, 分别指向自己对应的 block。这样就可以很快地跨 block 的移动指向位置了。

        Lucene 自然会对这个 block 再次进行压缩。其压缩方式叫做 Frame Of Reference 编码。示例如下：

        考虑到频繁出现的 term（所谓 low cardinality 的值），比如 gender 里的男或者女。如果有 1 百万个文档，那么性别为男的 posting list 里就会有 万个 int 值。用 Frame of Reference 编码进行压缩可以极大减少磁盘占用。这个优化对于减少索引尺寸有非常重要的意义。当然 mysql b-tree 里也有一个类似的 posting list 的东西，是未经过这样压缩的。

        因为这个 Frame of Reference 的编码是有解压缩成本的。利用 skip list，除了跳过了遍历的成本，也跳过了解压缩这些压缩过的 block 的过程，从而节省了 cpu。

        这也可以看到，Lucene 为了省内存真是做到了极致。

        Bitset 是一种很直观的数据结构，对应 posting list 如：

        [1,3,4,7,]

        对应的 bitset 就是：

        [1,0,1,1,0,0,1,0,0,1]

        每个文档按照文档 id 排序对应其中的一个 bit。Bitset 自身就有压缩的特点，其用一个 byte 就可以代表 8 个文档。所以 万个文档只需要 .5 万个 byte。但是考虑到文档可能有数十亿之多，在内存里保存 bitset 仍然是很奢侈的事情。而且对于个每一个 filter 都要消耗一个 bitset，比如 age= 缓存起来的话是一个 bitset，<=age< 是另外一个 filter 缓存起来也要一个 bitset。

        所以秘诀就在于需要有一个数据结构：

        可以很压缩地保存上亿个 bit 代表对应的文档是否匹配 filter；

        这个压缩的 bitset 仍然可以很快地进行 AND 和 OR 的逻辑操作。

        Lucene 使用的这个数据结构叫做 Roaring Bitmap。

        其压缩的思路其实很简单。与其保存 个 0，占用 个 bit。还不如保存 0 一次，然后声明这个 0 重复了 遍。

        为什么是以为界限？程序员的世界里除了外，也是一个经典值，因为它=2^-1，正好是用2个字节能表示的最大数，一个short的存储单位，注意到上图里的最后一行“If a block has more than values, encode as a bit set, and otherwise as a simple array using 2 bytes per value”，如果是大块，用节省点用bitset存，小块就豪爽点，2个字节我也不计较了，用一个short[]存着方便。

        在 Lucene 7.0之后，Lucene 针对 bitset的稠稀性，采用不同的存储方式：当 bitset比较稀疏时，直接存储DocID；当 bitset 稠密时，则直接存储 bitset 的Bits数据。根据数据的分布情况不同，采用适当的结构不仅可以提高空间的利用率，还能提高遍历的效率。

        Elasticsearch/Lucene 为了提升索引和搜索的效率，从上层到底层，使用了各种巧妙的数据结构和设计，靠优秀的理论加极致的优化，做到查询性能上的极致。