Package org.apache.lucene.codecs

Class MultiLevelSkipListWriter

  • Direct Known Subclasses:
    Lucene84SkipWriter
    public abstract class MultiLevelSkipListWriter
extends java.lang.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.

    • 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

      All Methods Instance Methods Abstract Methods Concrete Methods 
      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
      long writeSkip​(IndexOutput output)
      Writes the buffered skip lists to the given output.
      protected abstract void writeSkipData​(int level, IndexOutput 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 Detail

      • numberOfSkipLevels

        protected final int numberOfSkipLevels
        number of levels in this skip list

      • skipInterval

        private final int skipInterval
        the skip interval in the list with level = 0

      • skipMultiplier

        private final int skipMultiplier
        skipInterval used for level > 0

      • skipBuffer

        private RAMOutputStream[] skipBuffer
        for every skip level a different buffer is used

    • Constructor Detail

      • 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 Detail

      • 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,
                                      IndexOutput skipBuffer)
                               throws java.io.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:
        java.io.IOException

      • bufferSkip

        public void bufferSkip​(int df)
                throws java.io.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:
        java.io.IOException - If an I/O error occurs

      • writeSkip

        public long writeSkip​(IndexOutput output)
               throws java.io.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:
        java.io.IOException