lucene4.5源码分析系列：lucene默认索引的文件格式-总述

学习lucene索引文件格式的目的是通过对lucene数据结构的理解，从而为lucene索引实现打下基础。

索引文件的整体结构

  如下图，这是整个索引文件的整体结构，可以看到，实际上lucene索引保存下了相当多的东西

  

  但是，单从上面的文件罗列，很难看出来一个整体的结构，那么，接下来这张图就向我们展示这个结构，原图来源于网络，但是由于已经过时，我根据lucene最新的版本重新画了一张。如果相对比3.0版就会发现，一些文件后缀也被改变了，比如tis,tii变成新的tim,tip，另外，实际上del文件也没有使用了，究其原因是writer会动态计算被删除的文件，而不是写入文件。

   索引文件中最重要的结构便是倒排索引了，如下图，其中Dictionary就是所有term的集合，放在tim和tip中，而posting list则存放文档id，词频和单词出现的位置，放在pos和doc中，其中doc存放的是词频，pos存放的是单词位置。

 

编解码器

  索引的文件格式有可能会进化，一旦版本更新之后就不能再支持其他的索引文件格式，或者说一个lucene版本只能支持lucene自己的索引势必会降低lucene的灵活性，那么如何保持索引文件格式的灵活性和动态扩展性也是一个值得考虑的问题，lucene采用编解码器（codec）来实现这种灵活性。

 

  编解码器是lucene中负责与索引文件直接读写的模块。所有的上层调用都基于编解码器，这是代码模块化的结果。我们来看编解码器的一些设计思想。

  首先是LuceneXXCodec，这是Codec的直接实现者，不同的版本可能会实现不同的codec，例如，lucene4.5就是Lucene45Codec。codec的实现采用了facade模式，屏蔽了后面的所有format

  

   因为不同的版本可能会有不同的格式，所以对应将这些格式抽象出来对于可扩展性就尤为重要了。也正是因为如此，lucene前面的版本和后面的版本格式可能差别会很大。对于我们了解lucene文件格式可能并不太好。但是lucene索引中许多精髓都类似，因而他们还是相通的，理解一种格式便于我们了解另一种。

  在lucene4系列中，4.0的实现是所有格式中最全的，其他新版本可能或多或少依赖了老版本，所以可能你运行的是lucene4.5，但实际上看到的索引文件是Lucene41_0.doc。对于几个期望更灵活的类和格式，lucene采取注册查找的方式来获得。NamedSPILoader就是负责查找Codec，PostingFormat和DocValuesFormat的类，而注册的类会放在下面的文件里。org.apache.lucene.codecs.lucene41.Lucene41Codec便是配置在Codec中的。

索引文件格式的设计技巧

  索引文件之所以是整个lucene的核心和关键，原因在于索引文件设计的好坏直接关系到时间和空间两方面因素。好的索引文件格式既要占用相对少的硬盘空间，又要支持搜索时尽可能快的查找。如果从这两方面衡量，会发现lucene中有许多精妙的设计，下面是一些罗列：

  1. 文件的内容以数字和byte组成，而数字会根据需要自动变长，从而节省空间。下面分别是DataOutput和DataInput的writeVInt, readVInt的代码（writeVLong, readVLong），从这些代码中，我们可以看出来lucene是怎么做到自动变长的。

 

public final void writeVInt(int i) throws IOException {
  while ((i & ~0x7F) != 0) {
    writeByte((byte)((i & 0x7F) | 0x80));
    i >>>= 7;
  }
  writeByte((byte)i);
}
public int readVInt() throws IOException {
  byte b = readByte();
  if (b >= 0) return b;
  int i = b & 0x7F;
  b = readByte();
  i |= (b & 0x7F) << 7;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 14;
  if (b >= 0) return i;
  b = readByte();
  i |= (b & 0x7F) << 21;
  if (b >= 0) return i;
  b = readByte();
  // Warning: the next ands use 0x0F / 0xF0 - beware copy/paste errors:
  i |= (b & 0x0F) << 28;
  if ((b & 0xF0) == 0) return i;
  throw new IOException("Invalid vInt detected (too many bits)");
}

 

  下图就是自动变长的设计原理，注意，与我们的习惯不一样的是，这里是低字节在前，高字节在后，原因是要适应这里的流式处理，顺序的将字节写入文件。可以看到，为了适应变长的设计，每个字节只能使用7位，而变长整形最多能写入1-5个字节（本例为3字节），也就是35bit，实际上正好能容纳一个int(32bit)。

  写入变长字节时先从整数的低字节处理，如果超过7个字节，则在第一个字节的第一个bit位置0，依次处理余下字节。

  而读入变长字节时也是从低字节处读入，发现该字节如果小于0，说明后续仍然有字节需要处理（第1bit为1即补码为负），依次判断并处理下一字节；如果该字节大于0，则说明此变长字节处理完毕。

  感慨lucene的设计者想出如此节省空间的方法，将一个bool型(8bit)缩减为1bit，并且简化了类型操作。而且代码也足够精巧，比如(i & ~0x7F) != 0，为什么要取0x7F的反呢，直接用0x80是不是更简单？但注意这里的i其实是一个整数，高位还有其他字节。

  2. 差值（delta）。

  差值的出现本质上是为了缩减存储空间，基于前面的自动变长，能够让差值工作得更顺畅。

  如图，在许多地方都会存储一组从小到大的顺序值，或者将已有数据调整为顺序值，如果采用vint，则每个值都需要2个字节，但是采用差值方法来处理的话，除了第一个159需要2字节（根据自动变长，超过127的便会扩展到2字节），后面的5个数字都只需要1字节，如此便节省了空间。如果你对节省下来的这点空间不以为然，那么请将如下的int数组放大到G，就可以明白这其中的奥妙了。

  3. 跳跃表(skip list)

  跳跃表其实典型的是以空间换时间的方式，通过增加额外的存储空间（即索引）来更快速的定位元素位置。在lucene中，它被用来写入下面这3类文件，即doc，pos，pay
  跳跃表的具体实现这里就不细讲了，MultiLevelSkipListWriter中有具体实现。这里仅浅显的讲讲跳跃表怎么工作的。跳跃表分为n层（默认为10），每层的跳跃间隔为s（默认为128，即块大小），每次搜索时从最高层开始定位，逐层向下找到元素（其思想有些类似二分搜索），可大幅缩减搜索时间。比如要查找20，首先查找第二层27，发现在27之后，于是查找第一层9,18，由于27大于20，于是查找第0层18，19，20

  

   4. 压缩数组(packed array)

  压缩数组主要目的是为了减少内存的浪费，比如这样的情况，当你申请16位整数时能存放16bit的二进制，但是一旦大于16bit(小于32bit)  ，比如17bit，你就得申请32位整数来存放17bit，空间浪费率是47%。所以需要通过压缩数组来将数字打包成一块一块的，从而减少空间浪费。压缩数组的实现有很多方式，比如下图1中的跨block分割存储，或者图2中的跨block存储。lucene中的实现是取一个块的每个数据中最长的bit数来存放每个数据，在数据大小比较均匀的情况下，这种方式会浪费尽可能少的空间。在lucene中，真正实现这部分功能的类是ForUtil，BulkOperationPacked，BulkOperationPackedSingleBlock，PackedInts等，有兴趣的同学可以参考。关于压缩数组的参考资料，也在文末列出一部分。

  索引策略

  主要介绍下常见的建立索引的策略。

  1. 2遍扫描法。所有操作在内存中进行，需要消耗大量内存，内存不足时无法完成索引操作。第一遍扫描主要做准备，得到一些全局的统计信息并且分配好接下来准备使用的内存；第二遍扫描则填充相应的信息到已分配好的内存中间。

  2. 排序法。排序法在内存中分配固定大小的内存来存放词典和三元组（即单词ID，文档ID，单词频率），当内存不够时，将三元组合并到磁盘中，但是词典仍然驻留内存（一个hash表放在内存要快很多），词典在后期也会越来越大，导致可用内存越来越少。

  3. 归并法。归并法则是在内存中建立一整套完整的索引，当内存不足时将整套新索引以类似更新索引的方式合并到旧索引中去。从lucene的实现来看，便是用类似这样的策略

 

  lucene索引文件 http://www.cnblogs.com/forfuture1978/archive/2009/12/14/1623597.html

  跳跃表 http://zh.wikipedia.org/wiki/%E8%B7%B3%E8%B7%83%E5%88%97%E8%A1%A8

  压缩数组 http://blog.jpountz.net/post/25530978824/how-fast-is-bit-packing

                   http://pempek.net/articles/2013/08/03/packedarray-random-access-array-tightly-packed-unsigned-integers/

                   http://software.intel.com/en-us/articles/paos-packed-array-of-structures

http://blog.csdn.net/liweisnake/article/details/10956645