dedecms网站开发,wordpress display_name,网站续费怎么做,中山手机网站建设价格摘要#xff1a; # 前言 Lucene 是一个基于 Java 的全文信息检索工具包#xff0c;目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理#xff0c;就需要深入lucene这一层#xff0c;看看lucene是如何存储需要检索的数…摘要 # 前言 Lucene 是一个基于 Java 的全文信息检索工具包目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理就需要深入lucene这一层看看lucene是如何存储需要检索的数据以及如何完成高效的数据检索。
前言Lucene 是一个基于 Java 的全文信息检索工具包目前主流的搜索系统Elasticsearch和solr都是基于lucene的索引和搜索能力进行。想要理解搜索系统的实现原理就需要深入lucene这一层看看lucene是如何存储需要检索的数据以及如何完成高效的数据检索。在数据库中因为有索引的存在也可以支持很多高效的查询操作。不过对比lucene数据库的查询能力还是会弱很多本文就将探索下lucene支持哪些查询并会重点选取几类查询分析lucene内部是如何实现的。为了方便大家理解我们会先简单介绍下lucene里面的一些基本概念然后展开lucene中的几种数据存储结构理解了他们的存储原理后就可以方便知道如何基于这些存储结构来实现高效的搜索。本文重点关注是lucene如何做到传统数据库较难做到的查询对于分词打分等功能不会展开介绍。本文具体会分以下几部分介绍lucene的数据模型细节可以参阅lucene数据模型一文。介绍lucene中如何存储需要搜索的term。介绍lucene的倒排链的如何存储以及如何实现docid的快速查找。介绍lucene如何实现倒排链合并。介绍lucene如何做范围查询和前缀匹配。介绍lucene如何优化数值类范围查询。Lucene数据模型Lucene中包含了四种基本数据类型分别是Index索引由很多的Document组成。Document由很多的Field组成是Index和Search的最小单位。Field由很多的Term组成包括Field Name和Field Value。Term由很多的字节组成。一般将Text类型的Field Value分词之后的每个最小单元叫做Term。在lucene中读写路径是分离的。写入的时候创建一个IndexWriter而读的时候会创建一个IndexSearcher下面是一个简单的代码示例如何使用lucene的IndexWriter建索引以及如何使用indexSearch进行搜索查询。 Analyzer analyzer new StandardAnalyzer();// Store the index in memory:Directory directory new RAMDirectory();// To store an index on disk, use this instead://Directory directory FSDirectory.open(/tmp/testindex);IndexWriterConfig config new IndexWriterConfig(analyzer);IndexWriter iwriter new IndexWriter(directory, config);Document doc new Document();String text This is the text to be indexed.;doc.add(new Field(fieldname, text, TextField.TYPE_STORED));iwriter.addDocument(doc);iwriter.close();// Now search the index:DirectoryReader ireader DirectoryReader.open(directory);IndexSearcher isearcher new IndexSearcher(ireader);// Parse a simple query that searches for text:QueryParser parser new QueryParser(fieldname, analyzer);Query query parser.parse(text);ScoreDoc[] hits isearcher.search(query, 1000).scoreDocs;//assertEquals(1, hits.length);// Iterate through the results:for (int i 0; i hits.length; i) {Document hitDoc isearcher.doc(hits[i].doc);System.out.println(hitDoc.get(fieldname));}ireader.close();directory.close();从这个示例中可以看出lucene的读写有各自的操作类。本文重点关注读逻辑在使用IndexSearcher类的时候需要一个DirectoryReader和QueryParser其中DirectoryReader需要对应写入时候的Directory实现。QueryParser主要用来解析你的查询语句例如你想查 “A and Blucene内部会有机制解析出是term A和term B的交集查询。在具体执行Search的时候指定一个最大返回的文档数目因为可能会有过多命中我们可以限制单词返回的最大文档数以及做分页返回。下面会详细介绍一个索引查询会经过几步每一步lucene分别做了哪些优化实现。Lucene 查询过程在lucene中查询是基于segment。每个segment可以看做是一个独立的subindex在建立索引的过程中lucene会不断的flush内存中的数据持久化形成新的segment。多个segment也会不断的被merge成一个大的segment在老的segment还有查询在读取的时候不会被删除没有被读取且被merge的segement会被删除。这个过程类似于LSM数据库的merge过程。下面我们主要看在一个segment内部如何实现高效的查询。为了方便大家理解我们以人名字年龄学号为例如何实现查某个名字有重名的列表。docidnameageid1Alice181012Alice201023Alice211034Alan211045Alan18105在lucene中为了查询nameXXX的这样一个条件会建立基于name的倒排链。以上面的数据为例倒排链如下姓名Alice | [1,2,3]---- | --- | Alan | [4,5]如果我们还希望按照年龄查询例如想查年龄18的列表我们还可以建立另一个倒排链18 | [1,5]---| --- | 20 | [2]21 | [3,4]在这里AliceAlan18这些都是term。所以倒排本质上就是基于term的反向列表方便进行属性查找。到这里我们有个很自然的问题如果term非常多如何快速拿到这个倒排链呢在lucene里面就引入了term dictonary的概念也就是term的字典。term字典里我们可以按照term进行排序那么用一个二分查找就可以定为这个term所在的地址。这样的复杂度是logN在term很多内存放不下的时候效率还是需要进一步提升。可以用一个hashmap当有一个term进入hash继续查找倒排链。这里hashmap的方式可以看做是term dictionary的一个index。 从lucene4开始为了方便实现rangequery或者前缀后缀等复杂的查询语句lucene使用FST数据结构来存储term字典下面就详细介绍下FST的存储结构。FST我们就用Alice和Alan这两个单词为例来看下FST的构造过程。首先对所有的单词做一下排序为“Alice”“Alan”。插入“Alan”插入“Alice”这样你就得到了一个有向无环图有这样一个数据结构就可以很快查找某个人名是否存在。FST在单term查询上可能相比hashmap并没有明显优势甚至会慢一些。但是在范围前缀搜索以及压缩率上都有明显的优势。在通过FST定位到倒排链后有一件事情需要做就是倒排链的合并。因为查询条件可能不止一个例如上面我们想找namealan and age18的列表。lucene是如何实现倒排链的合并呢。这里就需要看一下倒排链存储的数据结构SkipList为了能够快速查找docidlucene采用了SkipList这一数据结构。SkipList有以下几个特征元素排序的对应到我们的倒排链lucene是按照docid进行排序从小到大。跳跃有一个固定的间隔这个是需要建立SkipList的时候指定好例如下图以间隔是3SkipList的层次这个是指整个SkipList有几层有了这个SkipList以后比如我们要查找docid12原来可能需要一个个扫原始链表1235781012。有了SkipList以后先访问第一层看到是然后大于12进入第0层走到38发现15大于12然后进入原链表的8继续向下经过10和12。有了FST和SkipList的介绍以后我们大体上可以画一个下面的图来说明lucene是如何实现整个倒排结构的有了这张图我们可以理解为什么基于lucene可以快速进行倒排链的查找和docid查找下面就来看一下有了这些后如何进行倒排链合并返回最后的结果。倒排合并假如我们的查询条件是name “Alice”那么按照之前的介绍首先在term字典中定位是否存在这个term如果存在的话进入这个term的倒排链并根据参数设定返回分页返回结果即可。这类查询在数据库中使用二级索引也是可以满足那lucene的优势在哪呢。假如我们有多个条件例如我们需要按名字或者年龄单独查询也需要进行组合 name Alice and age 18的查询那么使用传统二级索引方案你可能需要建立两张索引表然后分别查询结果后进行合并这样如果age 18的结果过多的话查询合并会很耗时。那么在lucene这两个倒排链是怎么合并呢。假如我们有下面三个倒排链需要进行合并。在lucene中会采用下列顺序进行合并在termA开始遍历得到第一个元素docId1Set currentDocId1在termB中 search(currentDocId) 1 (返回大于等于currentDocId的一个doc),因为currentDocId 1继续如果currentDocId 和返回的不相等执行2然后继续到termC后依然符合返回结果currentDocId termC的nextItem然后继续步骤3 依次循环。直到某个倒排链到末尾。整个合并步骤我可以发现如果某个链很短会大幅减少比对次数并且由于SkipList结构的存在在某个倒排中定位某个docid的速度会比较快不需要一个个遍历。可以很快的返回最终的结果。从倒排的定位查询合并整个流程组成了lucene的查询过程和传统数据库的索引相比lucene合并过程中的优化减少了读取数据的IO倒排合并的灵活性也解决了传统索引较难支持多条件查询的问题。BKDTree在lucene中如果想做范围查找根据上面的FST模型可以看出来需要遍历FST找到包含这个range的一个点然后进入对应的倒排链然后进行求并集操作。但是如果是数值类型比如是浮点数那么潜在的term可能会非常多这样查询起来效率会很低。所以为了支持高效的数值类或者多维度查询lucene引入类BKDTree。BKDTree是基于KDTree对数据进行按照维度划分建立一棵二叉树确保树两边节点数目平衡。在一维的场景下KDTree就会退化成一个二叉搜索树在二叉搜索树中如果我们想查找一个区间logN的复杂度就会访问到叶子结点得到对应的倒排链。如下图所示如果是多维kdtree的建立流程会发生一些变化。比如我们以二维为例建立过程如下确定切分维度这里维度的选取顺序是数据在这个维度方法最大的维度优先。一个直接的理解就是数据分散越开的维度我们优先切分。切分点的选这个维度最中间的点。递归进行步骤12我们可以设置一个阈值点的数目少于多少后就不再切分直到所有的点都切分好停止。下图是一个建立例子BKDTree是KDTree的变种因为可以看出来KDTree如果有新的节点加入或者节点修改起来消耗还是比较大。类似于LSM的merge思路BKD也是多个KDTREE然后持续merge最终合并成一个。不过我们可以看到如果你某个term类型使用了BKDTree的索引类型那么在和普通倒排链merge的时候就没那么高效了所以这里要做一个平衡一种思路是把另一类term也作为一个维度加入BKDTree索引中。如何实现返回结果进行排序聚合通过之前介绍可以看出lucene通过倒排的存储模型实现term的搜索那对于有时候我们需要拿到另一个属性的值进行聚合或者希望返回结果按照另一个属性进行排序。在lucene4之前需要把结果全部拿到再读取原文进行排序这样效率较低还比较占用内存为了加速lucene实现了fieldcache把读过的field放进内存中。这样可以减少重复的IO但是也会带来新的问题就是占用较多内存。新版本的lucene中引入了DocValuesDocValues是一个基于docid的列式存储。当我们拿到一系列的docid后进行排序就可以使用这个列式存储结合一个堆排序进行。当然额外的列式存储会占用额外的空间lucene在建索引的时候可以自行选择是否需要DocValue存储和哪些字段需要存储。Lucene的代码目录结构介绍了lucene中几个主要的数据结构和查找原理后我们在来看下lucene的代码结构后续可以深入代码理解细节。lucene的主要有下面几个目录analysis模块主要负责词法分析及语言处理而形成Term。codecs模块主要负责之前提到的一些数据结构的实现和一些编码压缩算法。包括skiplistdocvalue等。document模块主要包括了lucene各类数据类型的定义实现。index模块主要负责索引的创建里面有IndexWriter。store模块主要负责索引的读写。search模块主要负责对索引的搜索。geo模块主要为geo查询相关的类实现util模块是bkdfst等数据结构实现。最后本文介绍了lucene中的一些主要数据结构以及如何利用这些数据结构实现高效的查找。我们希望通过这些介绍可以加深理解倒排索引和传统数据库索引的区别数据库有时候也可以借助于搜索引擎实现更丰富的查询语意。除此之外做为一个搜索库如何进行打分query语句如何进行parse这些我们没有展开介绍有兴趣的同学可以深入lucene的源码进一步了解。原文链接干货好文请关注扫描以下二维码
