|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object org.apache.lucene.codecs.MultiLevelSkipListWriter
public abstract class 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 | |
---|---|
protected int |
numberOfSkipLevels
number of levels in this skip list |
Constructor Summary | |
---|---|
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 | |
---|---|
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 |
---|
protected int numberOfSkipLevels
Constructor Detail |
---|
protected MultiLevelSkipListWriter(int skipInterval, int skipMultiplier, int maxSkipLevels, int df)
MultiLevelSkipListWriter
.
protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df)
MultiLevelSkipListWriter
, where
skipInterval
and skipMultiplier
are
the same.
Method Detail |
---|
protected void init()
protected void resetSkip()
protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException
level
- the level skip data shall be writing forskipBuffer
- the skip buffer to write to
IOException
public void bufferSkip(int df) throws IOException
df
- the current document frequency
IOException
- If an I/O error occurspublic long writeSkip(IndexOutput output) throws IOException
output
- the IndexOutput the skip lists shall be written to
IOException
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |