云社区 博客 博客详情

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

山山而川&潺潺成镜 发表于 2020-06-28 19:26:38 2020-06-28
0
2

【摘要】 最近看到圈里一个朋友发了一篇推文,是关于华为云时序数据库influxDB的,之前对时序数据库不太了解,于是顺着这个点去学习了一下,由于接触不多只能浅尝辄止,发现这个倒排索引很有意思,今天就和大家简单聊聊倒排索引。

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

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

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

image.png

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

     image.png

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

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

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

image.png

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

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

image.png

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

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

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

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

2. 有些单词词根是相同的:TestTests 用户认为表达相似的意思。

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

小结

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


登录后可下载附件,请登录或者注册

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请发送邮件至:huaweicloud.bbs@huawei.com;如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
评论文章 //点赞 收藏 2
点赞
分享文章到微博
分享文章到朋友圈

上一篇:轻松读懂MySQL主从复制演进过程

下一篇:SQL Server内存管理小知识

评论 (0)


登录后可评论,请 登录注册

评论