Class MultiLevelSkipListWriter

  • Direct Known Subclasses:
    Lucene90SkipWriter, Lucene99SkipWriter, SimpleTextSkipWriter

    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.
     
    • Field Summary

      Fields 
      Modifier and Type Field Description
      protected int numberOfSkipLevels
      number of levels in this skip list
      private ByteBuffersDataOutput[] skipBuffer
      for every skip level a different buffer is used
      private int skipInterval
      the skip interval in the list with level = 0
      private int skipMultiplier
      skipInterval used for level > 0
      private int windowLength
      Length of the window at which the skips are placed on skip level 1
    • 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
      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 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
      • windowLength

        private final int windowLength
        Length of the window at which the skips are placed on skip level 1
    • 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,
                                              DataOutput 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
      • writeLevelLength

        protected void writeLevelLength​(long levelLength,
                                        IndexOutput output)
                                 throws java.io.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:
        java.io.IOException
      • writeChildPointer

        protected void writeChildPointer​(long childPointer,
                                         DataOutput skipBuffer)
                                  throws java.io.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:
        java.io.IOException