Package org.apache.lucene.codecs
Class MultiLevelSkipListWriter
java.lang.Object
org.apache.lucene.codecs.MultiLevelSkipListWriter
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
FieldsModifier and TypeFieldDescriptionprotected int
number of levels in this skip list -
Constructor Summary
ConstructorsModifierConstructorDescriptionprotected
MultiLevelSkipListWriter
(int skipInterval, int maxSkipLevels, int df) Creates aMultiLevelSkipListWriter
, whereskipInterval
andskipMultiplier
are the same.protected
MultiLevelSkipListWriter
(int skipInterval, int skipMultiplier, int maxSkipLevels, int df) Creates aMultiLevelSkipListWriter
. -
Method Summary
Modifier and TypeMethodDescriptionvoid
bufferSkip
(int df) Writes the current skip data to the buffers.protected void
init()
Allocates internal skip buffers.protected void
Creates new buffers or empties the existing oneslong
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.
-
Field Details
-
numberOfSkipLevels
protected int numberOfSkipLevelsnumber of levels in this skip list
-
-
Constructor Details
-
MultiLevelSkipListWriter
protected MultiLevelSkipListWriter(int skipInterval, int skipMultiplier, int maxSkipLevels, int df) Creates aMultiLevelSkipListWriter
. -
MultiLevelSkipListWriter
protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) Creates aMultiLevelSkipListWriter
, whereskipInterval
andskipMultiplier
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
Subclasses must implement the actual skip data encoding in this method.- Parameters:
level
- the level skip data shall be writing forskipBuffer
- the skip buffer to write to- Throws:
IOException
-
bufferSkip
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
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
-