En trädtopologi är en speciell typ av struktur där många sammanhängande element är arrangerade som grenar av ett träd. Till exempel används trädtopologier ofta för att organisera datorerna i ett företagsnätverk, eller informationen i en databas.

I en trädtopologi kan det bara finnas en anslutning mellan två anslutna noder. Eftersom några två noder bara kan ha en gemensam anslutning, bildar trädtopologier en naturlig förälder och barnhierarki.

I datanätverk är en trädtopologi också känd som en stjärnbustopologi . Den innehåller inslag av både en bustopologi och en stjärntopologi. Nedan är ett exempel på nätverksdiagram över en trädtopologi, där de centrala noderna i tvåstjärniga nätverk är anslutna till varandra.

På bilden ovan, om huvudkabeln eller stammen mellan vart och ett av de två stjärntopologinätmen skulle misslyckas skulle dessa nätverk inte kunna kommunicera med varandra. Datorer på samma stjärntopologi skulle dock fortfarande kunna kommunicera.

Trädtopologi i datorprogrammering

I datorprogrammering kan trädtopologier användas för att strukturera många typer av data, inklusive ett datorprogram i sig.

Till exempel är detta ett enkelt datorprogram skrivet i Lisp:

 (+ 1 2 (om (> p 10) 3 4)) 

Detta program säger "Om p är större än 10, lägg till siffrorna 1, 2 och 3. Annars lägg till siffrorna 1, 2 och 4." Liksom alla Lisp-program har den en inneboende trädtopologi struktur. Om vi ​​ritar det som ett diagram ser det ut som det träd som visas till höger. Att representera ett program på detta sätt kan vara användbart eftersom det tydligt visar hur alla operationer och data är anslutna.

Program i denna typ av struktur har också särskilda användningsområden. Till exempel kan genetiska programmeringstekniker utveckla nya datorprogram genom utbyte av filialer mellan befintliga program som struktureras som träd.

Trädtopologi i binära träd

Ett binärt träd är en trädtopologi där varje nod har högst två barn. Barnnoden är märkt som "vänster barn" eller "rätt barn". Denna typ av datastruktur används ofta för att sortera och söka stora mängder data. I det binära trädet som visas nedan har varje föräldras vänstra barn ett värde mindre än rätt barn.

B-träd

Ett B-träd är en variation av ett binärt träd som uppfanns av Rudolf Bayer och Ed McCreight vid Boeing Labs 1971. Dess noder har barn som faller inom ett fördefinierat minimum och maximalt, vanligtvis mellan 2 och 7. Ett enkelt B-träd grafen kan se ut som bilden nedan.

B-träd är "självbalanserade", vilket innebär att grenarnas höjd hanteras så att de inte blir godtyckligt stora. Varje nod innehåller partitionering "nyckelvärden" som anger barnens värden. Deras design är optimerad för hantering av mycket stora datafiler och för skrivning av data till minne eller disk. De används i stor utsträckning i databasystem som MySQL, PostgreSQL och Redis, och filsystem som NTFS, HFS + och ext4.

Nätverksvillkor, Topologi