Вступ

Ієрархічні дані можна знайти всюди у розробці програмного забезпечення: у всіх списках, діаграмах організації, файлових системах, категоріях продуктів і форумах. Вічні питання щодо того, як зберегти дерево у реляційній базі даних? " є розробники- привиди з ранніх днів SQL, і, чесно кажучи, немає єдиної відповіді, яка б зробила всіх щасливими. у 2004 році., і основні виклики сьогодні залишаються такими самими.

Чому у SQL є дуже важкою ієрархією

Ось основна проблема: реляційні бази даних думають у наборах, а не в деревахДжо Целько розповідає у своїй чудовій книжці Думки на ділі, SQL працює з цілими таблицями, а не окремими рядками.

Коли ви пишете запит SQL, рушій бази даних працює на набори рядківЦе блискуче у операціях на зразок "відшукати всі замовлення на понад 100" або "під'єднати клієнтів до своїх закупівель" - ці операції визначаються природно згідно до того, як працюють таблиці. Результатом завжди є плоский набір рядків.

Але ієрархія властива рекурсивно. Щоб знайти всіх нащадків вузла, вам слід:

1. Знайдіть найближчих дітей
2. Знайти для кожної дитини їх children
3. Повторюйте, поки не пройдете весь піддерево

Цей рекурсивний хід не відповідає за встановлення дій. Ви не можете виразити " надати мені всі нащадки з будь- якої глибини " за одним простим твердженням SQL без будь- яких:

• Рекурсивні CTES (додано SQL: 1999, але обчислювальна вартість)
• Декілька раундів до бази даних
• Умная денормация, которая предотвращает отношения.

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

Приклад: коментарі з гілками

Щоб зробити порівняння конкретним, ми скористаємося коментарями у гілці, які використовуються у нашому прикладі, - чимось, що використовується у цьому блозі. Нитка коментарів може виглядати так:

flowchart TD
    subgraph Post["Post: How to Deploy Docker Containers"]
        C1["Comment 1: Great article!<br/>depth 0"]
        C2["Comment 2: Thanks!<br/>depth 1"]
        C3["Comment 3: Very helpful indeed<br/>depth 1"]
        C4["Comment 4: Agreed!<br/>depth 2"]
        C5["Comment 5: What about Kubernetes?<br/>depth 0"]
        C6["Comment 6: That's covered in part 2<br/>depth 1"]
    end

    C1 --> C2
    C1 --> C3
    C3 --> C4
    C5 --> C6

    style Post stroke:#10b981,stroke-width:2px
    style C1 stroke:#6366f1,stroke-width:2px
    style C2 stroke:#8b5cf6,stroke-width:2px
    style C3 stroke:#8b5cf6,stroke-width:2px
    style C4 stroke:#a855f7,stroke-width:2px
    style C5 stroke:#6366f1,stroke-width:2px
    style C6 stroke:#8b5cf6,stroke-width:2px

Нам потрібно підтримувати ці операції:

• Отримати всі коментарі для допису (з збереженою структурою розгалуження)
• Отримати всі предки коментар (швидкісна стежка)
• Отримати всі нащадки коментар (додаток піддерева)
• Додати новий коментар (як відповідь на існуючий коментар)
• Вилучити піддерево (Вилучає коментар і всі відповіді)
• Пересунути піддерево (побачити коментар - рідкісніший, але іноді потрібно)

П'ять приближається

Кожен підхід докладно описано у власній статті. Ось короткий огляд, який допоможе вам обрати:

---

Список можливостей (Паративний посилання)

Прочитайте всю статтю

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

Як це працює: Кожен коментар може бути недійсним ParentCommentId стовпчик. Корінні коментарі мають NULL, відповіді вказують на їх батьківський елемент.

Найкраще для: Невеликі ієрархії (менш ніж 5- 6 рівнів), часті ходи піддерева, якщо ви бажаєте, щоб властивості навігації EF Core працювали природним чином.

Торгівля: Для отримання предків або нащадків потрібні рекурсивні CTTS або декілька запитів. Просто писати, можливо, повільно для читання глибоких дерев.

---

Таблиця для клонування 2.

Прочитайте всю статтю

Замість того, щоб визначати відносини під час опитування, ми зберігаємо їх прямо з їх глибиною.

Як це працює: Розлука CommentClosure магазини таблиць (sancestor_ id, потомок_ id, глибина) для кожної пари. Коментар 4 за допомогою Коментара 1 буде містити записи: (1, 4, 2), (3, 4, 1), (4, 4, 0).

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

Торгівля: Складніші вставки (мусить додати закриті записи), зберігання зростає з глибиною, пересування піддерева вимагає відновлення закриття.

---

Матеріальний шлях

Прочитайте всю статтю

Зберігає повний родовід як обмежений рядок. Вважайте його зберіганням повної поштової адреси, а не лише назви вулиці.

Як це працює: Кожен коментар має Path column на зразок " 1/ 3/ 7 " означає " root 1, батьківський елемент - 3, - це 7 ." Передня частина може бути розшифрована з рядка; нащадки можна знайти за допомогою запитів, подібних до подібних.

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

Торгівля: ЯК БУТИ запитами повільно без належного індексу, шляхи мають обмеження на довжину, так і пересування піддерева вимагає оновлення всіх сходів нащадків.

---

4. Вкладені набори

Прочитайте всю статтю

Призначає значення для кожного вузла ліворуч і праворуч від меж з початковою глибиною. Всі нащадки мають значення між межі батьків.

Як це працює: Кожен коментар має Left і Right Значення. Вузол з L=4, R=7 містить всі вузли, де 4 < ліва і права < 7. Отримані з простими запитами у діапазоні.

Найкраще для: Втома для читання, сценарії запису, зокрема дерева категорій. Чудова можливість для " створити ціле піддерево у порядку показу ."

Торгівля: Для вставки потрібно оновити багато рядків (змістити всі значення на місце), пересування піддерева є складним. Не підходить для частих записів.

---

5. ltree PostgreSQL

Прочитайте всю статтю

Природний додаток PostgreSQL для ієрархічних даних. Такі як фіктивні шляхи, але з оптимізацією рівня бази даних і потужним збігом з шаблонами.

Як це працює: Використовує ltree тип даних з шляхами на зразок " 1. 3. 7 ." Індекси GiST уможливлюють ефективний предок/descendant запити з використанням таких операторів, як @> і <@.

Найкраще для: Лише PostgreSQL призначено для виконання завдань, які стосуються швидкодії, якщо вам потрібні запити, що збігаються з шаблонами, якщо ви бажаєте мати найкращі з матеріальних тек.

Торгівля: Лише PostgreSQL, додає залежність від розширення бази даних. Зауваження: The Провайдер Npgsql підтримує переклади LINQ для ltree через LTree Тип, хоча рекурсивні CTTS все ще вимагають сирого SQL.

---

Резюме порівняння

Д_Е-Е-Е-І-Е-Е-Е-Е-Е-Е-Е-Е-Е-Е-Пі-Е-Е-Па-Пі-Пі-Е-Е-Е-Е-А-Е-Е-Е-І-Е-Е-Е-Е-Е |----------|--------|---------------|-----------------|--------------|---------|-----------------| | Список задоволень Годі з КТАД) з "О" мінімальним значенням | Таблиця клонування Д. д. д. м. д. д. д. д. д. д. д. | Матеріальний шлях ДзЗУП) Noun, a currency* Д. О. О. О. д.) на м. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. | Вкладені набори Дззвінок. Дзвінок. | ltree Дззвінок Ойда, м. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. д. про н. про н. про н. про н. про н.е. про н. про н. про н. про н.е. LTree type] =_BAR_BAR_planet_BAR_planet_BAR_planet_BAR_planet_BAR_planet_BAR_planet_BAR_planets/ postal

n = загальний розмір вузлів, d = глибина, s = піддерево *З відповідним індексом

Блок- схема рішень

flowchart TD
    Start([Start]) --> Q1{Shallow tree?<br/>< 5 levels}
    Q1 -->|Yes| Q2{Need EF Core<br/>navigation properties?}
    Q2 -->|Yes| AL[Adjacency List]
    Q2 -->|No| Q3{Performance<br/>critical?}
    Q3 -->|No| AL
    Q3 -->|Yes| MP[Materialised Path]

    Q1 -->|No| Q4{Read-heavy?}
    Q4 -->|Yes| Q5{Writes rare?}
    Q5 -->|Yes| NS[Nested Sets]
    Q5 -->|No| CT[Closure Table]

    Q4 -->|No| Q6{PostgreSQL only?}
    Q6 -->|Yes| LT[ltree]
    Q6 -->|No| Q7{Need breadcrumbs?}
    Q7 -->|Yes| MP
    Q7 -->|No| CT

    style Start stroke:#10b981,stroke-width:2px
    style AL stroke:#6366f1,stroke-width:2px
    style MP stroke:#8b5cf6,stroke-width:2px
    style NS stroke:#ec4899,stroke-width:2px
    style CT stroke:#f59e0b,stroke-width:2px
    style LT stroke:#14b8a6,stroke-width:2px

Вибір реального світу: цей блог

Цей блог використовує a Таблиця клонування раціональне:

1. Коментарі читаються набагато частіше, ніж написано
2. Нам потрібно ефективно показувати вкладених коментованих ниток
3. Запити з обмеженням глибини важливі для швидкодії (на глибині 5 рівнів)
4. Пересування коментарів - рідкісне явище (час від часу потрібно робити це)

Див. Частина 1. 2: Таблиця клонування за повну реалізацію.

Серія Навігація

• Частина 1: Огляд (Ця стаття)
• Частина 1. 1: Список задоволень - Прості батьківські посилання
• Частина 1. 2: Таблиця клонування - Заздалегідні стосунки
• Частина 1. 3: Матеріальний шлях - Рядки шляхів
• Частина 1. 4: Вкладені набори - Праві/ ліві межі
• Частина 1. 5: ltree - Природний додаток PostgreSQL
• Частина 2: Raw SQL і Dapper (наближається)