Lucene核心数据结构——FST存词典,跳表存倒排或者roarning bitmap 见另外一个文章-阿里云开发者社区

开发者社区> 桃子红了呐> 正文

Lucene核心数据结构——FST存词典,跳表存倒排或者roarning bitmap 见另外一个文章

简介:
+关注继续查看

Lucene实现倒排表没有使用bitmap,为了效率,lucene使用了一些策略,具体如下:
1. 使用FST保存词典,FST可以实现快速的Seek,这种结构在当查询可以表达成自动机时(PrefixQuery、FuzzyQuery、RegexpQuery等)效率很高。(可以理解成自动机取交集)
此种场景主要用在对Query进行rewrite的时候。
2. FST可以表达出Term倒排表所在的文件偏移。
3. 倒排表使用SkipList结构。从上面的讨论可知,求倒排表的交集、并集、差集需要各种SeekTo(docId),SkipList能对Seek进行加速。

 

skiplist备忘

   如今大部分工具使用的倒排链已经不是简单的链表了。一个常用,比如lucene中用的,叫skiplist,是一种高效的链表结构,在查询、添加、删除的时间复杂度上做到O(logN)。数据结构如下图:

查询的过程很简单,从顶层开始,往后查询遇到节点的next()比待查的大或者到NIL了,节点不变下移一层继续向后查询,如此反复,直到到了底层还没查到。skiplist的资料也比较多,这里就不赘述了。

 

链表集合操作

   直接引用转述这篇博文:http://www.cnblogs.com/forfuture1978/archive/2010/04/04/1704258.html  。作者很细致地把过程都列出来了,真是方便了大家啊,建议顺着读一边。

    链表集合求交 

      lucene中用的是ConjunctionScorer ,大致过程是每条倒排链不断的推进到小于等于当前最大节点的位置。当然实现细节还是很丰富的,作者很细心的把过程都列出来了,建议顺着读一边。这里摘抄部分:

首先把倒排链按第一个next排序:

    

查看0~7的倒排链的第一个和最后一个是否相同,不同就开始找;取最后一个倒排的第一个元素8作为终点, 第一个链表开始找8

第0个链表 跳过1到了10,那么8也不用找了都去找10就行了

第1根链表找到了11,那么10也不用找了,找11,之后都这么做

......

之后遇到11,本次交集操作找到一个11,

  后续的计算也是同理,当然整个代码实现会比较复杂和讨巧。基本思路就是每条倒排链能根据当前文档迅速跳过不符合的docid,由于倒排链可以用skiplist查询,因此即使很长的倒排链,如果交集的数量很少,整个求解过程可以很快跳过不需要比较的节点。















本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6394451.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9497 0
Java基础-22总结登录注册IO版,数据操作流,内存操作流,打印流,标准输入输出流,转换流,随机访问流,合并流,序列化流,Properties
你需要的是什么,直接评论留言。 获取更多资源加微信公众号“Java帮帮” (是公众号,不是微信好友哦) 还有“Java帮帮”今日头条号,技术文章与新闻,每日更新,欢迎阅读 学习交流请加Java帮帮交流QQ群553841695 分享是一种美德,分享更快乐! 1:登录注册IO版本案例(掌握) 要求,对着写一遍。 cn.i
1727 0
赠票福利 | DTCC 2020数聚英雄,企业级分布式数据库实践专场见!
中国数据库技术大会 DTCC 2020 将在 12.21-23 于北京国际会议中心隆重召开。OceanBase 将在12月21日下午携手山东移动、网商银行等行业伙伴及OB 核心技术及产品团队共同开启 OceanBase 企业级分布式数据库实践专场,从产品创新到客户实践,从能力探讨到价值挖掘, 7大主题演讲,待你与 OceanBase 一同感知数据新视界,精彩干货不容错过!进入文章扫描二维码即可免费获取专场门票,限量50张先到先得哦~
197 0
DTCC 回顾:技术破局,分布式数据库创赢未来
2020 年 12 月 21 日第十一届中国数据库技术大会(DTCC 2020)于北京召开,蚂蚁集团 OceanBase 资深总监、北京奥星贝斯科技研发中心总经理杨传辉,带来了《OceanBase 原生分布式数据库》的主题分享,以下为演讲实录:
928 0
独家 | ARIMA/Sarima与LSTM的时间序列数据集成学习(附链接)
本文探讨了简单的ARIMA/Sarima与LSTM的时间序列数据集成学习方面的问题。
1586 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13186 0
4269
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载