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.[1]
Č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.
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:
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.
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:
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.
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.
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.
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.[2][3] 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.