R+ tree

An R+ tree is a method for looking up data using a location, often (x, y) coordinates, and often for locations on the surface of the earth. Searching on one number is a solved problem; searching on two or more, and asking for locations that are nearby in both x and y directions, requires craftier algorithms.

Fundamentally, an R+ tree is a tree data structure, a variant of the R tree, used for indexing spatial information.

Difference between R+ trees and R trees

R+ trees are a compromise between R-trees and kd-trees: they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary. Coverage is the entire area to cover all related rectangles. Overlap is the entire area which is contained in two or more nodes.^[1] Minimal coverage reduces the amount of "dead space" (empty area) which is covered by the nodes of the R-tree. Minimal overlap reduces the set of search paths to the leaves (even more critical for the access time than minimal coverage). Efficient search requires minimal coverage and overlap.

R+ trees differ from R trees in that:

Nodes are not guaranteed to be at least half filled
The entries of any internal node do not overlap
An object ID may be stored in more than one leaf node

Advantages

Because nodes are not overlapped with each other, point query performance benefits since all spatial regions are covered by at most one node.
A single path is followed and fewer nodes are visited than with the R-tree

Disadvantages

Since rectangles are duplicated, an R+ tree can be larger than an R tree built on same data set.
Construction and maintenance of R+ trees is more complex than the construction and maintenance of R trees and other variants of the R tree.

Notes

↑ Härder, Rahm, Theo, Erhard (2007). Datenbanksysteme. (2., überarb. Aufl. ed.). Berlin [etc.]: Gardners Books. pp. 285, 286. ISBN 3-540-42133-5.

References

T. Sellis, N. Roussopoulos, and C. Faloutsos. The R+-Tree: A dynamic index for multi-dimensional objects. In VLDB, 1987.

Tree data structures

Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced

Heaps	Binary Binomial Fibonacci Leftist Pairing Skew Van Emde Boas

Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast

Spatial data partitioning trees	BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X

Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

Data structures

Types	Collection Container

Abstract	Associative array Multimap List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set

Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse array

Linked	Association list Linked list Skip list Unrolled linked list XOR linked list

Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree

Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph

List of data structures

This article is issued from Wikipedia - version of the Monday, July 22, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.