浅谈时序数据库中的倒排索引应用

       最近看到圈里一个朋友发了一篇推文，是关于华为云时序数据库influxDB的，之前对时序数据库不太了解，于是顺着这个点去学习了一下，由于接触不多只能浅尝辄止，总的来说，InfluxDB有两个最关键的模块，一是TSM存储引擎针对时序数据在内存以及文件格式上做了很多优化，实现高效写入以及高压缩率存储，并且文件级的B+树索引可以提高查询时间序列的性能；再就是InfluxDB还实现了内存以及文件级别的倒排索引，可以根据SeriesKey、fieldKey和时间间隔在文件中查询到相应的时序数据集合。这个倒排索引就很有意思，今天就和大家简单聊聊倒排索引。

首先，它和传统B+树索引一样，是一种索引结构。通常在做全文检索时会使用到倒排索引（inverted index）

而且，有倒排索引就应该有对应的正排索引（forward index），要理解倒排索引，先来看下正排索引的含义：在搜索所有文档时，首先针对文档里包含的关键词进行分析，获取到文档中关键词的位置和频率；假如每个文档都有一个ID，例如有以下3个文档：

    一般的正向索引会生成文档ID：关键字1，关键字2格式，例如上面文档经过分词提取了9个关键词，那么正向索引的形式如下:

可以看到文档0中包含了this关键词，（1,1）表示关键词出现了一次，在第一个位置。以上构建的索引就是正排索引。

然而，使用该索引会存在以下问题，当用户在搜索具体某个单词时，比如”inverted”，那么就需要扫描所有的文档，找出是否包含关键字“inverted”的文档，在根据一些其他方法模型进行打分，然后排名后呈现给客户。因为要搜索所有的文档，这种方式显然不能满足实时性要求。小结一下，对正排索引来说，我们的索引(key)是文档，内容(value)是关键字。倒排索引就是反过来：内容关键字作为索引(key)，所在文档作为内容(value)。

因此，在全文搜索引擎中会将正向索引进行重排，构建倒排索引结构。具体原理是，把文件ID对应到关键词的映射转化为关键词到文件ID的映射，每个关键词都对应着一系列包含在关键词的文件。上面的正排索引可以转化为：

可以看到单词this存在于文档0和1中，单词is存在于文档0,1,2中。之后在进行全文查询就简单了，可以直接根据关键词来查询关键词的文档。

以上最简单的倒排索引例子，仅仅包含了是否包括关键词的信息；倒排索引还可以包含关键词的位置信息，单词出现频率等信息，例如

以单词“inverted”为例，文档频率为2，代表整个文档集合中有2个文档包含这个单词，对应的倒排列表为{(1;6;<1>),(2;4;<1>)}，含义是在文档1，2出现过这个单词，在每个文档的出现过1次，单词“inverted”在第一个文档的位置是6，即文档的第6个单词是“inverted”；

有了这个索引索引，搜索引擎可以很方便地响应用户的查询，比如用户输入查询词“inverted”，搜索系统查找倒排索引，从中可以读出包含这个单词的文档，这些文档就是提供给用户的搜索结果，而利用单词频率信息、文档频率信息即可以对这些候选搜索结果进行排序，计算文档和查询的相似性，按照相似性得分由高到低排序输出。

除了上述信息，倒排索引在构建的过程中还有很多其他问题和优化点，例如：

1. 有些单词的大小写区分：Test 和 test 以独立的词条出现，然而用户可能认为它们是相同的词。

2. 有些单词词根是相同的：Test和Tests 用户认为表达相似的意思。

3. 有些单词是同义词：jumped 和 leap, 尽管没有相同的词根，但他们的意思很相近。他们是同义词。

小结

       本文通过一个搜索查询的例子，引出关键词查询的方案，进而浅谈了倒排索引的原理。现代搜索引擎是一个非常庞大和复杂的系统工程，这里的例子只是为了方便大家理解做了特别的简化。