B+ stablo

U računarstvu, B+ stablo je tip stabla koji predstavlja uskladištene podatke na način koji omogućava efikasno umetanje, pronalaženje i brisanje elemenata, od kojih svaki ima identifikator, ključ. To je dinamički indeks u više nivoa koji ima ograničen maksimum i minimum ključeva u svakom segmentu indeksa (koji se naziva blokom). Kod B+ stabla, za razliku od B-stabla, svi podaci se skladište u listovima; samo ključevi se skladište u unutrašnjim čvorovima.

Prvenstvena prednost B+ stabala je skladištenje podataka na način koji omogućava efikasno pronalaženje. Podaci se čuvaju u blokovima. Efikasnost B+ stabala prvenstveno potiče iz činjenice da za razliku od binarnog stabla pretrage ono ima vrlo veliku razgranatost (engl. fanout), obično reda 100 ili više, što umanjuje broj ulazno/izlaznih operacija neophodnih da bi se pronašao element u stablu.

Fajlsistemi NTFS, ReiserFS, NSS, XFS, i JFS koriste ovaj tip stabala za indeksiranje metapodataka. Sistemi za upravljanje bazama podataka kao što su PostgreSQL i MySQL takođe često koriste ovaj tip stabla za indekse tabela.

Detalji

Red B+ stabla je mera kapaciteta njegovih čvorova (to jest broja sinova nekog čvora) Definiše se kao broj d takav da $\lceil d/2\rceil \leq m\leq d$ , gde je m broj sinova svakog čvora. Na primer, ako je red B+ stabla 7, svaki unutrašnji čvor može da ima između 4 i 7 sinova. Koren može da ih ima između 2 i 7.

Pretraga

Algoritam koji obavlja pretragu za unosom r preko pokazivača prati putanju do odgovarajućeg lista (u kome bi trebalo da se nalazi traženi podatak). Zatim se taj blok (list) pretražuje dok se podatak ne nađe (ili se ne ispostavi da podatka nema).

 function traži(unos r)
   u := koren
   while (u nije list) do
     izaberi pravi pokazivač u čvoru
     idi u prvi čvor u koji vodi pokazivač
     u := trenutni čvor
   pretraži u za r

Ovaj pseudokod pretpostavlja da ponavljanje nije dozvoljeno.

Umetanje

izvrši pretragu da utvrdiš u koji blok treba da se smesti novi unos
ako odgovarajući blok nije pun, dodaj unos.
u suprotnom, podeli blok.
alociraj novi list i premesti polovinu elemenata iz starog lista u novi.
dodaj ključ i adresu najmanjeg ključa novog bloka u roditeljski čvor.
ako je roditeljski čvor pun, i njega podeli.
premesti srednji ključ u roditeljski čvor.
ponavljaj dok se ne pojavi roditelj koji ne mora da se deli.
ako je potrebno da se koren podeli, napravi novi koren koji ima jedan ključ i dva pokazivača.

Karakteristike

Za B+ stablo reda b sa h nivoa indeksa:

Maksimalan broj unosa koji mogu da se uskladište je $n=b^{h}$
Minimalan broj ključeva je $2(b/2)^{h-1}$
Prostor neophodan za skladištenje stabla je $O(n)$
Umetanje unosa zahteva $O(\log _{b}n)$ operacija u najgorem slučaju.
Pronalaženje unosa zahteva $O(\log _{b}n)$ operacija u najgorem slučaju.
Brisanje (prethodno pronađenog) unosa zahteva $O(\log _{b}n)$ operacija u najgorem slučaju.
Pronalaženje svih unosa koji odgovaraju opsegu sa k elemenata u opsegu zahteva $O(\log _{b}n+k)$ operacija u najgorem slučaju.

Povezano