T-stablo

U računarstvu, T-stabla su vrsta binarnih stabala korišćena u bazama podataka, koje koriste glavnu memoriju za smeštanje podataka.

Primer T-stabla

T-stablo je struktura podataka izvedena kao samobalansirajuće indeksno stablo optimizirano za slučajeve gde su i indeks i sami podaci u potpunosti skladišteni u primarnoj memoriji računara, kao što je struktura B-stabla indeksna struktura optimizirana za skladištenje na sekundarne memorijske uređaje poput hard diska. T-stablima se želi postići brzina AVL stabala bez velikog zauzeća prostora za skladištenje koji im je svojstven (zbog skladištenja samo jednog podatka u svakom čvoru).

T-stabla ne čuvaju kopije indeksiranih polja podataka unutar samog čvora indeksnog stabla. Umesto toga, koriste činjenicu da su sami podaci uvek u glavnoj memoriji kao i indeks, tako da mogu jednostavno sadržati pokazivače na stvarne podatake.

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

Stuktura čvorova

Čvor T-stabla

Čvor T-stabla obično se sastoji od pokazivača na roditeljski čvor, levog i desnog sina (čvor dete), niz uređenih (sortiranih) pokazivača podataka i nešto dodatnih, kontrolnih podataka. Dakle, sami podaci zapisani su na nekom drugom mestu u memoriji, a T-stablo, odnosno polje podataka sadrži samo pokazivače na njih. Postoje tri vrste čvorova: Čvorovi sa dva podstabla zovu se unutrašnji čvorovi, čvorovi sa samo jednim podstablom zovu se polu-listovi, a oni bez podstabala zovu se listovi (engl. leaf node).

Zavisno od vrste čvora, jedan može sadržati najviše onoliko elemenata koliko ih stane u polje podataka. Polje podataka je uvek sortirano od elementa sa najmanjom vrednošću (minimalnog elementa), do elementa sa maksimalnom vrednošću (maksimalnog elementa). Za svaki unutrašnji čvor postoje dva pripadajuća čvora lista (ili polu-lista), od kojih jedan sadrži vrednost koja prethodi minimalnom elementu, a drugi vrednost koja sledi maksimalnom elementu (odnosno, radi se o pokazivačima na vrednosti/podatke). Vrednost koja prethodi minimalnoj vrednosti unutrašnjeg čvora naziva se najvećom donjom granicom, a ona koja sledi maksimalnoj naziva se najmanjom gornjom granicom tog čvora. Ako neka vrednost upada između te dve granice, kažemo da je navedeni čvor ograničava.

T-stablo ima predefinisan minimalan broj i maksimalan broj elemenata (važno je razlikovati ih od minimalne i maksimalne vrednosti) koje neki unutrašnji čvor može sadržati. Ta dva broja se obično razlikuju po jednom ili 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 ispunjenih polja podataka usled umetanja podataka, a i smanjena količina prepisivanja u roditeljske čvorove koja se događa zbog pražnjenja polja podataka usled brisanja podataka. Čvorovi listovi i polu-listovi, ipak mogu sadržati od nijednog do maksimalnog broja elemenata.

Algoritmi

Pretraživanje

Pretraživanje T-stabla obavlja se slično kao i kod B-stabla, osim što nema potrebe upoređivati svaki podatak u čvoru sa traženom vrednošću, već samo minimalnu i maksimalnu vrednost čvora. To se čini sve dok se ne dođe do čvora koji ograničava traženu vrednost:

• Početi pretragu od korena
• Ukoliko je tražena vrednost manja od minimuma trenutnog čvora, nastaviti pretragu u levom sinu. Ukoliko je veća od maksimuma, u desnom sinu.
• U suprotnom, pretražiti polje podataka trenutnog, ograničavajućeg čvora (onog čija je minimalna vrednost veća, a maksimalna manja od vrednosti koja se treba umetnuti).

Pretraga je uspela ako i samo ako je vrednost nađena u ograničavajućem čvoru. Ako vrednost nije nađena u ograničavajućem čvoru, ili takav ne postoji, onda je pretraga neuspešna.

Umetanje

Da bi vrednost mogla biti umetnuta u stablo, potrebno je prvo pronaći ograničavajući čvor. Nakon što je u taj čvor vrednost umetnuta, potrebno je proveriti balans stabla i ukoliko je on operacijom bio narušen, izbalansirati ga (o balansiranju kasnije u tekstu). Algoritam za umetanje sastoji se od sledećih koraka:

• Pokušaj pronaći čvor koji ograničava vrednost.
• Ukoliko je pronađen: Ako ima mesta za vrednost, umetnuti je i završiti. Ako nema mesta, izvaditi minimum i umetnuti novu vrednost. Potom se pomeriti na levog sina gde će biti umetnut izvađeni minimum (koji će tako postati maksimum lista).
• Ukoliko ograničavajući čvor nije nađen, učiniti sledeće: Ako smo u poslednjem (polu)listu dosegnutom pretraživanjem stare vrednosti, umetnuti vrednost(koja će tako postati minimum ili maksimum tog čvora). U suprotnom, stvoriti novi list koji će onda sadržati samo umetnutu vrednost.
• Ukoliko je novi čvor bio dodat, proveriti samo balans stabla: Kreni od lista prema korenu, a ukoliko se podstablo bilo kog od čvorova na tom putu razlikuje za više od jednog nivoa, izbalansirati stablo i završiti.

Razlog zašto izdvajamo i prosleđujemo minimum umesto maksimuma listu pre nego što upišemo novu vrednost u čvoru (koji je pun) je to što izbegavamo pomeranje polja podataka. Kada bi se prosleđivao maksimum, bio bi zapisan skroz levo u polju podataka (desnog) lista, što bi zahtevalo pomicanje celog polja. Dok se prosleđivanjem minimalne vrednosti dodaje skroz desno u polje podataka (levog) lista, što ne zahteva nikakvo pomeranje.

Brisanje

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

• Naći čvor koji ograničava traženu vrednost (ako ga nema, javiti grešku i završiti).
• Ako je navedeni čvor unutrašnji čvor, a broj elemenata jednak minimalnom broju, obrisati vrednost i zatim premestiti najveću donju granicu (maksimalnu vrednost iz levog polu/lista) u trenutni čvor. U suprotnom (ukoliko broj elemenata u čvoru nije jednak minimalnom broju ili se radi o polu/listu), obrisati vrednost i završiti.
• Ukoliko je čvor polu-list i može biti spojen sa listom, prepisati vrednosti iz polu-lista u list i obrisati suvišan čvor. A ukoliko je čvor list, treba stati ako nije prazan, a ako jeste obrisati ga.
• Proveriti balans stabla: Krenuti od lista prema korenu. Ukoliko se podstablo bilo kog od čvorova na tom putu razlikuje za više od jednog nivoa, izbalansirati stablo. Za razliku od postupka kod algoritma umetanja, nakon balansiranja je potrebno proveriti i prvi roditeljski čvor. Razlog je to što rotacija jednog čvora može iz balansa izbaciti čvor iznad njega (roditeljski čvor), te se balansiranje nastavlja sve dok se ne dođe do čvora koji jeste u balansu.

Balansiranje stabla

Balansiranje T-stabla slično je balansiranju AVL stabla. Potrebno je stablo balansirati kada se podstabla bilo kog čvora razlikuju za više od jednog nivoa, što se može dogoditi nakon umetanja ili brisanja čvora. Proverava se put od lista do korena stabla. Na tom putu se moraju proveriti podstabla za svaki čvor. Ukoliko stablo nije u ravnoteži (tj. jedno podstablo jednog od navedenih čvorova se razlikuje za više od jednog nivoa od drugog) onda se treba izvšiti jedno rotiranje stabla koje je dovoljno da se stablo vrati u ravnotežu. Pošto akcija brisanja može prouzrokovati neravnotežu u čvoru roditelja, potrebno je ponavljati akciju rotacije za sve čvorove iznad onoga koje je prvo rotirano, sve dok se ne dođe do prvog čvora koji je u ravnoteži.

Efikasnost

Iako su T-stabla dosta korišćena za bazu podataka koje primarno koriste glavnu memoriju za skladištenje, novija istraživanja govore da T-stabla zapravo nisu brža od B-stabala na modernom hardveru. Izgleda da je glavni razlog tome što je tradicionalna pretpostavka da memorijske reference imaju jedinstvenu veličinu postala netačna zbog velike razlike između brzine pristupa glavnoj i keš memoriji.