- dělí prostor na nějaký podprostor
- dělí prostor na podprostory
- až body jsou rozděleny dostatečně dobře, uloží si rozdělení
- prostor je dělen podle “hyperplanes” (pro 2d je to přímka)
- každý podprostor musí procházet bodem!
- vložení a dotazování není problém
- problém s dělením - vyvážení stromu
- problém když leží všechny body na přímce, poznačíme si speciální případ
- smazání a vyváženost stromu - “homework”
- BSP tree = může mít nakloněné úsečky
- Quad Tree - nedělí 1 úsečkou, ale 2. (4 podprostory) - povoluje prázdné buňky
- LSD strom = co nejvíc vyváženou část, nevyvážené části ukládád na disk (local speed decision)
- KDB tree = přestupoval a samo vyvažoval při vkládání, kombinace kd a b stromu
- hashing
- problémy
- body, co jsem hodně shlukované = prostor je přeplněný - jako u hashování naplnění 1 bucketu
- prostor se rozdělí na mřížku
- každé buňce musím přiřadit datovou jednotku (bucket)
- nemusí být pravidelná délka
- výsledné buňky mají různou velikost - spojíme 2 buňky do 1
- mřížka je na disku
- problém s výkonem při využití místa/zaplnění od 69%
- více populárnější než nested grid file
- 2 grid file s různým rozdělením, 1 je primární
- když chceme ukládát více rozměrné věci
- transformace - 2 bodů ve 2D → udělám bod 4D
- překrývání - R-tree
- jako B strom, ale v listech a uzlech jsou obdélníky
- clipping = zakazuje překrytí křivek
- nějaká část některého algoritmu
- nebo nějaká vlastnost struktury
- případně předalgoritmovské téma