Package org.apache.druid.collections.spatial

Class RTree

java.lang.Object

org.apache.druid.collections.spatial.RTree

public class RTree
extends Object

This RTree has been optimized to work with bitmap inverted indexes. This code will probably make a lot more sense if you read: http://www.sai.msu.su/~megera/postgres/gist/papers/gutman-rtree.pdf

Constructor Summary

Constructors

Constructor	Description
RTree(int numDims, SplitStrategy splitStrategy, BitmapFactory bitmapFactory)

Method Summary

Modifier and Type	Method	Description
BitmapFactory	getBitmapFactory()
int	getNumDims()
Node	getRoot()
int	getSize()
void	insert(float[] coords, int entry)	This description is from the original paper.
void	insert(float[] coords, MutableBitmap entry)

Methods inherited from class java.lang.Object

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

Constructor Details

RTree

public RTree(int numDims,
 SplitStrategy splitStrategy,
 BitmapFactory bitmapFactory)

Method Details

getBitmapFactory

public BitmapFactory getBitmapFactory()

insert

public void insert(float[] coords,
 int entry)

This description is from the original paper. Algorithm Insert: Insert a new index entry E into an R-tree. I1. [Find position for new record]. Invoke chooseLeaf(Node, Point) to select a leaf node L in which to place E. I2. [Add records to leaf node]. If L has room for another entry, install E. Otherwise invoke SplitStrategy split methods to obtain L and LL containing E and all the old entries of L. I3. [Propagate changes upward]. Invoke adjustTree(Node, Node) on L, also passing LL if a split was performed. I4. [Grow tree taller]. If node split propagation caused the root to split, create a new record whose children are the two resulting nodes.

Parameters:

coords - - the coordinates of the entry

entry - - the integer to insert

insert

public void insert(float[] coords,
 MutableBitmap entry)

getSize

public int getSize()

getNumDims

public int getNumDims()

getRoot

public Node getRoot()