R-Tree Indexes
[Storage Structures]

Collaboration diagram for R-Tree Indexes:

---

Detailed Description

An R-tree is a height-balanced structure designed for indexing multi-dimensional spatial objects. It stores the minimial bounding box (with 2 or higher dimension) of a spatial object as the key in the leaf pages. This implementation is a variant of an R-Tree called an R*-Tree, which improves the search performance by using a heuristic for redistributing entries and dynamically reorganizing the tree during insertion.

An R*-Tree stores key,value pairs where the key is of type nbox_t and the value is of type vec_t.

The number of key-value pairs an index can hold is limited by the space available on the volume containing the index. The minimum size of an R*-tree index is 8 pages.

Note:

This implementation uses coarse-grained (index-level) locking and supports only 2 dimensions and integer coordinates. For information about R*-trees, see the [BKSS].

Example:

     scan_rt_i scan(idx, nbox_t::t_overlap, universe, true);
     bool      eof;
     nbox_t    k;
     char*     e;
     smsize_t  elen;

     for(int i=0; 
             (!(rc = scanp->next(k,e,elen,eof)).is_error() && !eof);
             i++) ;
     cout << "Rtree " << idx << " contains " << i << " entries." << endl;

Bulk Loading

Bulk-loading of all index types is supported. See Bulk-Loading Indexes.

Functions
static rc_t	ss_m::create_md_index (vid_t vid, ndx_t ntype, store_property_t property, stid_t &stid, int2_t dim=2)
	Create an R*-Tree (multi-dimensional spatial) index.
static rc_t	ss_m::destroy_md_index (const stid_t &iid)
	Destroy an R*-Tree index.
static rc_t	ss_m::find_md_assoc (stid_t stid, const nbox_t &key, void *el, smsize_t &elen, bool &found)
	Look up an entry in a multi-dimensional index.
static rc_t	ss_m::create_md_assoc (stid_t stid, const nbox_t &key, const vec_t &el)
	Create an entry in a multi-dimensional index.
static rc_t	ss_m::destroy_md_assoc (stid_t stid, const nbox_t &key, const vec_t &el)
	Destroy an entry in a multi-dimensional index.
static rc_t	ss_m::rtree_stats (const stid_t &stid, rtree_stats_t &stat, uint2_t size=0, uint2_t *ovp=NULL, bool audit=false)
	Gather usage statistics about an R*-Tree index.

---

Function Documentation

static rc_t ss_m::create_md_index	(	vid_t	vid,
		ndx_t	ntype,
		store_property_t	property,
		stid_t &	stid,
		int2_t	dim = 2
	)			[static, inherited]

Create an R*-Tree (multi-dimensional spatial) index.

Parameters:

[in]	vid	Volume on which to create the index.
[in]	ntype	Type of index. Legitimate values are: t_rtree : R*-Tree
[in]	property	Logging level of store. Legitimate values are: t_temporary t_regular t_load_file t_insert_file See sm_store_property_t for details.
[in]	dim	Number of dimensions of the key. They key type is an nbox_t. See nbox_t for details.
[out]	stid	New store ID will be returned here.

static rc_t ss_m::destroy_md_index

(

const stid_t &

iid

)

[static, inherited]

Destroy an R*-Tree index.

Parameters:

[in]

iid

ID of the index to be destroyed.

static rc_t ss_m::find_md_assoc	(	stid_t	stid,
		const nbox_t &	key,
		void *	el,
		smsize_t &	elen,
		bool &	found
	)			[static, inherited]

Look up an entry in a multi-dimensional index.

Parameters:

[in]	stid	ID of the index.
[in]	key	Key associated with the entry to look up.
[out]	el	Element associated with the given key will be copied into this buffer.
[in]	elen	Length of buffer into which the result will be written. If too small, eRECWONTFIT will be returned. Length of result will be returned here.
[out]	found	True if an entry is found.

static rc_t ss_m::create_md_assoc	(	stid_t	stid,
		const nbox_t &	key,
		const vec_t &	el
	)			[static, inherited]

Create an entry in a multi-dimensional index.

Parameters:

[in]	stid	ID of the index.
[in]	key	Key for the association to be created.
[in]	el	Element for the association to be created.

static rc_t ss_m::destroy_md_assoc	(	stid_t	stid,
		const nbox_t &	key,
		const vec_t &	el
	)			[static, inherited]

Destroy an entry in a multi-dimensional index.

Parameters:

[in]	stid	ID of the index.
[in]	key	Key of the entry to be removed.
[in]	el	Element (value) of the entry to be removed.

static rc_t ss_m::rtree_stats	(	const stid_t &	stid,
		rtree_stats_t &	stat,
		uint2_t	size = 0,
		uint2_t *	ovp = NULL,
		bool	audit = false
	)			[static, inherited]

Gather usage statistics about an R*-Tree index.

Parameters:

[in]	stid	ID of the index.
[out]	stat	Usage statistics will be written here.
[in]	size	Number of uint2_t's in the array ovp.
[out]	ovp	Pre-allocated array of integers into which the method will write the overlap percentages for each level of the tree.
[in]	audit	If "true", the method will check assertions about the correctness of the rtree. If the audit fails an internal fatal error is generated to facilitate debugging. (It will generate a core file if your shell permits such.)

Note:

for debugging

---