V R-stromy jsou datové struktury ve formě hřídele používané jako metody průzkumu vesmíru . Používají se k indexování vícerozměrných informací ( zeměpisné souřadnice , obdélníky nebo mnohoúhelníky ). R-stromy, které vynalezl Antonin Guttman v roce 1984, se používají v teoretických i aplikovaných kontextech. Typickým případem použití pro stromy R je ukládání geografických informací: například umístění restaurací ve městě nebo polygony, které tvoří kresby mapy (silnice, budovy, pobřeží atd.), A poté schopen reagovat na dotazy jako „najít všechna muzea v okruhu 2 kilometrů“, „zobrazit všechny silnice do 5 kilometrů“ nebo „najít nejbližší čerpací stanici k mé poloze. poloha“, například v navigační aplikaci.
R-stromy lze také použít k urychlení hledání K nejbližších sousedů , zejména u určitých metrik, jako je vzdálenost velkého kruhu .
Hlavní myšlenkou za datovou strukturou je reprezentovat blízké objekty pomocí jejich ohraničujícího obdélníku na další vyšší úrovni stromu („R“ stromu R je iniciálkou „obdélníku“). Jinými slovy, v daném uzlu stromu jsou uloženy ohraničující obdélníky každého dílčího stromu, jehož je rodičem. Při hledání prostorových informací tedy stačí zkontrolovat pro každou větev, zda hledaná pozice protíná odpovídající obdélník, a ignorovat větve spojené s obdélníkem, pro který neexistuje žádný průnik. Každý list stromu popisuje jeden objekt a každá vyšší úroveň popisuje shromáždění rostoucího počtu objektů.
Stejně jako B-strom , i R-stromy jsou vyvážené výzkumné stromy (všechny listy jsou ve stejné vzdálenosti od kořene), jejichž data jsou organizována do stránek a jsou speciálně označena pro ukládání na disk., Například v případě databáze . Každá stránka má maximální kapacitu, označenou M (stránka má maximálně M záznamů) a strom zaručuje minimální míru naplnění každé stránky (kromě kořenového adresáře). Tato organizace stránky je vhodná pro velký objem dat: každou stránku lze v případě potřeby načíst do paměti, i když byl celý strom příliš velký na to, aby mohl být uložen do paměti.
Většina operací prostorového vyhledávání ( průnik , začlenění , hledání nejbližších sousedů ) je zjednodušena strukturou stromu R: pomocí hraničního obdélníku větve určíme, zda pokračujeme v průzkumu tam, což umožňuje eliminovat irelevantní uzly.
Obtíž při implementaci R-stromů pramení z potřeby udržovat strom vyvážený a přitom se vyhnout tomu, aby ohraničující obdélníky pokrývaly příliš mnoho prázdného prostoru nebo aby několik obdélníků nepokrývalo stejnou oblast. Bez něj by operace vesmírného vyhledávání riskovaly zbytečné prozkoumání příliš mnoha uzlů, což by mělo vliv na výkon. Zpočátku bylo vložení prvků provedeno umístěním prvku do podstromu, jehož ohraničovací rámeček by rostl nejméně přidáním nového prvku k němu. Pokud je stránka plná, rozdělíme její prvky a pokusíme se minimalizovat plochu obdélníků odpovídajících dvěma podmnožinám. Většina výzkumů týkajících se R-stromů usiluje o optimalizaci výkonu stromu vytvořeného z jednoho zdroje dat ( hromadné načítání ) nebo naopak o optimalizaci stromu v případě, že jsou data přidávána postupně.
Ačkoli R-stromy nenabízejí v nejhorším případě dobrý teoretický výkon, jsou v praxi velmi efektivní. Existují varianty, které nabízejí záruky optimality i v nejhorším případě hromadného nakládání , ale složitost jejich implementace omezuje jejich použití v praktických aplikacích.
Schopnost rychle najít objekty ve vzdálenosti r od daného bodu nebo k nejbližším sousedům (ve smyslu jakéhokoli norme- p ) pomocí základu operace prostorového spojení pro mnoho algoritmů, které se spoléhají na efektivní implementaci těchto operací, například pro shlukování nebo detekci anomálií .