之前写了NumericDocValue(存储数字的)和BinaryDocValue(存储byte[]的),今天看看存储带有排序的byte[]的docValue,也就是SortedDocValue,这里没有写为SortedBinaryDocValue,可能是为了省略吧,SortedDocValue特指的就排是序的byte[]。注意,之前在写NumericDocValue和BinaryDocValue的时候,忘了说一个事情,就是他们要求每个doc只能存储一个值,即一个数字或者一个byte[],这里SotedDocValue也是一样,每个doc只能有一个byte[]。这里说的排序是指每个doc的byte[]在所有的doc中的排序,在SotedDocValue中要保留这个排序,也就是我们可以从索引中马上得到这个doc的某个值的排序值,比如id是5的doc的排序是1,id是6的排序是3等,所以SortedDocValue特别适合排序,还有一个好处是,SortedDocValue提供了查询指定排序的byte[]的方法,即如果想查询排序是第几的doc的值,也可以快速的查找;还有一个优点就是如果在不建立索引的情况下,也可以查看某个byte[]存在与否。好了,好处慢慢再说,看下他是如何存储的吧。
和前面一样,写入的方法入口仍然是在DefaultIndexingChain的indexDocValue方法里面,里面会创建一个SortedDocValueWriter来写docValue,
//上面是一些属性, /**这个属性是记录所有添加的byte[]的,在添加每个byte[]后,会给其一个id,我们这里叫做termId,如果这个byte[]已经存在了,则返回负值,否则返回其id。其实这个类就是创建索引的时候保存所有的term使用的 */ final BytesRefHash hash; /**记录每个doc的termId的对象,每个doc都有一个termid,并且是按照顺序存放的,所以如果读取id是5的doc的值,则直接读取第五个值就可以。*/ private PackedLongValues.Builder pending; public SortedDocValuesWriter(FieldInfo fieldInfo, Counter iwBytesUsed) { this.fieldInfo = fieldInfo; this.iwBytesUsed = iwBytesUsed; hash = new BytesRefHash(new ByteBlockPool(new ByteBlockPool.DirectTrackingAllocator(iwBytesUsed)), BytesRefHash.DEFAULT_CAPACITY, new DirectBytesStartArray(BytesRefHash.DEFAULT_CAPACITY, iwBytesUsed)); pending = PackedLongValues.deltaPackedBuilder(PackedInts.COMPACT); bytesUsed = pending.ramBytesUsed(); iwBytesUsed.addAndGet(bytesUsed); }
看看他的添加docValue方法,当然这里还是在内存中保存着,
public void addValue(int docID, BytesRef value) { if (value.length > (BYTE_BLOCK_SIZE - 2)) {//太大会报错 throw new IllegalArgumentException("DocValuesField \"" + fieldInfo.name + "\" is too large, must be <= " + (BYTE_BLOCK_SIZE - 2)); ) // Fill in any holes:,因为有的doc没有值,所以要填窟窿,这样在读取的时候,直接按照doc的id读取即可,更加快速 while (pending.size() < docID) { pending.add(EMPTY_ORD); } addOneValue(value); } private void addOneValue(BytesRef value) { int termID = hash.add(value);//添加到内存中,返回其termid if (termID < 0) {//已经存在了 termID = -termID - 1; } else {//第一次出现,增加使用的内存 iwBytesUsed.addAndGet(2 * RamUsageEstimator.NUM_BYTES_INT); } pending.add(termID);//将这个termid记录起来,每个doc都有一个termid,这样在查找某个doc的termid的时候,直接根据doc的id查找即可。 updateBytesUsed(); }
看了代码,就知道,在保存到内存的时候,其实最重要的就是两个属性,一个是用来保存byte[]的hash对象,他用来根据byte[]生成一个id,第二个就是记录每个doc的termid的pending对象。
下面看当提交索引的时候操作:
public void flush(SegmentWriteState state, DocValuesConsumer dvConsumer) throws IOException { final int maxDoc = state.segmentInfo.getDocCount(); assert pending.size() == maxDoc; final int valueCount = hash.size();//term的个数 final PackedLongValues ords = pending.build();//可以通过这个对象找到每个doc含有的byte[]的id // 获得所有的termid,按照文本值从小到大排序 final int[] sortedValues = hash.sort(BytesRef.getUTF8SortedAsUnicodeComparator()); final int[] ordMap = new int[valueCount];//每个term的排序,数组的下标是termid,value是排序。 for (int ord = 0; ord < valueCount; ord++) { ordMap[sortedValues[ord]] = ord;// } dvConsumer.addSortedField(fieldInfo, // ord -> value,返回所有的byte[],已经是排好序的。这样就可以使用前缀压缩。这个对象可以通过每个byte[]的排序找到对应的byte[].因为sortedValues的下标就是排序,而值就是id,所以根据排序就能找到id,再根据id就能从hash中找到byte[] new Iterable<BytesRef>() { public Iterator<BytesRef> iterator() { return new ValuesIterator(sortedValues, valueCount, hash);//第一个参数是已经排序的termid的数组,第二个是所有的byte[]的数量,第三个是所有的byte[]。 } }, // doc -> ord,返回每个doc的byte[]的id,可以通过ords找到每个doc的byte[]的id,然后通过ordMap根据id找到排序. new Iterable<Number>() { public Iterator<Number> iterator() { return new OrdsIterator(ordMap, maxDoc, ords); } }); }
通过上面的两个Iterator就可以 快速的得到每个doc含有的byte[]的排序(通过ordMap),并且能根据排序找到对应的byte[]的id(通过sortedValues),然后根据id快速的找到对应的byte[](通过hash)。再看一下这两个iterable的具体实现:
private static class ValuesIterator implements Iterator<BytesRef> { final int sortedValues[];//次序到byte[]的id的映射 final BytesRefHash hash;//从byte[]的id到byte[]的映射 final BytesRef scratch = new BytesRef(); final int valueCount;//byte[]的数量 int ordUpto;//当前的指针 ValuesIterator(int sortedValues[], int valueCount, BytesRefHash hash) { this.sortedValues = sortedValues; this.valueCount = valueCount; this.hash = hash; } @Override public boolean hasNext() { return ordUpto < valueCount; } @Override public BytesRef next() { if (!hasNext()) { throw new NoSuchElementException(); } hash.get(sortedValues[ordUpto], scratch);//sortedValues[ordUpto]求出的是byte[]的id,然后hash.get是根据id求出byte[]来,然后放入到scratch中。 ordUpto++; return scratch; } }
可以总结,这个valueSourceIterator很简单,就是按照已经排好顺序的byte[]依次返回。再看看下一个iterator
private static class OrdsIterator implements Iterator<Number> { final PackedLongValues.Iterator iter;//这个是记录的每个doc的byte[]的id final int ordMap[];//记录的是每个byte[]的次序 final int maxDoc;//一共多少个doc int docUpto; OrdsIterator(int ordMap[], int maxDoc, PackedLongValues ords) { this.ordMap = ordMap; this.maxDoc = maxDoc; assert ords.size() == maxDoc; this.iter = ords.iterator(); } @Override public boolean hasNext() { return docUpto < maxDoc; } @Override public Number next() { if (!hasNext()) { throw new NoSuchElementException(); } int ord = (int) iter.next(); docUpto++; return ord == -1 ? ord : ordMap[ord];//返回的是次序。即每个doc的byte[]的次序 } }
从代码中可以看出,这个iterable返回的是每个doc的byte[] 的次序。
再看下到底是如何使用者两个iterable的,代码在Lucene410DocValuesConsumer.addSortedField(FieldInfo, Iterable<BytesRef>, Iterable<Number>)中:
public void addSortedField(FieldInfo field, Iterable<BytesRef> values, Iterable<Number> docToOrd) throws IOException { meta.writeVInt(field.number); meta.writeByte(Lucene410DocValuesFormat.SORTED);//记录格式。 addTermsDict(field, values);//添加那些byte[],按照前缀压缩的格式, addNumericField(field, docToOrd, false);//添加数字,也就是每个doc对应的排序 }
从名字上大概 可以看到,他是采取了两块来存储的,第一步存储的是byte[],第二步存储的是每个doc的次序。事实上就是这么做的,先看第一个代码,即存储所有的byte[]。
private void addTermsDict(FieldInfo field, final Iterable<BytesRef> values) throws IOException { // first check if its a "fixed-length" terms dict int minLength = Integer.MAX_VALUE; int maxLength = Integer.MIN_VALUE; long numValues = 0; for (BytesRef v : values) { minLength = Math.min(minLength, v.length); maxLength = Math.max(maxLength, v.length); numValues++; } if (minLength == maxLength) { addBinaryField(field, values);//如果所有的byte[]的长度都相等,则直接向存储普通的binaryDocValue那样存储就可以了,不错这个条件几乎不会实现的 } else if (numValues < REVERSE_INTERVAL_COUNT) { addBinaryField(field, values);//同上 } else { // header meta.writeVInt(field.number); meta.writeByte(Lucene410DocValuesFormat.BINARY); meta.writeVInt(BINARY_PREFIX_COMPRESSED);//写入存储格式,是基于前缀压缩的。 meta.writeLong(-1L); final long startFP = data.getFilePointer(); //刚上来可能不好看懂,所以我直接说一下是怎么存储的吧,在存储所有的byte[]的时候,是按照前缀压缩匹配的,就像在词典表中存放到格式一样。 //每16个byte[]作为一个块来存储,在一个块中又分为两部分,第一部分是记录的这个快的第一个byte[]以及后面的15个byte的除了共享前缀意外的长度。这一部分叫做headBuffer //在第二个块中记录的是另外15个byte[]的除了共享前缀意外的部分以及共享前缀的长度。这个部分叫做bytesBuffer RAMOutputStream addressBuffer = new RAMOutputStream(); MonotonicBlockPackedWriter termAddresses = new MonotonicBlockPackedWriter(addressBuffer, BLOCK_SIZE);//记录每个block的开始位置在data中的位置,也就是每个块的索引的 RAMOutputStream bytesBuffer = new RAMOutputStream();//记录第二部分 // buffers up block header RAMOutputStream headerBuffer = new RAMOutputStream();//第一部分,每隔16个则记录一次。 BytesRefBuilder lastTerm = new BytesRefBuilder();//刚刚写入第一部分的byte[]。 lastTerm.grow(maxLength); long count = 0; int suffixDeltas[] = new int[INTERVAL_COUNT];//记录第二部分的byte[]在刨除了和对应的第一部分的byte[]的共享前缀意外的长度 for (BytesRef v : values) { int termPosition = (int) (count & INTERVAL_MASK);//每隔interval_mask+1 个,也就是16个 if (termPosition == 0) {//每隔16个,记录一个到第一部分中 termAddresses.add(data.getFilePointer() - startFP);//记录一个小块的开始位置,也就是索引 headerBuffer.writeVInt(v.length);//在第一部分中记录当前的byte[]的长度 headerBuffer.writeBytes(v.bytes, v.offset, v.length);//记录当前的byte[]的内容 lastTerm.copyBytes(v);//保留当前的byte[], } else { // 基于前缀压缩的,最大共享前缀是255个 int sharedPrefix = Math.min(255, StringHelper.bytesDifference(lastTerm.get(), v));//当前的byte[]和刚刚写入上层跳表的byte[]的前缀的数量,最大255个。 bytesBuffer.writeByte((byte) sharedPrefix);//在第二部分中写入前缀的长度 bytesBuffer.writeBytes(v.bytes, v.offset + sharedPrefix, v.length - sharedPrefix);//将刨除了前缀以外的部分写入到第二部分中 suffixDeltas[termPosition] = v.length - sharedPrefix - 1;//记录当前的byte[]刨除了共享前缀意外的部分的长度,这个值将来写在第一部分里面,比如这个块的第一层记录的byte[]是a,而当前的byte[]记录的是ab,则这个值就是1,当然我这里用的是字符数组,不是byte[]。 } count++; if ((count & INTERVAL_MASK) == 0) {//每够16个,写入到硬盘 flushTermsDictBlock(headerBuffer, bytesBuffer, suffixDeltas); } } // flush trailing crap int leftover = (int) (count & INTERVAL_MASK); if (leftover > 0) {//写入最后的部分,因为上面只有到16的倍数才会写入到data中。 Arrays.fill(suffixDeltas, leftover, suffixDeltas.length, 0); flushTermsDictBlock(headerBuffer, bytesBuffer, suffixDeltas); } final long indexStartFP = data.getFilePointer();//索引部分,也就是上面的addressBuffer在data中的开始位置。 // write addresses of indexed terms,接下来要写的是每个块在data中的开始位置 termAddresses.finish(); addressBuffer.writeTo(data); addressBuffer = null; termAddresses = null; meta.writeVInt(minLength); meta.writeVInt(maxLength); meta.writeVLong(count); meta.writeLong(startFP);//记录byte[]数据的开始位置, meta.writeLong(indexStartFP);//记录索引的开始位置 meta.writeVInt(PackedInts.VERSION_CURRENT); meta.writeVInt(BLOCK_SIZE); addReverseTermIndex(field, values, maxLength); } }
还有一个方法是flushTermDictBlock方法,也就是当每个16个byte[]的时候,要把第一部分,第二部分写入到硬盘,看看他是如何操作的:
/**参数的意义可以在上面的方法中查找到*/ private void flushTermsDictBlock(RAMOutputStream headerBuffer, RAMOutputStream bytesBuffer, int suffixDeltas[]) throws IOException { boolean twoByte = false;//这个的意思是记录每一个块的长度的时候(长度说的是每个byte[]在刨除了共享前缀的byte[]以外的长度),可能会超过254,如果超过了就用short,否则用byte。 for (int i = 1; i < suffixDeltas.length; i++) { if (suffixDeltas[i] > 254) { twoByte = true; } } if (twoByte) {//随便看一种即可。可以发现是将每个byte[]的除了共享前缀意外的部分的长度写在了head里面,即第一部分里面。 headerBuffer.writeByte((byte) 255); for (int i = 1; i < suffixDeltas.length; i++) { headerBuffer.writeShort((short) suffixDeltas[i]); } } else { for (int i = 1; i < suffixDeltas.length; i++) { headerBuffer.writeByte((byte) suffixDeltas[i]); } } headerBuffer.writeTo(data);//将head写入到data中, headerBuffer.reset(); bytesBuffer.writeTo(data);//将bytes写入到data中 bytesBuffer.reset(); }
看完了上面的两个方法,我们可以总结下载存储具体的byte[]的时候是怎么存储的。所有的byte[]经过排序后,按照从小到大的顺序保存,然后每16个存储为一个块,这个块中分为两个部分,第一个部分叫做header,存储了 这个块的第一个byte[],以及剩下的15个byte[]的除了前缀意外的部分的长度,第二个块存储的是每个byte[]的共享前缀的长度,以及自己的byte[]。还有存储了termAddress,也就是记录了每个块在data中的开始位置,这样当我们要查找某个排序的byte[]的时候,就可以先计算其所属的块,然后直接根据termAddress找到对应的开始位置再从16个byte[]中查找就可以了。我们还忘记了一个方法,也即是上面的addReverseTermIndex方法,看一下:
private void addReverseTermIndex(FieldInfo field, final Iterable<BytesRef> values, int maxLength) throws IOException { long count = 0; BytesRefBuilder priorTerm = new BytesRefBuilder(); priorTerm.grow(maxLength); BytesRef indexTerm = new BytesRef(); long startFP = data.getFilePointer();//第三部分的开始的位置 PagedBytes pagedBytes = new PagedBytes(15);//用来记录生成的每个字符串 MonotonicBlockPackedWriter addresses = new MonotonicBlockPackedWriter(data, BLOCK_SIZE);//因为下面的每次的indexTerm的长度都是不同的,要使用这个对象记录每个indexTerm在data中的开始位置,这样在查找的时候能更快速的定位到第n个字符串的位置 for (BytesRef b : values) { int termPosition = (int) (count & REVERSE_INTERVAL_MASK); if (termPosition == 0) {//每隔1024个,记录一个term,第0个或者是第1024个,进入 int len = StringHelper.sortKeyLength(priorTerm.get(), b);//找到能够判断出两个byte[]大小所需要的最小的长度。 indexTerm.bytes = b.bytes; indexTerm.offset = b.offset; indexTerm.length = len;//只记录最开始的一些。 addresses.add(pagedBytes.copyUsingLengthPrefix(indexTerm));//记录添加前的位置,也就是开始位置,最终写入到data中去 } else if (termPosition == REVERSE_INTERVAL_MASK) {//第1023个进入 priorTerm.copyBytes(b); } count++; } addresses.finish();//将所有的新的字符串的位置写入到data中 long numBytes = pagedBytes.getPointer();//使用的byte的个数 pagedBytes.freeze(true); PagedBytesDataInput in = pagedBytes.getDataInput(); meta.writeLong(startFP);//第三部分的开始位置写入到索引中 data.writeVLong(numBytes);//记录pagedBytess使用的长度 data.copyBytes(in, numBytes);//写入pagedBytes,也就是所有的字符串(每隔1024个term计算一个字符串)。 }
这个方法很简单,他是对于所有的byte[],每1024个记录一些最短的byte[]的前缀(也就是上面说的产生一个新的字符串),使得所有的byte[]能够区别出大小来就可以,他的目的是对于某些查询,比如要查询abc这个byte[]存不存在(这个方法在SortedDocValues里面就存在),如果没有这个功能的话,我们并不知道他是哪一个块,只能尝试所有的块,而如果有了这个记录,我们就能快速定位他的大致的范围,然后再查找的话,就快的多了。这个功能是后来新家的,我看4.9就没有,4.10就有了。
再次总结一下sortedBinary的存储吧,一共分为三块,第一块是记录所有的byte[]的,按照每16个一个小块记录,每个小块分为两部分,header和bytes(详细的不再重复);第二块是记录了每个小块在data中的索引,方便快速的找到块的位置;第三部分就是每个2014个记录一个尽可能小的byte[],是为了查找某个byte[]存不存在而存放的,使用二分查找,快速的找到其大概位置,然后在从小块中查找,也可以看做是byte[]的索引吧。不过期效率不是很高。
还有一个方法就是addSortedField中的addNumericField,这个方法很简单,目的就是记录每个doc的byte[]的排序的,方便根据doc查找到排序后,再查找具体的byte[]值。这个方法就是之前写NumericDocValue时的方法。不再重复了。
算法上面的addNumeircField方法,我们可以将所有的sortedBinaryDocValue分为两个部分,一个是binary部分,一个是numeric部分,前面的部分负责保存byte[],是分为三个部分存放的额,第二个部分用来存放每个doc的byte[]的排序。 知道了这个存储格式,我们就能猜想sortedDocValue的功能的实现,比如查找排序是n的docValue,可以直接根据n找到binary部分的第一部分的第n%16+1个小块,根据第二小块的索引快速定位到开始位置,然后再16个小块中查找;如果想查找docid是n的doc的排序,则直接查找numeric部分即可,如果再想查找byte[],则再根据排序查找即可。
相关推荐
### Lucene3源码分析知识点概述 #### 一、全文检索的基本原理 ##### 1. 总论 全文检索系统是一种高效的信息检索技术,能够帮助用户在海量文档中快速找到包含特定关键词的信息。Lucene是Java领域内最受欢迎的全文...
源码阅读是理解任何软件内部工作原理的最好方式,通过研究Lucene的源码,我们可以深入了解其内部的数据结构、算法实现以及优化技巧。例如,可以学习到如何实现Trie数据结构进行高效查询,或者如何使用BitSet进行布尔...
《深入剖析Lucene.NET 2.9.4.2源码》 Lucene.NET是一个开源全文搜索引擎库,它是Apache Lucene项目的.NET版本。这个源码版是2.9.4.2版本,相较于2.9.4版进行了一些局部改进,以适应.NET平台的需求和优化。在本文中...
【Lucene源码解读1】 Lucene是一款开源的全文搜索引擎库,由Apache软件基金会开发,广泛应用于各种信息检索系统。其强大的搜索功能和高效的性能深受开发者喜爱。在深入理解Lucene之前,我们需要先了解它的核心概念...
总的来说,深入学习Lucene 3.5.0的源码,可以帮助开发者掌握全文检索的核心技术,了解其内部工作原理,并能灵活应用到自己的项目中。这份源码不仅适用于初学者,也是经验丰富的开发者的宝贵参考资料。通过阅读和理解...
通过深入理解Lucene.Net 2.9.2的源码,开发者可以定制自己的分析器、优化查询性能、调整索引策略,从而在实际项目中充分发挥Lucene.Net的潜力。在构建查询网站时,结合C#的特性,可以构建出高效、灵活且用户体验良好...
本文将主要围绕Java Lucene进行深入探讨,并基于提供的“Lucene学习源码.rar”文件中的“Lucene视频教程_讲解部分源码”展开讨论。 一、Lucene核心概念 1. 文档(Document):Lucene中的基本单位,用于存储待检索...
通过对“lucene全文检索案例源码”的学习,我们可以理解Lucene如何在实际项目中实现全文检索。从索引构建到搜索执行,每个步骤都至关重要。通过源码的深入研究,有助于我们在实际开发中更好地运用Lucene,提升搜索...
《深入剖析Lucene.NET 2.9.1:源码解析与应用开发》 Lucene.NET 2.9.1是开源搜索引擎库Lucene的.NET版本,它为.NET开发者提供了强大的全文检索和索引功能。这个版本的源码提供了一个宝贵的资源,帮助我们理解其内部...
在Java开发中,Lucene被广泛用于实现文件的全文检索功能,包括对doc、docx、pdf、txt等常见格式文档的文本内容检索。在本文中,我们将探讨如何使用Lucene对这些文件类型进行全文检索的实现。 首先,为了实现全文...
学习这个源码包可以帮助你理解如何在Java环境中使用Lucene进行全文检索,以及如何实现数据库与索引之间的交互。这不仅涉及到了Lucene的核心功能,也涵盖了实际项目中常见的增量索引和数据库集成问题。通过阅读和理解...
总之,《Lucene in Action》的源码是一份宝贵的教育资源,它能帮助开发者深入理解搜索引擎的运作原理,从而在实际项目中更好地利用Lucene。通过细致研究源码,我们不仅可以解决具体的技术问题,还能培养出更强的解决...
本文将结合“lucene 华电项目 源码”,深度解析Lucene的核心原理以及在华电项目中的实际应用。 首先,我们要理解Lucene的基本架构。Lucene的核心组件包括Analyzer(分析器)、Document(文档)、IndexWriter(索引...
4. FSTHashMap:这是一个基于探测法实现的HashMap,其key是基于FSTNode生成的hash值,而value是FSTnode在FSTbytes数组中的位置索引。FSTHashMap可以加速判断某个节点是否已经被存储到FSTbytes中。 5. Frontier:这...
源码文件通常包含了书中各个章节的示例程序,这些示例涵盖了Lucene的基本用法到高级特性的实现,如文档索引、搜索查询、结果排序、过滤器、分词器、高亮显示等。通过研究这些源码,开发者可以了解如何有效地利用...
在`lucene-1.4-final`这个压缩包中,包含了Lucene 1.4版本的源代码,你可以深入研究其内部实现,理解各个类和方法的工作原理。同时,这也可以帮助你定制分析器、优化搜索性能,或者扩展Lucene的功能,例如集成到你的...
《深入剖析Lucene中的中文分词算法源码》 在信息检索领域,Lucene作为一款强大的全文搜索引擎库,被广泛应用于各种数据检索系统。而中文分词是Lucene处理中文文本时的关键步骤,它决定了搜索的准确性和效率。本文将...
**Lucene.Net** 是一个基于 .NET Framework 的全文搜索引擎库,它是 Apache Lucene 项目的 .NET 实现。这个开源项目提供了高效、可扩展的搜索功能,使得开发者能够在其应用程序中轻松地实现高级的文本检索功能。 **...
作为一款Java实现的全文搜索引擎架构,Lucene 提供了完整的索引和查询引擎,使得开发者能够快速、有效地在大量数据中进行文本搜索。 ### Lucene 的核心组件 1. **索引(Indexing)**: Lucene 的索引过程将文档内容...
在Lucene-2.9.2的源码中,你可以看到关于TF-IDF的具体实现,如`TFIDFSimilarity`类,它是Lucene对TF-IDF算法的封装。它不仅包含了TF和IDF的计算逻辑,还考虑了诸如短语匹配、长度惩罚等因素,以提升搜索精度。 除了...