R+ tree

R+ tree

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 K-D-B trees; they avoid overlapping of internal nodes by inserting an object into multiple leaves if necessary.

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.

Algorithm

ee also

*R tree
*R* tree
*Hilbert R-tree

External links

References

T. Sellis, N. Roussopoulos, and C. Faloutsos. [http://citeseer.ist.psu.edu/sellis87rtree.html The R+-Tree: A dynamic index for multi-dimensional objects] . In VLDB, 1987.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Tree — /tree/, n. Sir Herbert Beerbohm /bear bohm/, (Herbert Beerbohm), 1853 1917, English actor and theater manager; brother of Max Beerbohm. * * * I Woody perennial plant. Most trees have a single self supporting trunk containing woody tissues, and in …   Universalium

  • Tree — (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree, oak, do ry… …   The Collaborative International Dictionary of English

  • Tree bear — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree beetle — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree bug — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cat — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree clover — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crab — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree creeper — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree cricket — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

  • Tree crow — Tree Tree (tr[=e]), n. [OE. tree, tre, treo, AS. tre[ o], tre[ o]w, tree, wood; akin to OFries. tr[=e], OS. treo, trio, Icel. tr[=e], Dan. tr[ae], Sw. tr[ a], tr[ a]d, Goth. triu, Russ. drevo, W. derw an oak, Ir. darag, darog, Gr. dry^s a tree,… …   The Collaborative International Dictionary of English

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”