K-D-B stablo

U informatici, K-D-B stablo (K - dimenzionalno B - stablo) je struktura podataka za podelu k - dimenzionalnog prostora za pretraživanje. Cilj K-D-B stabla je da se obezbedi efikasna pretraga balansiranog K-D stabla, pružajući blokovski-orijentisano skladištenje B stabla radi optimizacije pristupa spoljnoj memoriji.

Neformalni opis

Slično kao k-d stablo, K-D-B stablo organizuje tačke u k-dimenzionalnom prostoru i koristi se za pretraživanje opsega i multi-dimenzionalne upite nad bazama podataka. K-D-B stablo deli prostor na dva podprostora upoređivanjem elemenata u jednom domenu. Koristeći 2-D-B stablo (2-dimenzionalno K-D-B stablo) kao primer, prostor je podeljen na isti način kao i kod k-d stabla - koristeći tačku u samo jednom od domena, ili osa u ovom slučaju, sve ostale vrednosti su manje ili veće od trenutne vrednosti, i padaju levo i desno od ravni koja deli prostor.

Za razliku od k-d stabla, nije svaka polovina prostora sama sebi čvor. Umesto toga, kao u B-stablu, čvorovi u K-D-B stablu se čuvaju kao stranice, a stablo čuva pokazivač ka stranici u korenu.

Struktura

Osnovna struktura K-D-B stabla.

K-D-B stablo sadrži dve vrste stranica:

• Stranice-regioni: Kolekcija parova (region,dete) koji sadrži opis graničnog regiona, zajedno sa pokazivačem ka stranici-detetu koja odgovara tom regionu.
• Stranice-tačke: Kolekcija parova (tačka, lokacije). U slučaju baze podataka, lokacija može da pokazuje na indeks zapisa u bazi, dok se za tačke u k-dimenzionalnom prostoru može posmatrati kao koordinata tačke u tom prostoru.

Prelivanje stranice se javlja prilikom ubacivanja elemenata u K-D-B stablo, ako čvor pređe svoju optimalnu veličinu. Pošto je svrha K-D-B stabla da optimizuje pristup spoljnoj memoriji, stranica se smatra prelivenom ili prepunjenom kada veličina čvora pređe veličinu stranice spoljne memorije.

Tokom dodavanja/brisanja, K-D-B stablo zadržava određeni skup osobina:

• Graf je višeputno stablo. Stranice-regioni uvek pokazuju na stranicu decu i ne mogu biti prazne. Stranice-tačke su listovi čvorova stabla.
• Kao i B-stablo, dužina putanje do lista stabla je ista za sve upite.
• Regioni koji čine region stranica su razdvojeni.
• Ako je koren region stranica, skup njenih regiona je ceo prostor za pretragu.
• Kada je dete para (region, dete) u region stranici takođe region stranica, unija svih regiona u detetu je region.
• Sa druge strane, u prethodnom slučaju, ako je dete para tačka stranica, sve tačke u detetu moraju biti sadržane u regionu.

Operacije u K-D-B stablu

Upiti

Upiti na K-D-B stablo su pretraga opsega nad intervalima u svim domenima ili osama stabla. Ova kolekcija intervala se zove region upita. U k-prostoru, region upita se može sagledati kao granični volumen oko nekog podprostora u celom k-dimenzionalnom prostoru za pretragu. Upit može da spada u jednu od tri kategorije:

• Raspon nekih intervala je ceo domen ili osa, što upit čini upitom delimičnog opsega.
• Neki intervali su tačke, drugi su puni domeni, pa je upit sa delimičnim poklapanjem.
• Svi intervali su tačke, tako je i granični volumen tačka. To upit čini upitom sa potpunim poklapanjem.

Algoritam

1. Ako je koren stabla NULL, prekinuti, u suprotnom neka strana bude koren.
2. Ako je strana tačka stranica, vrati tačku u (tačka, lokacija) paru koji se nalazi u regionu upita.
3. Inače, strana je region stranica, tako da za sve parove (region, dete) gde se region i region upita seku, postavi stranicu da bude dete i nastavi od koraka 2.

Dodavanje

Zbog toga što dodavanje u K-D-B stablo može zahtevati deljenje stranice u slučaju prelivanja/preplavljenja stranice, moramo prvo definisati operaciju podele.

Algoritam podele

Region stranica je podeljena duž neke ravni, i od nje nastaju dve nove region stranice, leva i desna stranica. Ove stranice su popunjene regionima iz stare stranice, koja se briše. Zatim, za svaki (region, dete) par u originalnoj region strani, dete koje pamtimo je strana i region je granični region:

1. Ako region u potpunosti leži sa leve strane ravni podele, dodati (region, dete) levoj strani.
2. Ako region u potpunosti leži sa desne strane ravni podele, dodati (region, dete) desnoj strani.
3. Inače:
   1. Rekurzivno delimo dete po ravni podele, čime dobijamo novu levu stranicu i novu desnu stranicu.
   2. Deljenjem regiona po ravni podele dobijamo levi region i desni region.
   3. Dodajemo (levi region, novu levu stranu) levoj strani i (desni region, novu desnu stranu) desnoj strani.

Algoritam umetanja

Važnost odabira ispravnog domena podele.

Koristeći algoritam podele, umetanje novog (tačka, lokacija) para se može izvesti na sledeći način:

1. Ako je korena stranica NULL, napravi novu tačka-stranicu koja sadrži (tačku, lokaciju) i postavi korenu stranicu na tu vrednost.
2. U slučaju potpunog poklapanja upita, nađi stranicu u koju treba dodati tačku. Ako tačka već postoji u stranici, završi.
3. Dodaj (tačka, lokacija) u stranicu. Ako je stranica prepunjena, označi stranicu sa stranica.
4. Neka je stara stranica jednaka stranici. Izaberi neki element i domen/osu za definisanje ravni razdvajanja, tako da se stranica razdvoji na 2 stranice od kojih nijedna neće biti prepunjena posle dodavanja nove tačke. Razdvoj stranicu na 2 stranice, novu levu stranicu i novu desnu stranicu, i 2 nova regiona, novi levi region i novi desni region.
5. Ako je stranica bila u korenu, idi na korak 6. U suprotnom, stranica postaje roditelj stranice. Zameni (region, stara stranica) u stranici sa (novi levi region, nova leva stranica) i (novi desni region, nova desna stranica). Ako je stranica prepunjena ponovi korak 4, u suprotnom završi.
6. Neka levi region bude čitav prostor pretraživanja levo od ravni razdvajanja i neka desni region bude prostor pretraživanja desno, kao rezultati koraka 4. Postavi korenu stranicu tako da sadrži levi region i desni region.

Važno je paziti pri biranju domena i elementa po kojima se stranica deli, pošto je cilj da se balansira broj tačaka sa dve strane ravni razdvajanja. U nekim slučajevima, loš izbor domena će rezultirati neželjenim podelama. Takođe je moguće da stranica ne može biti razdvojena po nekom domenu.

Brisanje

Brisanje iz K-D-B stabla je vrlo jednostavno ako nema minimalnih zahteva za korišćenje memorije. Koristimo tačno poklapanje upita da pronađemo (tačku, lokaciju) par i jednostavno uklonimo taj par iz stabla ukoliko on postoji.

Algoritam reorganizacije

Zbog toga što brisanje iz K-D-B stabla može dovesti do toga da stranica ima jako malo podataka, može biti potrebno da se stablo reorganizuje kako bi ispunilo minimalne kriterijume u korišćenju memorije. Algoritam reorganizacije koji se koristi ukoliko stranica ima malo podataka je sledeći:

1. Neka strana bude roditelj od P i sadrži (region, P).
2. Pronađi susedne regione na strani tako da njihova unija predstavlja pravougaoni region. Ovi regioni se smatraju spojivim. Neka R označava skup ovih regiona.
3. Utopi skup R u jednu stranicu S, i ako je S prepuna ponovi sve dok nijedna od dobijenih stranica nije prepuna.
4. Zameni skup regiona R na strani sa stranicama dobijenim deljenjem S.

Radovi slične tematike

Kao i u k-d stablu, izmene u K-D-B stablu mogu dovesti do potrebe rekurzivnog razdvajanja čvorova. Ovo je vrlo neefikasno i može dovesti do neoptimalnog korišćenja memorije jer se stvara mnogo praznih listova. Lomet i Salcberg su predložili strukturu pod nazivom hB stablo kako bi poboljšali perfomanse K-D-B stabla ograničavajući podele koje nastaju nakon umetanja. Ovo je postignuto ne samo čuvanjem regiona kao pravougaonika već kao pravougaonika kojima je uklonjen pravougaonik iz centra.

U skorije vreme, B-K-D stablo je predloženo kao sredstvo da se obezbede brzi upiti i 100% iskorišćenost prostora statičkog K-D-B stabla. Umesto održavanja i rebalansiranja jednog stabla, skup od $\log _{2}(N/M)$ K-D-B stabla se održavaju i ponovo prave u redovnim intervalima. U ovom slučaju, $M$ je veličina međumemorije u broju tačaka.