En tretopologi er en spesiell type struktur der mange sammenhengende elementer er arrangert som grener av et tre. For eksempel brukes tree topologies ofte til å organisere datamaskinene i et bedriftsnettverk, eller informasjonen i en database.

I en tretopologi kan det bare være en forbindelse mellom to forbundne noder. Fordi noen to noder kun kan ha en gjensidig tilkobling, utgjør tree topologier et naturlig foreldre- og barnhierarki.

I datanettverk er en tretopologi også kjent som en stjernebusstopologi . Den inneholder elementer av både en busstopologi og en stjernetopologi. Nedenfor er et eksempel nettverk diagram av en tre topologi, der de sentrale noder av to-stjerners nettverk er koblet til hverandre.

I bildet ovenfor, hvis hovedkabelen eller bagasjerommet mellom hvert av de to stjernen topologi nettverk skulle svikte, ville disse nettverkene ikke kunne kommunisere med hverandre. Imidlertid vil datamaskiner på samme stjernetopologi fortsatt kunne kommunisere.

Tree topologi i dataprogrammering

I dataprogrammering kan tree topologies brukes til å strukturere mange typer data, inkludert et dataprogram selv.

For eksempel er dette et enkelt dataprogram skrevet i Lisp:

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

Dette programmet sier "Hvis p er større enn 10, legg til tallene 1, 2 og 3. Ellers legger du til tallene 1, 2 og 4." Som alle Lisp-programmer har den en innebygd tretopologi struktur. Hvis vi tegner det som en graf, ser det ut som treet vist til høyre. Å representere et program på denne måten kan være nyttig fordi det tydelig viser hvordan alle operasjoner og data er koblet sammen.

Programmer i denne typen struktur har også spesielle bruksområder. For eksempel kan genetiske programmeringsteknikker utvikle nye dataprogrammer ved å bytte grener mellom eksisterende programmer strukturert som trær.

Tree topologi i binære trær

Et binært tre er en tretopologi hvor hver knute har maksimalt to barn. Barnnodeene er merket som "venstre barn" eller "rett barn". Denne typen datastruktur brukes ofte til sortering og søking av store mengder data. I det binære treet som er vist nedenfor, har hver foreldres venstre barn en verdi mindre enn det riktige barnet.

B-trær

Et B-tre er en variasjon av et binært tre som ble oppfunnet av Rudolf Bayer og Ed McCreight ved Boeing Labs i 1971. Nodene har barn som ligger innenfor et forhåndsdefinert minimum og maksimum, vanligvis mellom 2 og 7. Et enkelt B-tre grafen kan se ut som bildet nedenfor.

B-trær er "selvbalanserende", noe som betyr at høyden på grenene styres slik at de ikke blir vilkårlige store. Hver node inneholder partisjonering "nøkkelverdier" som angir barns verdier. Deres design er optimalisert for å håndtere svært store datafiler, og for å skrive data til minne eller disk. De brukes mye i databasesystemer som MySQL, PostgreSQL og Redis, og filsystemer som NTFS, HFS + og ext4.

Nettverk, Topologi