R-strom je indexovaná struktura, kterou definoval Guttman v roce 1984. [1] Koncové uzly tohoto mnohacestného stromu obsahují položky ve tvaru: (I, identifikátor objektu), kde identifikátor objektu je ukazatel na datový objekt a I je ohraničující obálka, neboli osově souměrný minimální ohraničující obdélník (minimal bounding rectangle). Pro tento obdélník budeme používat zaběhlou zkratku MBR. Datový objekt může být libovolného typu: bod, polylinie nebo polygon. Vnitřní uzly (internal nodes) obsahují položky ve formě: (I, ukazatel na potomka), kde I je opět MBR toho potomka. Maximální počet položek v každém uzlu se nazývá faktor větvení M (the branching factor) a je vybrán tak, aby vyhověl stránkování a diskovému I/O buffering. Guttmanův algoritmus pro vkládání a mazání zaručuje, že počet položek v každém uzlu zůstane mezi m a M, kde m je minimálním počtem položek na uzel a platí, že m ≤ [M/2]. Výhodou R-stromu je, že jsou uchovány ukazatele k celým objektům (například polygonům). Důsledkem toho nejsou objekty nikdy fragmentované.

Obrázek 1. Geometrická datová struktura R-strom. [1]

Obrázek 1. ukazuje R-strom se dvěma úrovněmi, kde M = 4. Nejnižší úroveň obsahuje 3 koncové uzly (listy) a nejvyšší úroveň obsahuje jeden uzel s ukazateli a MBR obdélníky koncových uzlů. Pokrytí (coverage) je definováno jako celá plocha všech MBR obdélníků koncových uzlů. Překrytí (overlap) je celá plocha obsažená ve dvou nebo více listech MBR. Pokrytí je tedy A∪B∪C a překrytí je A∩B. Je jasné, že efektivní vyhledávání vyžaduje jak nízké pokrytí, tak nízké překrytí  zabalený (packed) R-strom.

Roussopoulos a kolektiv popisují algoritmus „Pack“, jenž vytvoří počáteční R-strom, který je pak více efektivní, než kdyby tento R-strom byl vytvořen pomocí algoritmu vkládání. Algoritmus Pack často používá funkci nejbližší soused (nearest neighbour) v průběhu balení R-stromu. Může být použita funkce „City block distance“, protože je výpočetně levnější a vychází vstříc párům bodů (nebo MBR obdélníkům, které leží podél hlavní osy) místo diagonálním orientací. Výsledkem je vytvoření obdélníků s menším pokrytím.

R⁺-strom je modifikací R stromu, který se vyhýbá překrytí. Daní za to je ale více uzlů a vícenásobných odkazů k některým objektům, viz obrázek 2. Analytické výsledky ukazují, že R⁺-strom dovoluje efektivní vyhledávání v případě velkých objektů. Efektivnost R-stromu a R⁺- stromu byla porovnávána v paměťových datových strukturách. [1]

Obrázek 2. R⁺-strom. [1]

Strip strom byl jednou z prvních datových struktur s úrovněmi detailů. Tento strom vytvořil Ballard v roce 1981. [1] Jedná se o hierarchickou reprezentaci křivek skládajících se z binárního stromu, kde každý uzel obsahuje obdélníkový pás (strip). Ukázka viz obrázek 3.

Obrázek 3. Strip strom. [1]

Arc strom je struktura podobná strip stromu a jedná se rovněž o binární strom, který reprezentuje hierarchicky chovající se křivku se zvýšenou přesností v nižších úrovních stromu. Hlavní odlišností od strip stromu je, že zde nejsou uchovávány žádné explicitní informace týkající se hraničního primitiva (bounding primitive) a způsobu, jakým je vybrán rozdělovací bod na křivce. Viz obrázek 4.

Obrázek 4. Arc-strom se zobrazenými pozicemi elips. [1]

Pozn.: Uchovávány jsou pouze body, nikoliv elipsy. Elipsa E1 v levé části obrázku není zobrazena.

Multi-měřítkový liniový strom je mnohacestný strom vhodný k reprezentaci polylinie pro pevný počet měřítek. Oproti arc stromu a strip stromu má tento strom kořeny více v kartografii než ve výpočetní technice. Je založen na Douglas-Peuckerově generalizačním algoritmu. Ten vybírá stejné body, jako by v požadovaném měřítku vybral strip strom pro polylinie, ale neukládá žádné obdélníkové pásy. Požadovaná měřítka musí být dopředu určena a pro každé měřítko je ve stromu jedna úroveň. Multi-měřítkový liniový strom znázorňuje obrázek 5.

Obrázek 5. Multi-měřítkový liniový strom. [1]

Flintstones tvoří hierarchickou reprezentaci a aproximační schéma pro polygony. Existuje ve 2D i 3D variantě. První (zero-order) aproximací polygonu je minimální kružnice dotýkající se hranic objektu, která se dotýká minimálně dvou bodů originálního polygonu (viz obrázek 6a). Polygon je rozdělen na dvě polylinie, definované dotykovými body. Každá polylinie je uzavřena Flintstonem, což je nejmenší průnik dvou kruhů. Každá polylinie je rozdělena do dvou polylinií bodem, který se dotýká oblouku s největším zakřivením (viz obrázek 6b). Začátek, konec a dotykové body z první aproximace jsou vidět na obrázku 6c. Celý proces uzavírání polylinií Flintstonem se opakuje na další úrovni aproximace a je přirozeně reprezentován binárním stromem (viz obrázek 6d).

Výhodou Flintstones oproti arc stromu je lepší výběr rozdělovacích bodů a levnější sférický test oproti testu s elipsami. Nevýhodou je, že Flintstones nemusí být nutně vyvážený. Kvalitu bodů vybraných flintstonem a bodů vybraných strip stromem je těžké porovnat. [1]

Obrázek 6. Flintstones. [1]