org.geogit.api

Class HRPlusTree

java.lang.Object

org.geogit.api.HRPlusTreeUtils

org.geogit.api.HRPlusTree

public class HRPlusTree
extends HRPlusTreeUtils

Implementation of the HRPlus tree described in [1] http://www.cs.ust.hk/faculty/dimitris/PAPERS/ssdbm01.pdf We chose the HRPlus tree for the spatial index because it provides - Provides access to past versions. Keeps a history. - Provides multiple roots. Multiple entry points. - Trees share branches when data doesn't change - Space-efficient - Improved query performance over regular R-Tree or Historical R-Tree

Constructor Summary

Constructors

Constructor and Description
HRPlusTree()

Method Summary

Methods

Modifier and Type	Method and Description
void	insert(ObjectId layerId, Envelope bounds) Insertion algorithm, roughly: - Create an HRPlus node from @param layerId and @param bounds - Find the correct container node to insert into.
HRPlusContainerNode	lookupHRPlusContainerNode(ObjectId objectId)
HRPlusNode	lookupHRPlusNode(ObjectId objectId)
java.util.List<HRPlusNode>	query(Envelope env) Bounding box query.

Methods inherited from class org.geogit.api.HRPlusTreeUtils

boundingBoxOf, getOverlap, getTotalAreaOfTwoRegions, marginOf, maxXSort, maxYSort, minXSort, minYSort, partitionByMinOverlap, sumOfMargins

Methods inherited from class java.lang.Object

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

Constructor Detail

HRPlusTree

public HRPlusTree()

Method Detail

insert

public void insert(ObjectId layerId,
          Envelope bounds)

Insertion algorithm, roughly: - Create an HRPlus node from @param layerId and @param bounds - Find the correct container node to insert into. Insert node into container. - Check for degree overflow, if so, rebalance the tree. - Re-organize tree among roots, add any new roots to the @field rootMap.

Parameters:

layerId -

bounds -

query

public java.util.List<HRPlusNode> query(Envelope env)

Bounding box query. Search the tree for nodes within the given envelope. Start at the roots, search all those containers. In each container, search the nodes contained within and their respective containers.

Parameters:

env -

Returns:

lookupHRPlusContainerNode

public HRPlusContainerNode lookupHRPlusContainerNode(ObjectId objectId)

Parameters:

objectId -

Returns:

the container associated with @param objectId

lookupHRPlusNode

public HRPlusNode lookupHRPlusNode(ObjectId objectId)