B-stablo

B-stabla su strukture podataka u informatici. Karakteristike su mu potpuna balansiranost, sortiranje podataka po vrijednosti ključa i čuvanje određenog broja elemenata u jednom čvoru stabla. Operacije nad podacima stabla se obavljaju u amortizirano logaritamskom vremenu. B-stablo nalazi primjenu u magnetskim diskovima ili drugim sekundarnim uređajima za pohranu podataka kojima je dopušten izravan pristup.

B-stabla su slična 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 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.

B-stablo s korijenom Z (korijen je korijen Z) ima sljedeća svojstva:

• Svaki čvor x ima sljedeća polja:
  • n[x], broj vrijednosti trenutno spremljenih u čvoru x
  • n[x] su spremljene u nepadajućemo redoslijedu tako da su vrijednost $k_{1}\left[x\right]$ ≤ $k_{2}\left[x\right]$ ≤ ··· ≤ Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle k_{n}\left[x\right]}
  • listovni čvor [x], boolean vrijednosti koja je TRUE ako je x listovni čvor i FALSE ako je x unutarnji čvor.

• Svaki unutarnji čvor x također sadrži n[x[+1 pokazivača $c_{1}\left[x\right]$, Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{2}\left[ x \right]} , ..., Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{n\left[ x \right]+1}\left[ x \right]} . Listovni čvorovi nemaju djece te su stoga njihova polja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c_{i}\left[ x \right]} nedefinirana.

• Vrijednosti Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle vrijednost_{i}\left[ x \right]} odvajaju raspon vrijednosti spremljene u jednome podstablu: ako je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{i}} spremljena u prvome stablu s korijenom $c_{i}\left[x\right]$ onda Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v_{1}\le vrijednost_{1}\left[ x \right]\le v_{2}\le vrijednost_{2}\left[ x \right]\le ...\le vrijednost_{n\left[ x \right]}\left[ x \right]\le v_{n\left[ x \right]+1}}

• Svi listovi imaju jednaku dubinu što na kraju daje visinu stabla (h).

• Postoje gornje i donje granice broja vrijednosti koje čvor može sadržavati. Ove granice mogu biti izražene u terminima fiksiranih cjelobornih tipova t ≥ 2 i zove se minimalni stupanj B-stabla:
  • Svaki čvor koji nije korijen mora imat najamanje t-1 vrijednosti. Svaki unutarnji čvor koji nije korijen ima stoga najmanje t djece. Ako stablo nije prazno korijen mora imati najmanje jednu vrijednost.
  • Svaki čvor može imati najviše 2t-1 vrijednosti. Stoga unutarnji čvor može imati najviše 2t djece. Kažemo da je čvor pun ako sadrži točno 2t-1 vrijednosti.

Najjednostavnije b-stablo se pojavljuje kada je t = 2. Svaki unutarnji čvor ima 2,3 ili 4 djeteta i imamo 2-3-4 stablo. U praksi se obično koriste mnogo veće vrijednosti.

Osobine

Za B-stablo visine h, sa konstantom k i brojem čvorova n važi sljedeće:

Visina stabla	$h\leq \log _{k}\left({n+1 \over 2}\right)$
Minimalan broj čvorova (h > 0)	Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 1 + 2\sum_{i=0}^{h-1}{(k+1)^i}}
Minimalan broj elemenata (h > 0)	Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = 1 + 2k\sum_{i=0}^{h-1}{(k+1)^i}}
Maksimalan broj čvorova	Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n = \sum_{i=0}^{h}{(2k+1)^i}}
Maksimalan broj elemenata	Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle n=2k\sum _{i=0}^{h}{(2k+1)^{i}}}