B+ stablo
<s>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č.</s><s>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).</s><s>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.</s>

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

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

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

<s>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).</s><s>Zatim se taj blok (list) pretražuje dok se podatak ne nađe (ili se ne ispostavi da podatka nema).</s>

<s>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</s>

<s>Ovaj pseudokod pretpostavlja da ponavljanje nije dozvoljeno.</s>

<s>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.</s>

<s>Karakteristike 
Za B+ stablo reda b sa h nivoa indeksa:
 Maksimalan broj unosa koji mogu da se uskladište je 
 Minimalan broj ključeva je 
 Prostor neophodan za skladištenje stabla je 
 Umetanje unosa zahteva  operacija u najgorem slučaju.</s><s>Pronalaženje unosa zahteva  operacija u najgorem slučaju.</s><s>Brisanje (prethodno pronađenog) unosa zahteva  operacija u najgorem slučaju.</s><s>Pronalaženje svih unosa koji odgovaraju opsegu sa k elemenata u opsegu zahteva  operacija u najgorem slučaju.</s>

<s>Vidi još 
Binarno stablo pretrage
B# stablo
B-stablo
Strategija podeli pa vladaj</s>

<s>Strukture podataka</s>

