Cesko.wiki R-strom
Author
Albert FloresSchéma R-stromů na jednoduchém příkladu. R-strom je stromová datová struktura podobná B-stromům, ale používaná pro prostorové přístupové metody, například pro indexovaní vícerozměrných struktur například v geografických informačních systémech. Mimo to, pomocí R-stromů je implementováno například datové úložiště MyISAM v MySQL.
Datová struktura dělí místo na hierarchicky vkládané a potenciálně se překrývající, tzv. MBR (minimum bounding rectangles - minimální ohraničující obdélníky, též nazývané obdélníky nebo boxy - R z anglického výrazu pro obdélník (rectangle) tvoří část názvu R-stromů).
Každý uzel R-stromu má proměnlivý počet záznamů (až do předdefinovaného maxima). Každý záznam uvnitř uzlu, který není listem, ukládá dvě další informace: způsob identifikace dceřiného uzlu a MBR všech záznamů uvnitř tohoto dceřiného uzlu.
Algoritmy pro vložení nového a smazání stávajícího prvku používají MBR z uzlů ke kontrole, že prvky v geometrickém okolí jsou umístěny do stejných listových uzlů (konkrétně, nový prvek půjde do listového uzlu, který potřebuje nejmenší rozšíření svého MBR). Každý záznam uvnitř listového uzlu uloží dvě informace: identifikátor daného prvku (který může být alternativně umístěn přímo do uzlu) a MBR datového prvku.
Podobně, vyhledávací algoritmy používají MBR k rozhodnutí, zdali hledat uvnitř daného uzlu. Tímto způsobem při hledání většina uzlů „netknutých“. +more Stejně jako B-stromy, jsou R-stromy vhodné pro databáze, kde se uzly podle potřeby mohou načítat do paměti.
U R-stromů lze nastavit nejen maximální počet prvků v něm, ale i algoritmus, kdy se má daný list změnit v uzel další úrovně. Mezi tyto algoritmy patří: * linear-cost algoritm * quadratic-cost algoritm * exhaustive algoritm
R-stromy nezaručují dobrý výkon pro nejnepříznivější případ uložení dat, ale jejich implementace dosahují slušných výkonů při použití „reálných“ dat. V roce 2004 byl nicméně vyvinut nový algoritmus, Priority R-Tree, který má výkon vylepšovat právě pro nepříznivě uložená data.
Varianty
R* strom * R+ strom * Hilbertův R-strom * Prioritní R-strom (PR-strom)
Odkazy
Reference
Literatura
Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. +more 47-57. * Yannis Manolopoulos, Alexandros Nanopoulos, Apostolos N. Papadopoulos, Yannis Theodoridis: R-Trees: Theory and Applications, Springer, 2005. * [url=http://dbs. mathematik. uni-marburg. de/publications/myPapers/1990/BKSS90. pdf]N. Beckmann, H. -P. Kriegel, R. Schneider, B. Seeger: The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD Conference 1990: 322-331[/url].
Externí odkazy
[url=http://www. rtreeportal. +moreorg/]R-tree portal[/url] * [url=http://www-db. deis. unibo. it/courses/SI-LS/papers/Gut84. pdf]R-Trees: A Dynamic Index Structure for Spatial Searching[/url] * implementace R-stromu: [url=http://gis. umb. no/gis/applets/rtree2/jdk1. 1/]Java applet[/url] , [url=http://www. cliki. net/spatial-trees]Common Lisp[/url], [url=https://web. archive. org/web/20110208001256/http://e-dynamica. com/]. NET[/url], [url=http://pypi. python. org/pypi/Rtree/]Python[/url].
