T-stablo

Primjer T-stabla

U računarstvu, T-stabla su vrsta binarnih stabala koji se potrebljavaju u bazama podataka koje upotrebljavaju glavnu memoriju za smještaj podataka.

T-stablo je podatkovna struktura izvedena kao samobalansirajuće indeksno stablo optimizirano za slučajeve gdje su i indeks i sami podatci u potpunosti pohranjeni u primarnoj memoriji računala, kao što je struktura B-stabla indeksna struktura optimizirana za pohranu na sekundarne memorijske uređaje poput tvrdog diska. T-stablima se želi postići brzina AVL stabala bez velikog izdatka prostora za pohranu koji im je svojstven (zbog pohrane samo jednog podatka u svakom čvoru).

T-stabla ne čuvaju kopije indeksiranih polja podataka unutar samog čvora indeksnog stabla. Umjesto toga, iskorištavaju činjenicu da su sami podatci uvijek u glavnoj memoriji kao i indeks, tako da mogu jednostavno sadržavati pokazivače na stvarne podatake.

'T' u T-stablu označava oblik čvora struktura podataka u izvornom radu koji je prvi opisao ovakvu vrstu indeksa.

Ustrojstvo čvorova

Čvor T-stabla

Čvor T-stabla obično se sastoji od pokazivača na roditeljski čvor, lijevi i desni čvor dijete, uređeno (sortirano) podatkovno računarstvo polje, pokazivača (na podatke) i nešto dodatnih, kontrolnih podataka. Dakle sami podatci zapisani su drugdje u memoriji, a T-stablo, odnosno podatkovno polje sadrži samo pokazivače na njih. Postoje tri vrste čvorova: Čvorovi s dva podstabla zovu se unutarnji čvorovi, čvorovi sa samo jednim potstablom zovu se polulistovi, a oni bez podstabala zovu se listovi (engl. leaf node).

Ovisno o vrsti čvora, jedan može sadržavati maksimalno onoliko elemenata koliko ih stane u podatkovno polje. Podatkovno polje je uvijek sortirano od elementa s najmanjom vrijednošću - minimalnog elementa, do elementa s maksimalnom vrijednošću - maksimalnog elementa. Za svaki unutarnji čvor, postoje neka dva pripadajuća čvora lista (ili polulista), od kojih jedan sadržava vrijednost koja prethodi minimalnom elementu, a drugi vrijednost koja slijedi maksimalnom elementu (odnosno, radi se o pokazivačima na vrijednosti/podatke). Vrijednost koja prethodi minimalnoj vrijednosti unutarnjeg čvora naziva se najvećom donjom granicom, a ona koja slijedi maksimalnoj naziva se najmanjom gornjom granicom tog čvora. Ako neka vrijednost upada između te dvije granice, kažemo da ju rečeni čvor omeđuje.

T-stablo ima predefiniran minimalan broj i maksimalan broj elemenata (važno je razlikovati ih od minimalne i maksimalne vrijednosti) koje neki unutarnji čvor može pohraniti. Ta dva broja obično se razlikuju za samo jedan-dva elementa što je dovoljno da se znatno smanji potreba za balansiranjem stabla pomoću rotacije. Uzrok tome je smanjena količina prepisivanja u čvorove listove koja se događa zbog ispunjenja polja podataka zbog umetanja podataka, a i smanjena količina prepisivanja u roditeljske čvorove koja se događa zbog pražnjenja polja podataka zbog brisanja podataka. Čvorovi listovi i polulistovi, pak, mogu sadržavati od 0 do maksimalnog broja elemenata.

Algoritmi

Pretraživanje

Pretraživanje T-stabla obavlja se slično kao i kod B-stabla, osim što nema potrebe uspoređivati svaki podatak u čvoru s traženim, već samo minimalnu i maksimalnu vrijednost čvora. To se čini sve dok se ne dođe do čvora koji omeđuje traženu vrijednost:

• Počni pretragu od korijena
• Ako je tražena vrijednost manja od minimuma trenutnog čvora, nastavi pretragu u lijevom čvoru djetetu. Ako je veća od maksimuma, u desnom.
• U suprotnom, pretraži podatkovno polje trenutnog, omeđujućeg čvora (onog čija je min. vrijednost veća, a max. manja od vrijednosti koja se treba umetnuti).

Pretraga je uspjela ako je vrijednost nađena u omeđujućem čvoru. Ako vrijednost nije nađena u omeđujućem čvoru, ili takav ne postoji(!), pretraga je neuspješna.

Umetanje

Da bi vrijednost mogla biti umetnuta u stablo, potrebno je prvo pronaći omeđujući čvor. Nakon što je u taj čvor vrijednost umetnuta, potrebno je provjeriti balans stabla i ako je on operacijom bio narušen, izbalansirati ga (o balansiranju kasnije u tekstu). Algoritam za umetanje sastoji se od sljedećih koraka:

• Pokušaj naći čvor koji omeđuje vrijednost;
• Ako je takav nađen: Ako ima mjesta za vrijednost, umetni ju i završi. Ako nema mjesta, izuzmi minimum, a umetni novu vrijednost. Potom se pomakni na lijevi čvor dijete. gdje će biti umetanut izuzeti minimum (koji će tako postati listov maksimum).
• Ako omeđujući čvor nije nađen učini sljedeće: Ako u posljednji (polu)list dosegnut pretraživanjem stane vrijednost, umetni ju (tako će postati min. ili max. tog čvora). U suprotnom, stvori novi list koji će onda sadržavati samo umetnutu vrijednost.
• Ako je novi čvor bio dodan, provjeri balans stabla: Kreni od lista prema korijenu; ako se podstablo bilo kojeg od čvorova na tom putu razlikuje za više od jednog nivoa, izbalansiraj stablo i završi.

Razlog izdvajanja i prosljeđivanja listu minimuma umjesto maksimuma, prije nove upisa vrijednosti u čvor koji je pun je izbjegavanje posmicanja polja podataka. Kad bi se prosljeđivao maksimum, bio bi zapisan skroz lijevo u podatkovnom polju (desnog) lista, što bi zahtijevalo posmicanje cijelog polja. Prosljeđivanjem minimuma, naprotiv, vrijednost se dodaje skroz desno u podatkovno polje (lijevog) lista, što ne zahtjeva nikakvo posmicanje.

Brisanje

Slično kao i kod umetanja, potrebno je naći odgovarajući čvor i nakon izvršenja operacije (brisanje iz rečenog čvora) eventualno rebalansirati stablo.

• Nađi čvor koji omeđuje traženu vrijednost (ako ga nema, javi grešku i završi).
• Ako je rečeni čvor unutarnji čvor, a broj elemenata je jednak minimalnom broju obriši vrijednost i zatim premjesti najveću donju granicu (maksimalnu vrijednost iz lijevog polu/lista) u trenutni čvor. U suprotnom (ako broj elemenata u čvoru nije jednak minimalnom broju ili se radi o polu/listu), obriši vrijednost i završi.
• Ako je čvor polulist i može biti spojen s listom, prepiši vrijednosti iz polulista u list i obriši suvišan čvor. U suprotnom, ako čvor nije polulist nego list, onda ako nije prazan stani, a ako jest, obriši ga.
• Provjeri balans stabla: Kreni od lista prema korijenu; ako se podstablo bilo kojeg od čvorova na tom putu razlikuje za više od jednog nivoa, izbalansiraj stablo, ali (za razliku od postupka kod algoritma umetanja), nakon balansiranja, potrebno je provjeriti i prvi roditeljski čvor. Razlog je to što rotacija jednog čvora može iz balansa izbaciti čvor iznad (prethodni, dakle roditeljski), te se balansiranje nastavlja sve dok se ne dođe do čvora koji jest u balansu.

Balansiranje stabla

Balansiranje T-stabla slično je balansiranju AVL stabla. Potrebno je ako se podstabla bilo kojeg čvora razlikuju za više od jedne razine, što se može dogoditi nakon umetanja ili brisanja čvora. Provjerava se put od lista do korijena stabla. Na tom putu mora se provjeriti za svaki čvor njegova podstabla. Ako stablo nije u ravnoteži (jedno podstablo jednog od rečenih čvorova razlikuje se za više od jedne razine od drugog), čini se jedno rotiranje stabla - koja je dovoljno da se stablo vrati u ravnotežu. Ipak, nakon akcije brisanja rotiacija jednog čvora nakon može prouzročiti neravnotežu u čvoru roditelju, potrebno je ponavljati akciju rotacije za sve čvorove iznad onoga koje je prvo rotirano, dokle god se ne dođe do prvog čvora koji jest u ravnoteži.

Efikasnost

Iako se široko primjenjuju za baze podataka koje primarno upotrebljavaju glavnu memoriju za pohranu, novija istraživanja govore da T-stabla zapravo nisu brža od B-stabala na modernom očvrsju. Izgleda da je glavni razlog tome to što je tradicionalna pretpostavka da memorijske reference imaju jedinstvenu veličinu postala netočna zbog velike razlike između brzine pristupa glavnoj i priručnoj memoriji.