倒排索引

如上图，这个倒排索引使用哈希表来实现也是可以的，其有着 O(1) 查询复杂度，能完美地满足我们的需求。但是呢，现实中数据往往是海量的，如果简单地使用哈希表来实现倒排索引是不可行的，因为存储海量的数据时，系统将会面临下面几个问题：

• 分词形成的词项（term）可能是海量的，需要可以在内存和磁盘上高效存储；
• 既然词项是海量的，那么如何快速找到对应的词项也是个问题；
• 每个词项对应的文档数可能非常多，也就是上图中文档列表的链表很长；
• 在词项对应的文档多的情况下，多个文档列表间做交集的效率将是个挑战。

其实这四个问题可以分为两个方面：词项方面的问题和文档列表方面的问题。在 Lucene 的倒排索引的实现中，其使用词项索引（Term Index）来解决上述 1 和 2 的问题，而对于 3 和 4，Lucene 对数据进行了压缩处理，使用 Roaring Bitmaps、跳表等技术来进行快速求交集。在面对海量的数据时，系统的设计往往都是非常复杂的，我将在下篇来介绍倒排索引的实现，并且看看这些问题是如何解决的。