B-stablo: razlika između inačica

Izbrisani sadržaj Dodani sadržaj
Nema sažetka uređivanja
Nema sažetka uređivanja
Redak 1:
[[Slika:B-tree.png|thumb|400px|right|Primjer jednostavnoga b-stabla čije su vrijednosti brojevi]]
 
B-stabla su balansirana [[stablo (podatkovna struktura)|stabla]] pretraživanja dizajnirana za rad na magnetskim diskovima ili drugim sekundarnim uređajima za pohranu podataka kojima je dopušten izravan pristup. B-stabla su slična [[crvencrveno-crno stablo|crveno crnim stablima]], ali su bolji u minimiziranju I/O operacija. Mnogi sustavi baza podataka za pohranu koriste b-stabla ili varijante b-stabala. Razlika između crveno-crnih stabala jest u tome što b-stabla mogu imati mnogo djece zbog ''faktora grananja'' dok im je visina O(lg n), a visina je puno manja nego u crveno-cnih stabala također zbog ''faktora grananja''. Stoga se b-stabla mogu koristiti za skup operacija u vremenu O(lg n).
 
B-stabla su generalizirana [[binarno stablo pretraživanja|binarna stabla pretraživanja]]. Ako unutarnji čvor x sadrži n[x] vrijednosti onda x ima n[x] + 1 djece. Vrijednosti u čvoru x se koriste kao točke grananja odvajajući raspon vrijednosti x-a u n[x] +1 podraspona u kojem svako dijete od x-a radi s jednom vrijednošću. Kada pretražujemo vrijednost u b-stablu radimo {n[x] + 1 ) načina odluke baziranih na usporedbi s n[x] vrijenosti u čvoru . Struktura listovnih čvorova razlikuje se od one unutarnjih čvorova.