FileDocCategorySizeDatePackage
MultiLevelSkipListWriter.javaAPI DocApache Lucene 2.2.05311Sat Jun 16 22:20:36 BST 2007org.apache.lucene.index

MultiLevelSkipListWriter

public abstract class MultiLevelSkipListWriter extends Object
This abstract class writes skip lists with multiple levels. Example for skipInterval = 3: c (skip level 2) c c c (skip level 1) x x x x x x x x x x (skip level 0) d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d (posting list) 3 6 9 12 15 18 21 24 27 30 (df) d - document x - skip data c - skip data with child pointer Skip level i contains every skipInterval-th entry from skip level i-1. Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))). Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1. This guarantess a logarithmic amount of skips to find the target document. While this class takes care of writing the different skip levels, subclasses must define the actual format of the skip data.

Fields Summary
private int
numberOfSkipLevels
private int
skipInterval
private RAMOutputStream[]
skipBuffer
Constructors Summary
protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)

    this.skipInterval = skipInterval;
    
    // calculate the maximum number of skip levels for this document frequency
    numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df) / Math.log(skipInterval));
    
    // make sure it does not exceed maxSkipLevels
    if (numberOfSkipLevels > maxSkipLevels) {
      numberOfSkipLevels = maxSkipLevels;
    }
Methods Summary
voidbufferSkip(int df)
Writes the current skip data to the buffers. The current document frequency determines the max level is skip data is to be written to.

param
df the current document frequency
throws
IOException

    int numLevels;
   
    // determine max level
    for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {
      numLevels++;
    }
    
    long childPointer = 0;
    
    for (int level = 0; level < numLevels; level++) {
      writeSkipData(level, skipBuffer[level]);
      
      long newChildPointer = skipBuffer[level].getFilePointer();
      
      if (level != 0) {
        // store child pointers for all levels except the lowest
        skipBuffer[level].writeVLong(childPointer);
      }
      
      //remember the childPointer for the next level
      childPointer = newChildPointer;
    }
protected voidinit()

    skipBuffer = new RAMOutputStream[numberOfSkipLevels];
    for (int i = 0; i < numberOfSkipLevels; i++) {
      skipBuffer[i] = new RAMOutputStream();
    }
protected voidresetSkip()

    // creates new buffers or empties the existing ones
    if (skipBuffer == null) {
      init();
    } else {
      for (int i = 0; i < skipBuffer.length; i++) {
        skipBuffer[i].reset();
      }
    }
longwriteSkip(org.apache.lucene.store.IndexOutput output)
Writes the buffered skip lists to the given output.

param
output the IndexOutput the skip lists shall be written to
return
the pointer the skip list starts

    long skipPointer = output.getFilePointer();
    if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;
    
    for (int level = numberOfSkipLevels - 1; level > 0; level--) {
      long length = skipBuffer[level].getFilePointer();
      if (length > 0) {
        output.writeVLong(length);
        skipBuffer[level].writeTo(output);
      }
    }
    skipBuffer[0].writeTo(output);
    
    return skipPointer;
protected abstract voidwriteSkipData(int level, org.apache.lucene.store.IndexOutput skipBuffer)
Subclasses must implement the actual skip data encoding in this method.

param
level the level skip data shall be writting for
param
skipBuffer the skip buffer to write to