Bx-strom

V informatice je strom B x  dotaz a aktualizace efektivní indexovací struktury pro přesun objektů na základě B+‍‍-stromů .

Struktura indexu

Základem stromové struktury B x je strom B+‍‍, ve kterém jsou interní uzly považovány za adresáře obsahující ukazatele na pravý sousední uzel (se stejným rodičem). V raných verzích B x -stromu [1] listy obsahovaly polohu indexovaných pohyblivých objektů a odpovídající čas indexování. V optimalizované verzi [2] obsahuje každý list id, rychlost, jednorozměrnou (skalární) hodnotu poziční funkce a čas poslední aktualizace objektu. Rozdíl je zvětšen chybějícím uložením polohy pohybujících se objektů, protože ji lze získat z hodnoty funkce .

Použití B+‍‍-stromů pro přesun objektů

Stejně jako u mnoha jiných indexací pohybujících se objektů je dvourozměrný pohybující se objekt modelován lineární funkcí O = ((x, y), (vx, vy), t), kde (x, y) a (vx, vy ) jsou poloha a rychlost objektu v čase t , tedy v době poslední aktualizace. B+‍‍-tree je struktura pro indexování jednorozměrných dat. Pro přizpůsobení B+‍‍-stromu pro indexování pohybujících se objektů používá Bx -strom techniku ​​linearizace , která pomáhá převést polohu objektu v čase t na jednorozměrnou hodnotu. Zejména objekty jsou nejprve rozděleny podle času aktualizace. Pro objekty v časovém rozdělení si B x -strom pamatuje polohu objektu v daném časovém bodě, získanou lineární interpolací . Tím si strom Bx udržuje konzistentní obraz všech objektů v rámci rozděleného prvku, aniž by se měnil čas aktualizace objektů.

Dále je prostor rozdělen mřížkou a poloha objektů je pro prvek přepážky v čase linearizována podle křivky vyplňující prostor, například Peano křivky nebo Hilbertovy křivky .

Poté, v kombinaci s číslem rozděleného prvku (informace o čase) a lineárním pořadím (informace o poloze), je objekt indexován do stromu B x s jednorozměrnou hodnotou klíče (hodnota B x ):

Zde index-partition je index prvku oddílu určený časem aktualizace a xrep je hodnota pozice objektu na křivce vyplňování prostoru v době indexování, znamená binární hodnotu x, „+“ znamená řetězec zřetězení.

Zadaný objekt O ((7, 2), (-0,1, 0,05), 10), tmu = 120, lze hodnotu B x pro O vypočítat následovně.

  1. O je indexováno v prvku 0 časového rozdělení, jak je popsáno výše. Takže indexpartition = (00) 2 .
  2. Poloha objektu O v době nastavení času pro oddíl 0 je (1,5).
  3. Pomocí Z-křivky řádu 3 je Z-hodnota objektu O, xrep, (010011) 2 .
  4. Spojíme řádky indexpartition a xrep, dostaneme hodnotu B x (00010011) 2 =19.

Vkládání, aktualizace a mazání

Pokud je zadán nový objekt, vypočítá se jeho indexový klíč a objekt se vloží do B x -stromu jako do B+‍‍-stromu. Aktualizace se skládá z odstranění následovaného vložením. Další struktury se používají k uložení posledního klíče každého indexu, takže objekt lze odstranit, když je klíč vyhledán. Indexový klíč se vypočítá před zahrnutím do stromu. Strom B x tedy přímo zdědí dobré vlastnosti stromu B+‍‍ a dosahuje dobrého výkonu aktualizace.

Žádosti

Dotaz podle rozsahu

Dotaz na rozsah načte všechny objekty, jejichž umístění spadá do obdélníkové oblasti , v čase , který není dřívější než aktuální čas.

Strom Bx používá k zodpovězení tohoto dotazu techniku ​​rozšíření okna dotazu. Rozšíření má dva případy – umístění musí být vypočteno v nějakém předchozím časovém okamžiku, nebo v pozdějším časovém okamžiku. Hlavní myšlenkou je rozšířit okno dotazu takovým způsobem, že bude zahrnovat všechny objekty, které nejsou zahrnuty v okně dotazu v době uvedené v klíči objektu, ale spadají do něj v době požadavku.

Po rozbalení se musíte podívat přes části B x -stromu a najít objekty, které spadají do rozbaleného okna. V každé sekci aplikace křivky vyplňování prostoru znamená, že rozsah dotazu v přirozeném 2D prostoru se stává množinou dotazů rozsahu v 1D prostoru [1] .

Aby se předešlo dotazům s příliš velkým rozsahem po rozšíření okna dotazu v asymetrických datech, existuje optimalizační algoritmus [3] , který zlepšuje výkon dotazů odstraněním zbytečných rozšíření.

Dotaz na K nejbližších sousedů

Dotaz na K nejbližších sousedů se provádí opakovaným prováděním dotazů na rozsah s rostoucí oblastí hledání, dokud nezískáme k odpovědí. Další možností je použít podobné nápady spolu s technikou iDistance .

Další požadavky

Algoritmy dotazu na rozsah a K dotazu na nejbližšího souseda lze snadno rozšířit o podporu intervalových dotazů, kontinuálních dotazů atd. [2] .

Přizpůsobení relačních databází tak, aby vyhovovaly pohybujícím se objektům

Protože strom B x je index vytvořený nad stromem B+‍‍, všechny operace ve stromu Bx , včetně vkládání, mazání a vyhledávání, jsou stejné jako ve stromu B+‍‍. Provádění těchto operací není třeba měnit. Jediný rozdíl v implementaci spočívá v implementaci procedury pro získání indexačního klíče jako uložené procedury ve stávající databázi . Bx -strom lze tedy snadno integrovat do existující databáze, aniž by to ovlivnilo jádro .

SpADE [4]  je systém pro správu pohyblivých objektů postavený na populární databázi MySQL , který k indexování objektů používá strom B x . V implementaci jsou data přesouvaných objektů konvertována a uložena přímo v MySQL a dotazy jsou transformovány na standardní SQL dotazy, které jsou efektivně zpracovávány runtimem relační databáze. A co je nejdůležitější, to vše se děje úhledně a nezávisle, aniž by to zasahovalo do jádra MySQL.

Ladění výkonu

Možné problémy se zkreslením dat

Bx - strom používá alokační mřížku prostoru k transformaci dvourozměrné pozice na jednorozměrný klíč. To může vést ke snížení výkonu v dotazech i aktualizacích při práci s asymetrickými daty. Pokud je buňka mřížky velká, obsahuje tato buňka mnoho objektů. Protože objekty v buňce jsou nerozlišitelné podle indexu, dojde k určitému přetečení uzlů v podkladovém B+‍‍-stromu. Existence přetečených stránek nejen ničí rovnováhu stromu, ale také zvyšuje náklady na aktualizaci. Stejně jako u normálních dotazů je i u dotazu na rozsah výsledkem větších buněk více falešných vzorků a prodloužení doby provádění. Na druhou stranu, pokud je prostor rozdělen na menší mřížku, tedy na menší buňky, obsahuje každá buňka méně objektů. Je nepravděpodobné, že by v tomto případě bylo dosaženo přetečení stránky a bude také méně falešných vzorků, ale bude potřeba naskenovat více buněk. Zvýšení počtu buněk, na které je třeba se podívat, také zvyšuje složitost dotazu.

Nastavení indexu

ST 2 B-strom [5] zavádí samoladící schéma pro ladění výkonu B x stromu při práci s nesymetrickými daty v prostoru a čase. Pro práci s asymetrickými daty v prostoru ST 2 rozděluje B-strom celý prostor do oblastí s různou hustotou objektů pomocí sady řídicích bodů. Každá oblast používá samostatnou mřížku, jejíž velikost buněk je určena hustotou objektů v oblasti.

B x -strom má několik oddílů pro různé časové intervaly. ST 2 B-strom používá zvýšení nebo snížení intervalu k úpravě indexování tak, aby vyhovovalo rozdělení prostoru a změnám času. Zejména když se oddíl vyprázdní a začne růst, vybere se nová sada řídicích bodů a pro každý bod se vybere nová mřížka podle poslední hustoty dat. Ladění je založeno na statistikách shromážděných za dané časové období, takže rozdělení prostoru lépe odpovídá nejnovější distribuci dat. V tomto smyslu se očekává , že ST 2 B-strom minimalizuje efekt způsobený zkreslením dat v prostoru a změnami dat v průběhu času.

Viz také

Poznámky

  1. ↑ 1 2 Jensen, Lin, Ooi, 2004 , str. 768-779.
  2. ↑ 12 Dan Lin, 2006 .
  3. ↑ Jensen, Tiesyte, Tradisauskas, 2006 .
  4. ↑ SpADE Archivováno z originálu 2. ledna 2009. : SPatio-temporální autonomní databázový stroj pro lokalizační služby.
  5. ↑ Chen, Ooi, Tan, Nacismento, 2008 , str. 29-42.

Literatura