Деревоподібна топологія - це особливий тип структури, в якому багато пов'язаних елементів розташовані так, як гілки дерев. Наприклад, деревоподібні топології часто використовуються для організації комп'ютерів у корпоративній мережі або інформації в базі даних.

У деревоподібній топології може бути тільки одне з'єднання між будь-якими двома зв'язаними вузлами. Оскільки будь-які два вузли можуть мати тільки одне взаємне з'єднання, топології дерев утворюють природну батьківську і дитячу ієрархію.

У комп'ютерних мережах топологія дерева також відома як топологія зіркових шин . Вона включає елементи як топології шини, так і топології зірок. Нижче наведено приклад мережевої діаграми топології дерева, в якій центральні вузли двох зіркових мереж з'єднані один з одним.

На малюнку вище, якщо головний кабель або магістраль між кожною з двох топологічних мереж зірок зірвалися, ці мережі не зможуть взаємодіяти один з одним. Однак комп'ютери з однією топологією зірок все одно зможуть спілкуватися.

Дерево топології в комп'ютерному програмуванні

У комп'ютерному програмуванні топології дерев можна використовувати для структурування багатьох видів даних, включаючи саму комп'ютерну програму.

Наприклад, це проста комп'ютерна програма, написана на Lisp:

 (+ 1 2 (якщо (> p 10) 3 4)) 

У цій програмі написано "Якщо p більше 10, додайте цифри 1, 2 і 3. В іншому випадку додайте числа 1, 2 і 4." Як і всі програми Lisp, він має властиву структуру деревної топології. Якщо намалювати його як графік, це виглядає як дерево, показане праворуч. Представлення програми таким чином може бути корисним, оскільки воно чітко показує, як всі операції і дані підключені.

Програми в цій структурі також мають особливе призначення. Наприклад, методики генетичного програмування можуть розвивати нові комп'ютерні програми шляхом обміну гілками між існуючими програмами, структурованими як дерева.

Деревоподібна топологія в бінарних деревах

Двійкове дерево - це топологія дерева, в якій кожен вузол має максимум двох дітей. Дочірні вузли позначені як "ліва дитина" або "права дитина". Цей тип структури даних часто використовується для сортування та пошуку великих обсягів даних. У двійковому дереві, показаному нижче, ліва дитина кожного з батьків має значення, менше, ніж права дитина.

B-дерева

B-дерево - це варіація бінарного дерева, винайденого Рудольфом Байєром і Едом МакКрейт в лабораторіях Boeing в 1971 році. Її вузли мають дітей, які знаходяться в межах заздалегідь визначеного мінімуму і максимуму, як правило, від 2 до 7. Просте дерево B Графік може виглядати як зображення нижче.

B-дерева "самобалансуються", тобто висота гілок управляється так, що вони не отримують довільно великих. Кожен вузол містить розділи "ключові значення", які вказують значення дітей. Їх конструкція оптимізована для обробки дуже великих файлів даних, а також для запису даних в пам'ять або диск. Вони широко використовуються в системах баз даних, таких як MySQL, PostgreSQL і Redis, і файлові системи, такі як NTFS, HFS + і ext4.

Умови мережі, топологія