B-stablo
<s>B-stablo je struktura podataka u informatici.</s><s>Karakteristike su mu potpuna balansiranost, sortiranje podataka po vrednosti ključa i čuvanje određenog broja elemenata u jednom čvoru stabla.</s><s>Operacije nad podacima stabla se obavljaju u amortizovano logaritamskom vremenu.</s><s>B-stablo nalazi primenu u bazama podataka i sistemima fajlova i direktorijuma na tvrdim diskovima.</s>

<s>Definicija 
Svako b-stablo je određeno jednim parametrom k, koji može uzimati vrednosti prirodnih brojeva.</s><s>Uslovi koje svako b-stablo treba da ispunjava su sledeći:</s>

<s>Svi listovi drveta se nalaze na istoj visini u odnosu na koren stabla.</s><s>Koren stabla može sadržati 1 do 2k elemenata.</s><s>Svaki drugi čvor stabla sadrži od k do 2k elemenata.</s><s>Svi elementi u jednom čvoru su sortirani po vrednosti ključa
 Čvor koji nije list i sadrži k elemenata pokazuje na k'+1 dece.</s><s>Pokazivači ka deci su tako raspoređeni da pokazuju na čvorove sa vrednostima ključeva između vrednosti ključeva svaka dva susedna elementa čvora, kao i na čvorove sa vrednostima ključevima manjim i većim od vrednosti svakog njegovog ključa.</s>

<s>Osobine 
Za b-stablo visine h, sa konstantom k i brojem čvorova n važe sledeći iskazi:</s>

<s>Operacije  
Struktura b-stabla za isti skup podataka u principu nije jednoznačna.</s><s>Na primer za k=1 i vrednosti ključeva 21,22,23,24 je za koren stabla moguće uzeti ključ 22 odnosno 23, pri čemu bi u prvom slučaju levi čvor preuzeo ključ 21 a desni 23 i 24.</s><s>U drugom slučaju bi levi čvor preuzeo ključeve 21 i 22, a desni 24.</s><s>Sa porastom konstante k i broja elemenata raste i broj mogućnosti njihovog raspoređivanja.</s>

<s>Pretraživanje stabla 
Pretraživanje, kao i kod drugih vrsta stabala, počinje od korena stabla i nastavlja se tako što se pri svakom koraku pretrage ustanovljava da li tražena vrednost ključa postoji u trenutno pretraživanom čvoru, u nekom od njegove dece ili ne postoji u stablu.</s>

<s>Dodavanje novog elementa</s>

<s>Novi element se uvek dodaje na dno stabla, kao novi elemenat u nekom od listova.</s><s>Ukoliko u nekom trenutku broj elemenata u nekom od čvorova pređe dozvoljenu vrednost od 2k, elemenat najbliži sredini niza elemenata biva izdvojen iz niza i dodat u roditelja čvora kome je pripadao, istovremeno postajući roditelj svih elemenata sa njegove leve odnosno desne strane.</s>

<s>Na datom primeru (slika desno) je broj k=1. Pri drugom koraku u postojeće stablo je dodat element sa ključem 80.</s><s>Kako je time prekoračen broj (2k=2) dozvoljenih elemenata po čvoru, izabran je središlji elemenat problematičnog čvora sa ključem 50 i dodat u svoj roditeljski čvor koji u tom trenutku sadrži samo vrednost 42.</s><s>Svi elementi sa njegove leve odnosno desne strane se dele u dva nova čvora čiji će roditelj on postati.</s>

<s>Da je prethodno opisanim operacijama dozvoljeni broj elemenata u roditeljskom čvoru bio narušen, proces bi bio ponovljen i za njega.</s><s>Ukoliko do ovakve situacije dođe u korenu stabla, neminovno je povećanje visine stabla za jedan.</s>

<s>Brisanje elementa iz stabla 
Operacija Brisanja''' elementa može rezultovati gubljenjem osobina b-stabla.</s><s>Pritom se isključivo radi o povredi pravila o minimalnom broju elemenata po čvoru.</s><s>Pristup problemu se sastoji u tome da se u čvor koji nakon brisanja poseduje k-1 elemenata ubaci element iz roditeljskog čvora.</s><s>Ovaj proces se može ponavljati rekurzivno, od dna stabla prema vrhu.</s>

<s>Pritom se izdvaja slučaj kada stablo iz koga se briše jedan element ima minimalan broj elemenata u svakom čvoru.</s><s>Ovo znači da će na kraju procesa koren stabla koga čini samo jedan element biti utopljen u jedno od svoje dece a pritom će svako od njih imati tačno po k elemenata.</s><s>U ovom slučaju završni korak je stapanje to dvoje dece u novi čvor koji će postati koren stabla.</s><s>Jedna od posledica brisanja u ovom slučaju je smanjenje visine stabla h za jedan.</s>

<s>Izvori 
 Skripta za predmet „Informatika 2“ sa Univerziteta Karlsrue, Nemačka.''</s>

<s>Vidi još 
 Crveno-crno stablo
 AVL-stablo
 B+ stablo</s>

<s>Spoljašnje veze</s>

<s>Java-aplet koji simulira unos podataka b-stabla</s>

<s>Stabla (strukture podataka)</s>

