org.apache.lucene.codecs

Class 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.
     
    • Field Detail

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