Package org.apache.cassandra.index.sai.disk.v1.bbtree

Class BlockBalancedTreeWriter

java.lang.Object

org.apache.cassandra.index.sai.disk.v1.bbtree.BlockBalancedTreeWriter

@NotThreadSafe
public class BlockBalancedTreeWriter
extends Object

This is a specialisation of the Lucene BKDWriter that only writes a single dimension balanced tree.

Recursively builds a block balanced tree to assign all incoming points to smaller and smaller rectangles (cells) until the number of points in a given rectangle is <= maxPointsInLeafNode. The tree is fully balanced, which means the leaf nodes will have between 50% and 100% of the requested maxPointsInLeafNode. Values that fall exactly on a cell boundary may be in either cell.

Visual representation of the disk format:

 +========+=======================================+==================+========+
 | HEADER | LEAF BLOCK LIST                       | BALANCED TREE    | FOOTER |
 +========+================+=====+================+==================+========+
          | LEAF BLOCK (0) | ... | LEAF BLOCK (N) | VALUES PER LEAF  |
          +----------------+-----+----------------+------------------|
          | ORDER INDEX    |                      | BYTES PER VALUE  |
          +----------------+                      +------------------+
          | PREFIX         |                      | NUMBER OF LEAVES |
          +----------------+                      +------------------+
          | VALUES         |                      | MINIMUM VALUE    |
          +----------------+                      +------------------+
                                                  | MAXIMUM VALUE    |
                                                  +------------------+
                                                  | TOTAL VALUES     |
                                                  +------------------+
                                                  | INDEX TREE       |
                                                  +--------+---------+
                                                  | LENGTH | BYTES   |
                                                  +--------+---------+
  

NOTE: This can write at most Integer.MAX_VALUE * maxPointsInLeafNode total points.

See Also:

• BKDWriter

Field Summary

Fields

Modifier and Type	Field	Description
static final boolean	DEBUG
static final int	DEFAULT_MAX_POINTS_IN_LEAF_NODE

Constructor Summary

Constructors

Constructor	Description
BlockBalancedTreeWriter(int bytesPerValue, int maxPointsInLeafNode)

Method Summary

Modifier and Type	Method	Description
int	getBytesPerValue()
int	getMaxPointsInLeafNode()
long	getValueCount()
long	write(org.apache.lucene.store.IndexOutput treeOutput, Iterator<IndexEntry> iterator, org.apache.cassandra.index.sai.disk.v1.bbtree.BlockBalancedTreeWriter.Callback callback)	Write the sorted values from an Iterator.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Details

DEBUG

public static final boolean DEBUG

DEFAULT_MAX_POINTS_IN_LEAF_NODE

public static final int DEFAULT_MAX_POINTS_IN_LEAF_NODE

See Also:

• Constant Field Values

Constructor Details

BlockBalancedTreeWriter

public BlockBalancedTreeWriter(int bytesPerValue,
 int maxPointsInLeafNode)

Method Details

getValueCount

public long getValueCount()

getBytesPerValue

public int getBytesPerValue()

getMaxPointsInLeafNode

public int getMaxPointsInLeafNode()

write

public long write(org.apache.lucene.store.IndexOutput treeOutput,
 Iterator<IndexEntry> iterator,
 org.apache.cassandra.index.sai.disk.v1.bbtree.BlockBalancedTreeWriter.Callback callback)
           throws IOException

Write the sorted values from an Iterator.

Parameters:

treeOutput - The IndexOutput to write the balanced tree to

iterator - An Iterator of IndexEntrys containing the terms and postings, sorted in term order

callback - The BlockBalancedTreeWriter.Callback used to record the leaf postings for each leaf

Returns:

The file pointer to the beginning of the balanced tree

Throws:

IOException