T-träd

För T-förgrening, se H-träd och Itererat funktionssystem .
Ett exempel T-träd

Inom datavetenskap är ett T-träd en typ av binär träddatastruktur som används av huvudminnesdatabaser , såsom Datablitz , eXtremeDB , MySQL Cluster , Oracle TimesTen och MobileLite.

Ett T-träd är en balanserad indexträdsdatastruktur som är optimerad för fall där både index och faktiska data hålls helt i minnet, precis som ett B-träd är en indexstruktur optimerad för lagring på blockorienterade sekundära lagringsenheter som hårddiskar . T-träd försöker få prestandafördelarna med trädstrukturer i minnet som AVL-träd samtidigt som de undviker det stora lagringsutrymmet som är gemensamt för dem.

T-träd behåller inte kopior av de indexerade datafälten inom själva indexträdnoderna. Istället utnyttjar de det faktum att den faktiska datan alltid finns i huvudminnet tillsammans med indexet så att de bara innehåller pekare till de faktiska datafälten.

'T' i T-trädet hänvisar till formen på noddatastrukturerna i originalpapperet som först beskrev denna typ av index.

Nodstrukturer

En T-trädnod består vanligtvis av pekare till föräldernoden, vänster och höger undernod, en ordnad uppsättning datapekare och lite extra kontrolldata. Noder med två underträd kallas interna noder , noder utan underträd kallas lövnoder och noder med endast ett underträd kallas halvbladsnoder . En nod kallas begränsningsnoden för ett värde om värdet ligger mellan nodens nuvarande minimi- och maxvärde, inklusive.

Bundna värden

För varje intern nod finns det löv- eller halvlövsnoder som innehåller föregångaren till dess minsta datavärde (kallad den största nedre gränsen ) och en som innehåller efterföljaren till dess största datavärde (kallad den minsta övre gränsen ). Löv- och halvbladsnoder kan innehålla valfritt antal dataelement från en till maximal storlek på datamatrisen. Interna noder håller sin beläggning mellan fördefinierade minsta och maximala antal element

Algoritmer

Sök

  • Sökningen börjar vid rotnoden
  • Om den aktuella noden är den avgränsande noden för sökvärdet, sök sedan dess datamatris. Sökningen misslyckas om värdet inte hittas i datamatrisen.
  • Om sökvärdet är mindre än minimivärdet för den aktuella noden, fortsätt sökningen i dess vänstra underträd. Sökningen misslyckas om det inte finns något vänster underträd.
  • Om sökvärdet är större än maxvärdet för den aktuella noden, fortsätt sökningen i dess högra underträd. Sökningen misslyckas om det inte finns något rätt underträd.

Införande

  • Sök efter en begränsningsnod för det nya värdet. Om en sådan nod finns:
    • kontrollera om det fortfarande finns utrymme i dess dataarray, infoga i så fall det nya värdet och avsluta
    • om inget utrymme är tillgängligt, ta bort minimivärdet från nodens datamatris och infoga det nya värdet. Fortsätt nu till den nod som har den största nedre gränsen för den nod som det nya värdet infogades till. Om det borttagna minimivärdet fortfarande passar in där, lägg till det som det nya maxvärdet för noden, annars skapa en ny höger subnod för denna nod.
  • Om ingen avgränsande nod hittades, infoga värdet i den senast sökta noden om den fortfarande passar in i den. I det här fallet blir det nya värdet antingen det nya minimi- eller maximivärdet. Om värdet inte passar längre, skapa ett nytt vänster eller höger underträd.

Om en ny nod lades till kan trädet behöva balanseras om, enligt beskrivningen nedan.

Radering

  • Sök efter begränsningsnod för värdet som ska raderas. Om ingen gränsnod hittas, avsluta.
  • Om den gränsande noden inte innehåller värdet, avsluta.
  • ta bort värdet från nodens datamatris

Nu måste vi skilja efter nodtyp:

  • Intern nod:

Om nodens datamatris nu har mindre än det minsta antalet element, flytta det största nedre gränsvärdet för denna nod till dess datavärde. Fortsätt med ett av följande två steg för halvbladet eller lövnoden som värdet togs bort från.

  • Bladnod:

Om detta var det enda elementet i datamatrisen, ta bort noden. Balansera om trädet om det behövs.

  • Halvbladsnod:

Om nodens dataarray kan slås samman med dess leafs dataarray utan översvämning gör du det och tar bort leafnoden. Balansera om trädet om det behövs.

Rotation och balansering

Ett T-träd implementeras ovanpå ett underliggande självbalanserande binärt sökträd . Specifikt beskriver Lehman och Careys artikel ett T-träd balanserat som ett AVL-träd : det blir ur balans när en nods barnträd skiljer sig i höjd med minst två nivåer. Detta kan hända efter en infogning eller borttagning av en nod. Efter en insättning eller radering skannas trädet från bladet till roten. Om en obalans upptäcks utförs en trädrotation eller ett par rotationer, vilket garanterat balanserar hela trädet.

När rotationen resulterar i att en intern nod har färre än det minsta antalet objekt, flyttas objekt från nodens nya barn till den interna noden.

Prestanda och lagring

Även om T-träd en gång i tiden användes i stor utsträckning för databaser med huvudminne på grund av prestandafördelar, lägger de senaste trenderna för mycket stora databaser med huvudminne mer tonvikt på provisioneringskostnaderna. Med moderna NOSQL-databassystem som ofta lagrar biljoner poster kan minneskostnaden för att lagra ens ett enda index som innehåller faktiska värden överstiga tiotals eller till och med hundratals terabyte.

Se även

Andra träd

  1. ^   Lehman, Tobin J.; Carey, Michael J. (25–28 augusti 1986). En studie av indexstrukturer för huvudminnesdatabashanteringssystem . Tolfte internationella konferensen om mycket stora databaser (VLDB 1986). Kyoto. ISBN 0-934613-18-4 .

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=T-tree&oldid=1080671828 "