Package org.apache.lucene.codecs

Class MultiLevelSkipListWriter

java.lang.Object
org.apache.lucene.codecs.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 guarantees 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.
WARNING: This API is experimental and might change in incompatible ways in the next release.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    protected final int
    numberOfSkipLevels
    number of levels in this skip list

  • Constructor Summary

    Constructors
    Modifier
    Constructor
    Description
    protected
    MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)
    Creates a MultiLevelSkipListWriter, where skipInterval and skipMultiplier are the same.
    protected
    MultiLevelSkipListWriter(int skipInterval, int skipMultiplier, int maxSkipLevels, int df)
    Creates a MultiLevelSkipListWriter.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    bufferSkip(int df)
    Writes the current skip data to the buffers.
    protected void
    init()
    Allocates internal skip buffers.
    protected void
    resetSkip()
    Creates new buffers or empties the existing ones
    protected void
    writeChildPointer(long childPointer, DataOutput skipBuffer)
    Writes the child pointer of a block to the given output.
    protected void
    writeLevelLength(long levelLength, IndexOutput output)
    Writes the length of a level to the given output.
    long
    writeSkip(IndexOutput output)
    Writes the buffered skip lists to the given output.
    protected abstract void
    writeSkipData(int level, DataOutput skipBuffer)
    Subclasses must implement the actual skip data encoding in this method.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • numberOfSkipLevels

      protected final int numberOfSkipLevels
      number of levels in this skip list

  • Constructor Details

    • MultiLevelSkipListWriter

      protected MultiLevelSkipListWriter(int skipInterval, int skipMultiplier, int maxSkipLevels, int df)
      Creates a MultiLevelSkipListWriter.

    • MultiLevelSkipListWriter

      protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)
      Creates a MultiLevelSkipListWriter, where skipInterval and skipMultiplier are the same.

  • Method Details

    • init

      protected void init()
      Allocates internal skip buffers.

    • resetSkip

      protected void resetSkip()
      Creates new buffers or empties the existing ones

    • writeSkipData

      protected abstract void writeSkipData(int level, DataOutput skipBuffer) throws IOException
      Subclasses must implement the actual skip data encoding in this method.
      Parameters:
      level - the level skip data shall be writing for
      skipBuffer - the skip buffer to write to
      Throws:
      IOException

    • bufferSkip

      public void bufferSkip(int df) throws IOException
      Writes the current skip data to the buffers. The current document frequency determines the max level is skip data is to be written to.
      Parameters:
      df - the current document frequency
      Throws:
      IOException - If an I/O error occurs

    • writeSkip

      public long writeSkip(IndexOutput output) throws IOException
      Writes the buffered skip lists to the given output.
      Parameters:
      output - the IndexOutput the skip lists shall be written to
      Returns:
      the pointer the skip list starts
      Throws:
      IOException

    • writeLevelLength

      protected void writeLevelLength(long levelLength, IndexOutput output) throws IOException
      Writes the length of a level to the given output.
      Parameters:
      levelLength - the length of a level
      output - the IndexOutput the length shall be written to
      Throws:
      IOException

    • writeChildPointer

      protected void writeChildPointer(long childPointer, DataOutput skipBuffer) throws IOException
      Writes the child pointer of a block to the given output.
      Parameters:
      childPointer - block of higher level point to the lower level
      skipBuffer - the skip buffer to write to
      Throws:
      IOException