R-tree
Sign in to savethumb|400px|right|Simple example of an R-tree for 2D rectangles thumb|400px|right|Visualization of an R*-tree for 3D points using ELKI (the [[cuboids are directory pages)]]
Key facts
- Data structure.name
- R-tree
- Data structure.type
- tree
- Data structure.invented_by
- Antonin Guttman
- Data structure.invented_year
- 1984
- Data structure.search_avg
- O(logMn)
- Data structure.search_worst
- O(n)
- Data structure.insert_worst
- O(n)
via Wikipedia infobox
Article
13 sectionsContents
- R-tree idea
- Variants
- Algorithm
- Data layout
- Search
- Insertion
- Choosing the insertion subtree
- Splitting an overflowing node
- Deletion
- Bulk-loading
- See also
- References
- External links
thumb|400px|right|Simple example of an R-tree for 2D rectangles thumb|400px|right|Visualization of an R*-tree for 3D points using ELKI (the [[cuboids are directory pages)]]
R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons. The R-tree was proposed by Antonin Guttman in 1984 and has found significant use in both theoretical and applied contexts. A common real-world usage for an R-tree might be to store spatial objects such as restaurant locations or the polygons that typical maps are made of: streets, buildings, outlines of lakes, coastlines, etc. and then find answers quickly to queries such as "Find all museums within 2 km of my current location", "retrieve all road segments within 2 km of my location" (to display them in a navigation system) or "find the nearest gas station" (although not taking roads into account). The R-tree can also accelerate nearest neighbor search for various distance metrics, including great-circle distance.