Lucene 索引结构

Lucene核心部分——索引排序
Lucene 的索引排序是使用了倒排序原理。

该结构及相应的生成算法如下：
设有两篇文章1和2
文章1的内容为：Tom lives in Guangzhou,I live in Guangzhou too.
文章2的内容为：He once lived in Shanghai.

1. 由于lucene是基于关键词索引和查询的，首先我们要取得这两篇文章的关键词，通常我们需要如下处理措施

a. 我们现在有的是文章内容，即一个字符串，我们先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。中文单词间是连在一起的需要特殊的分词处理。

b. 文章中的”in”, “once” “too”等词没有什么实际意义，中文中的“的”“是”等字通常也无具体含义， 这些不代表概念的词可以过滤掉，这个也就是在《Lucene详细分析》中所讲的StopTokens

c. 用户通常希望查“He”时能把含“he”，“HE”的文章也找出来，所以所有单词需要统一大小写。

d. 用户通常希望查“live”时能把含“lives”，“lived”的文章也找出来，所以需要把“lives”，“lived”还原成“live”

e. 文章中的标点符号通常不表示某种概念，也可以过滤掉,在lucene中以上措施由Analyzer类完成,经过上面处理后:

文章1的所有关键词为：[tom] [live] [guangzhou] [live] [guangzhou]
文章2的所有关键词为：[he] [live] [shanghai]

2. 有了关键词后，我们就可以建立倒排索引了

上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成：“关键词”对“拥有该关键词的所有文章号”。文章1，2经过倒排后变成
<!--[if !supportLineBreakNewLine]-->

关键词
文章号

guangzhou
1

he
2

i
1

live
1,2

shanghai
2

tom
1

 

通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：a)字符位置，即记录该词 是文章中第几个字符（优点是关键词亮显时定位快）；b)关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组（phase）查询快）， lucene中记录的就是这种位置。
加上“出现频率”和“出现位置”信息后，我们的索引结构变为：

 

关键词
文章号[出现频率]
出现位置

guangzhou
1[2]
3，6

he
2[1]
1

i
1[1]
4

live
1[2],2[1]
2，5，2

shanghai
2[1]
3

tom
1[1]
1

 

以live 这行为例我们说明一下该结构：live在文章1中出现了2次，文章2中出现了一次，它的出现位置为“2,5,2”这表示什么呢？我们需要结合文章号和出现 频率来分析，文章1中出现了2次，那么“2,5”就表示live在文章1中出现的两个位置，文章2中出现了一次，剩下的“2”就表示live是文章2中第 2个关键字。
以上就是lucene索引结构中最核心的部分。我们注意到关键字是按字符顺序排列的（lucene没有使用B树结构），因此lucene可以用二元搜索算法快速定位关键词。
实 现时 lucene将上面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信 息。

Lucene中使用了field的概念，用于表达信息所在位置（如标题中，文章中，url中），在建索引中，该field信息也记录在词典文件中，每个关键词都有一个field信息(因为每个关键字一定属于一个或多个field)。
为 了减小索引文件的大小，Lucene对索引还使用了压缩技术。首先，对词典文件中的关键词进行了压缩，关键词压缩为<前缀长度，后缀>，例 如：当前词为“阿拉伯语”，上一个词为“阿拉伯”，那么“阿拉伯语”压缩为<3，语>。其次大量用到的是对数字的压缩，数字只保存与上一个值 的差值（这样可以减小数字的长度，进而减少保存该数字需要的字节数）。例如当前文章号是16389（不压缩要用3个字节保存），上一文章号是16382， 压缩后保存7（只用一个字节）。
下面我们可以通过对该索引的查询来解释一下为什么要建立索引。
假设要查询单词 “live”，lucene先对词典二元查找、找到该词，通过指向频率文件的指针读出所有文章号，然后返回结果。词典通常非常小，因而，整个过程的时间是毫秒级的。
而用普通的顺序匹配算法，不建索引，而是对所有文章的内容进行字符串匹配，这个过程将会相当缓慢，当文章数目很大时，时间往往是无法忍受的。

3.2. Lucene的相关度积分公式
score_d = sum_t(tf_q * idf_t / norm_q * tf_d * idf_t / norm_d_t * boost_t) * coord_q_d

注解：

score_d : 该文档d的得分

sum_t : 所有项得分的总和

tf_q : 查询串q中，某个项出项的次数的平方根

tf_d : 文档d中 ，出现某个项的次数的平方根

numDocs : 在这个索引里，找到分数大于0的文档的总数

docFreq_t : 包含项t的文档总数

idf_t : log(numDocs/docFreq+1)+1.0

norm_q : sqrt(sum_t((tf_q*idf_t)^2))

norm_d_t : 在文档d中，与项t相同的域中，所有的项总数的平方根

boost_t : 项t的提升因子，一般为 1.0

coord_q_d : 在文档d中，命中的项数量除以查询q的项总数

3.3. Lucene的其他特性
3.3.1. Boosting特性
luncene对Document和Field提供了一个可以设置的Boosting参数， 这个参数的用处是告诉lucene， 某些记录更重要，在搜索的时候优先考虑他们 比如在搜索的时候你可能觉得几个门户的网页要比垃圾小站更优先考虑

lucene默认的boosting参数是1.0, 如果你觉得这个field重要,你可以把boosting设置为1.5, 1.2....等, 对Document设置boosting相当设定了它的每个Field的基准boosting，到时候实际Field的boosting就是 (Document-boosting*Field-boosting)设置了一遍相同的boosting.

似乎在lucene的记分公式里面有boosting参数,不过我估计一般人是不会去研究他的公式的（复杂）,而且公式也无法给出最佳值，所以我们所能做的只能是一点一点的改变boosting, 然后在实际检测中观察它对搜索结果起到多大的作用来调整

一般的情况下是没有必要使用boosting的, 因为搞不好你就把搜索给搞乱了, 另外如果是单独对Field来做Bossting, 也可以通过将这个Field提前来起到近似的效果

3.3.2. Indexing Date
日期是lucene需要特殊考虑的地方之一, 因为我们可能需要对日期进行范围搜索, Field.keyword(string,Date)提供了这样的方法,lucene会把这个日期转换为string, 值得注意的是这里的日期是精确到毫秒的,可能会有不必要的性能损失, 所以我们也可以把日期自行转化为YYYYMMDD这样的形势,就不用精确到具体时间了,通过File.keyword(Stirng,String) 来index, 使用PrefixQuery 的YYYY一样能起到简化版的日期范围搜索(小技巧), lucene提到他不能处理1970年以前的时间,似乎是上一代电脑系统遗留下来的毛病

3.3.3. Indexing 数字
如果数字只是简单的数据, 比如中国有56个民族. 那么可以简单的把它当字符处理

如果数字还包含数值的意义,比如价格, 我们会有范围搜索的需要(20元到30元之间的商品),那么我们必须做点小技巧, 比如把3,34,100 这三个数字转化为003,034,100 ,因为这样处理以后, 按照字符排序和按照数值排序是一样的,而lucene内部按照字符排序,003->034->100 NOT(100->3->34)

3.3.4. 排序
Lucene默认按照相关度(score)排序,为了能支持其他的排序方式,比如日期,我们在add Field的时候,必须保证field被Index且不能被tokenized(分词),并且排序的只能是数字,日期,字符三种类型之一

3.3.5. Lucene的IndexWriter调整
IndexWriter提供了一些参数可供设置，列表如下

属性
默认值
说明

mergeFactor
org.apache.lucene.mergeFactor
10
控制index的大小和频率,两个作用

maxMergeDocs
org.apache.lucene.maxMergeDocs
Integer.MAX_VALUE
限制一个段中的document数目

minMergeDocs
org.apache.lucene.minMergeDocs
10
缓存在内存中的document数目，超过他以后会写入到磁盘

maxFieldLength

1000
一个Field中最大Term数目，超过部分忽略，不会index到field中，所以自然也就搜索不到

 

这些参数的的详细说明比较复杂：mergeFactor有双重作用

设置每mergeFactor个document写入一个段，比如每10个document写入一个段

设置每mergeFacotr个小段合并到一个大段，比如10个document的时候合并为1小段，以后有10个小段以后合并到一个大段，有10个大段以后再合并，实际的document数目会是mergeFactor的指数

简单的来说mergeFactor 越大，系统会用更多的内存，更少磁盘处理，如果要打批量的作index，那么把mergeFactor设置大没错， mergeFactor 小了以后， index数目也会增多，searhing的效率会降低， 但是mergeFactor增大一点一点，内存消耗会增大很多(指数关系),所以要留意不要"out of memory"
把maxMergeDocs设置小，可以强制让达到一定数量的document写为一个段，这样可以抵消部分mergeFactor的作用.
minMergeDocs相当于设置一个小的cache,第一个这个数目的document会留在内存里面，不写入磁盘。这些参数同样是没有最佳值的， 必须根据实际情况一点点调整。
maxFieldLength可以在任何时刻设置， 设置后，接下来的index的Field会按照新的length截取，之前已经index的部分不会改变。可以设置为Integer.MAX_VALUE

3.3.6. RAMDirectory 和 FSDirectory 转化
RAMDirectory(RAMD)在效率上比 FSDirectyr(FSD)高不少, 所以我们可以手动的把RAMD当作FSD的buffer,这样就不用去很费劲的调优FSD那么多参数了,完全可以先用RAM跑好了index， 周期性（或者是别的什么算法）来回写道FSD中。 RAMD完全可以做FSD的buffer。

3.3.7. 为查询优化索引(index)
Indexwriter.optimize()方法可以为查询优化索引（index），之前 提到的参数调优是为indexing过程本身优化，而这里是为查询优化，优化主要是减少index文件数，这样让查询的时候少打开文件，优化过程中， lucene会拷贝旧的index再合并，合并完成以后删除旧的index，所以在此期间，磁盘占用增加， IO符合也会增加，在优化完成瞬间，磁盘占用会是优化前的2倍,在optimize过程中可以同时作search。

3.3.8. 并发操作Lucene和locking机制
v 所有只读操作都可以并发

v 在index被修改期间，所有只读操作都可以并发

v 对index修改操作不能并发，一个index只能被一个线程占用

v index的优化，合并，添加都是修改操作

v IndexWriter和IndexReader的实例可以被多线程共享，他们内部是实现了同步，所以外面使用不需要同步

3.3.9. Locing
lucence内部使用文件来locking， 默认的locking文件放在java.io.tmpdir,可以通过-Dorg.apache.lucene.lockDir=xxx指定新的dir， 有write.lock commit.lock两个文件，lock文件用来防止并行操作index，如果并行操作， lucene会抛出异常，可以通过设置-DdisableLuceneLocks=true来禁止locking，这样做一般来说很危险，除非你有操作系 统或者物理级别的只读保证，比如把index文件刻盘到CDROM上。

4. Lucene文档结构
Lucene中最基础的概念是索引（index），文档（document．，域（field）和项（term）。
索引包含了一个文档的序列。
· 文档是一些域的序列。
· 域是一些项的序列。
· 项就是一个字串。
存在于不同域中的同一个字串被认为是不同的项。因此项实际是用一对字串表示的，第一个字串是域名，第二个是域中的字串。

4.1. Lucene概念详细介绍
4.1.1. 域的类型
Lucene中，域的文本可能以逐字的非倒排的方式存储在索引中。而倒排过的域称为被索引过了。域也可能同时被存储和被索引。
域的文本可能被分解许多项目而被索引，或者就被用作一个项目而被索引。大多数的域是被分解过的，但是有些时候某些标识符域被当做一个项目索引是很有用的。

4.1.2. 段（Segment）
Lucene索引可能由多个子索引组成，这些子索引成为段。每一段都是完整独立的索引，能被搜索。索引是这样作成的：
1. 为新加入的文档创建新段。
2. 合并已经存在的段。
搜索时需要涉及到多个段和/或者多个索引，每一个索引又可能由一些段组成。

4.1.3. 文档号（document．nbspNumber）
内部的来说，Lucene用一个整形（interger）的文档号来指示文档。第一个被加入到索引中的文档就是0号，顺序加入的文档将得到一个由前一个号码递增而来的号码。

注意文档号是可能改变的，所以在Lucene外部存储这些号码时必须小心。特别的，号码的改变的情况如下：

· 只有段内的号码是相同的，不同段之间不同，因而在一个比段广泛的上下文环境中使用这些号码时，就必须改变它们。标准的技术是根据每一段号码多少为每一段分 配一个段号。将段内文档号转换到段外时，加上段号。将某段外的文档号转换到段内时，根据每段中可能的转换后号码范围来判断文档属于那一段，并减调这一段的 段号。例如有两个含5个文档的段合并，那么第一段的段号就是0，第二段段号5。第二段中的第三个文档，在段外的号码就是8。

· 文档删除后，连续的号码就出现了间断。这可以通过合并索引来解决，段合并时删除的文档相应也删掉了，新合并而成的段并没有号码间断。

4.1.4. 索引信息
索引段维护着以下的信息：
· 域集合。包含了索引中用到的所有的域。
· 域值存储表。每一个文档都含有一个“属性－值”对的列表，属性即为域名。这个列表用来存储文档的一些附加信息，如标题，url或者访问数据库的一个ID。在搜索时存储域的集合可以被返回。这个表以文档号标识。
· 项字典。这个字典含有所有文档的所有域中使用过的的项，同时含有使用过它的文档的文档号，以及指向使用频数信息和位置信息的指针。
· 项频数信息。对于项字典中的每个项，这些信息包含含有这个项的文档的总数，以及每个文档中使用的次数。
· 项位置信息。对于项字典中的每个项，都存有在每个文档中出现的各个位置。
· 标准化因子。对于文档中的每一个域，存有一个值，用来以后乘以这个这个域的命中数（hits）。
· 被删除的文档信息。这是一个可选文件，用来表明那些文档已经删除了。
接下来的各部分部分详细描述这些信息。

4.1.5. 文件的命名（File Naming）
同属于一个段的文件拥有相同的文件名，不同的扩展名。扩展名由以下讨论的各种文件格式确定。
一般来说，一个索引存放一个目录，其所有段都存放在这个目录里，不这样作，也是可以的，在性能方面较低。

4.2. Lucene基本数据类型（Primitive Types）
4.2.1. 字节Byte
最基本的数据类型就是字节（byte，8位）。文件就是按字节顺序访问的。其它的一些数据类型也定义为字节的序列，文件的格式具有字节意义上的独立性。
UInt32 ：32位无符号整数，由四个字节组成，高位优先。UInt32 --> <Byte>4
Uint64 ： 64位无符号整数，由八字节组成，高位优先。UInt64 --> <Byte>8
VInt ： 可变长的正整数类型，每字节的最高位表明还剩多少字节。每字节的低七位表明整数的值。因此单字节的值从0到127，两字节值从128到16,383，等等。
VInt 编码示例
value
First byte
Second byte
Third byte
0
00000000
1
00000001
2
00000010
...
127
01111111
128
10000000
00000001
129
10000001
00000001
130
10000010
00000001
...
16,383
11111111
01111111
16,384
10000000
10000000
00000001
16,385
10000001
10000000
00000001
... 这种编码提供了一种在高效率解码时压缩数据的方法。

4.2.2. 字符串Chars
Lucene输出UNICODE字符序列，使用标准UTF-8编码。
String ：Lucene输出由VINT和字符串组成的字串，VINT表示字串长，字符串紧接其后。
String --> VInt, Chars

4.3. 索引包含的文件（Per-Index Files）
4.3.1. Segments文件
索引中活动的段存储在Segments文件中。每个索引只能含有一个这样的文件，名为"segments".这个文件依次列出每个段的名字和每个段的大小。
Segments --> SegCount, <SegName, SegSize>SegCount
SegCount, SegSize --> UInt32
SegName --> String
SegName表示该segment的名字，同时作为索引其他文件的前缀。
SegSize是段索引中含有的文档数。

4.3.2. Lock文件
有一些文件用来表示另一个进程在使用索引。
· 如果存在"commit.lock"文件，表示有进程在写"segments"文件和删除无用的段索引文件，或者表示有进程在读"segments"文件 和打开某些段的文件。在一个进程在读取"segments"文件段信息后，还没来得及打开所有该段的文件前，这个Lock文件可以防止另一个进程删除这些 文件。
· 如果存在"index.lock"文件，表示有进程在向索引中加入文档，或者是从索引中删除文档。这个文件防止很多文件同时修改一个索引。

4.3.3. Deleteable文件
名为"deletetable"的文件包含了索引不再使用的文件的名字，这些文件可能并没有被实际的删除。这种情况只存在与Win32平台下，因为Win32下文件仍打开时并不能删除。
Deleteable --> DelableCount, <DelableName>DelableCount
DelableCount --> UInt32
DelableName --> String

4.3.4. 段包含的文件（Per-Segment Files）
剩下的文件是每段中包含的文件，因此由后缀来区分。
域（Field）
域集合信息（Field Info）
所有域名都存储在这个文件的域集合信息中，这个文件以后缀.fnm结尾。

FieldInfos (.fnm) --> FieldsCount, <FieldName, FieldBits>FieldsCount
FieldsCount --> VInt
FieldName --> String
FieldBits --> Byte
目前情况下，FieldBits只有使用低位，对于已索引的域值为1，对未索引的域值为0。
文件中的域根据它们的次序编号。因此域0是文件中的第一个域，域1是接下来的，等等。这个和文档号的编号方式相同。

4.3.5. 域值存储表（Stored Fields）
域值存储表使用两个文件表示：
1. 域索引（.fdx文件）。
如下，对于每个文档这个文件包含指向域值的指针：
FieldIndex (.fdx) --> <FieldvaluesPosition>SegSize
FieldvaluesPosition --> Uint64
FieldvaluesPosition 指示的是某一文档的某域的域值在域值文件中的位置。因为域值文件含有定长的数据信息，因而很容易随机访问。在域值文件中，文档n的域值信息就存在n*8位 置处（The position of document．nbspn's field data is the Uint64 at n*8 in this file.）。
2. 域值（.fdt文件）。
如下，每个文档的域值信息包含：
FieldData (.fdt) --> <DocFieldData>SegSize
DocFieldData --> FieldCount, <FieldNum, Bits, value>FieldCount
FieldCount --> VInt
FieldNum --> VInt
Bits --> Byte
value --> String
目前情况下，Bits只有低位被使用，值为1表示域名被分解过，值为0表示未分解过。÷

4.3.6. 项字典（Term Dictionary）
项字典用以下两个文件表示：
1. 项信息（.tis文件）。
TermInfoFile (.tis)--> TermCount, TermInfos
TermCount --> UInt32
TermInfos --> <TermInfo>TermCount
TermInfo --> <Term, DocFreq, FreqDelta, ProxDelta>
Term --> <PrefixLength, Suffix, FieldNum>
Suffix --> String
PrefixLength, DocFreq, FreqDelta, ProxDelta
--> VInt

项信息按项排序。项信息排序时先按项所属的域的文字顺序排序，然后按照项的字串的文字顺序排序。

项的字前缀往往是共同的，与字的后缀组成字。PrefixLength变量就是表示与前一项相同的前缀的字数。因此，如果前一个项的字是"bone"，后一个是"boy"的话，PrefixLength值为2，Suffix值为"y"。

FieldNum指明了项属于的域号，而域名存储在.fdt文件中。

DocFreg表示的是含有该项的文档的数量。

FreqDelta指明了项所属TermFreq变量在.frq文件中的位置。详细的说，就是指相对于前一个项的数据的位置偏移量（或者是0，表示文件中第一个项）。

ProxDelta指明了项所属的TermPosition变量在.prx文件中的位置。详细的说，就是指相对于前一个项的数据的位置偏移量（或者是0，表示文件中第一个项）。

2. 项信息索引（.tii文件）。

每个项信息索引文件包含.tis文件中的128个条目，依照条目在.tis文件中的顺序。这样设计是为了一次将索引信息读入内存能，然后使用它来随机的访问.tis文件。
这个文件的结构和.tis文件非常类似，只在每个条目记录上增加了一个变量IndexDelta。
TermInfoIndex (.tii)--> IndexTermCount, TermIndices
IndexTermCount --> UInt32
TermIndices --> <TermInfo, IndexDelta>IndexTermCount
IndexDelta --> VInt
IndexDelta表示该项的TermInfo变量值在.tis文件中的位置。详细的讲，就是指相对于前一个条目的偏移量（或者是0，对于文件中第一个项）。

4.3.7. 项频数（Frequencies）
.frq文件包含每一项的文档的列表，还有该项在对应文档中出现的频数。
FreqFile (.frq) --> <TermFreqs>TermCount
TermFreqs --> <TermFreq>DocFreq
TermFreq --> DocDelta, Freq?
DocDelta,Freq --> VInt
TermFreqs序列按照项来排序（依据于.tis文件中的项，即项是隐含存在的）。
TermFreq元组按照文档号升序排列。
DocDelta 决定了文档号和频数。详细的说，DocDelta/2表示相对于前一文档号的偏移量（或者是0，表示这是TermFreqs里面的第一项）。当 DocDelta是奇数时表示在该文档中频数为1，当DocDelta是偶数时，另一个VInt（Freq）就表示在该文档中出现的频数。
例如，假设某一项在文档7中出现一次，在文档11中出现了3次，在TermFreqs中就存在如下的VInts序列：
15, 22, 3

4.3.8. 项位置（Position）
.prx文件包含了某文档中某项出现的位置信息的列表。
ProxFile (.prx) --> <TermPositions>TermCount
TermPositions --> <Positions>DocFreq
Positions --> <PositionDelta>Freq
PositionDelta --> VInt
TermPositions按照项来排序（依据于.tis文件中的项，即项是隐含存在的）。
Positions元组按照文档号升序排列。
PositionDelta是相对于前一个出现位置的偏移位置（或者为0，表示这是第一次在这个文档中出现）。
例如，假设某一项在某文档第4项出现，在另一个文档中第5项和第9项出现，将存在如下的VInt序列：
4, 5, 4

4.3.9. 标准化因子（Normalization Factor）
.nrm文件包含了每个文档的标准化因子，标准化因子用来以后乘以这个这个域的命中数。
Norms (.nrm) --> <Byte>SegSize
每个字节记录一个浮点数。位0-2包含了3位的尾数部分，位3-8包含了5位的指数部分。
按如下规则可将这些字节转换为IEEE标准单精度浮点数：
1. 如果该字节是0，就是浮点0；
2. 否则，设置新浮点数的标志位为0；
3. 将字节中的指数加上48后作为新的浮点数的指数；
4. 将字节中的尾数映射到新浮点数尾数的高3位；并且
5. 设置新浮点数尾数的低21位为0。

4.3.10. 被删除的文档（Deleted document）
.del文件是可选的，只有在某段中存在删除操作后才存在：
Deletions (.del) --> ByteCount,BitCount,Bits
ByteSize,BitCount --> Uint32
Bits --> <Byte>ByteCount
ByteCount表示的是Bits列表中Byte的数量。典型的，它等于（SegSize/8）+1。
BitCount表示Bits列表中多少个已经被设置过了。
Bits列表包含了一些位（bit），顺序表示一个文档。当对应于文档号的位被设置了，就标志着这个文档已经被删除了。位的顺序是从低到高。因此，如果Bits包含两个字节，0x00和0x02，那么表示文档9已经删除了。

4.3.11. 局限性（Limitations）
在以上的文件格式中，好几处都有限制项和文档的最大个数为32位数的极限，即接近于40亿。今天看来，这不会造成问题，但是，长远的看，可能造成问题。因此，这些极限应该或者换为UInt64类型的值，或者更好的，换为VInt类型的值（VInt值没有上限）。

有两处地方的代码要求必须是定长的值，他们是：

1. FieldvaluesPosition变量（存储于域索引文件中，.fdx文件）。它已经是一个UInt64型，所以不会有问题。

2. TermCount变量（存储于项信息文件中，.tis文件）。这是最后输出到文件中的，但是最先被读取，因此是存储于文件的最前端 。索引代码先在这里写入一个0值，然后在其他文件输出完毕后覆盖这个值。所以无论它存储在什么地方，它都必须是一个定长的值，它应该被变成UInt64 型。
除此之外，所有的UInt值都可以换成VInt型以去掉限制。

评论

1 楼 abushuia 2008-12-23  

这个是人大的几个学生写的吧？