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

      • numberOfSkipLevels

        protected int numberOfSkipLevels
        number of levels in this skip list
    • 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