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. The storage manager does not provide complete support for non-unique multidimensional indexes. While you may insert multiple (distinct) entries for the same key in a multi-dimensional index, you will not be able to use them; only the first can be retrieved.
static rc_t	ss_m::destroy_md_index (const stid_t &iid)
	Destroy an R*-Tree index.
static rc_t	ss_m::print_md_index (stid_t stid, ostream &out)
	Print a representation of the rtree.
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. The storage manager does not provide complete support for non-unique multidimensional indexes. While you may insert multiple (distinct) entries for the same key in a multi-dimensional index, you will not be able to use them; only the first can be retrieved.
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. The storage manager does not provide complete support for non-unique multidimensional indexes. While you may insert multiple (distinct) entries for the same key in a multi-dimensional index, you will not be able to use them; only the first can be retrieved.

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::print_md_index	(	stid_t	stid,
		ostream &	out
	)			[static, inherited]

Print a representation of the rtree.

Parameters:

[in]	stid	ID of the index to be printed.
[in]	out	I/O stream to which to write the output.

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.

If the index is not unique (allows duplicates), the first element found with the given key will be returned.

The storage manager does not provide a method to locate all entries associated with a non-unique key.

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. The storage manager does not provide complete support for non-unique multidimensional indexes. While you may insert multiple (distinct) entries for the same key in a multi-dimensional index, you will not be able to use them; only the first can be retrieved.

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

---