- Що робити, якщо ваш запит в БД відпрацьовує повільно?
- Ну я б спробував(ла) додати індекс.
- Чудово, а чому індекс пришвидшує пошук?
- Нуууу, просто це якась відсортована штука збоку. Ось вона відсортована, пошук швидше.
На моїй практиці 7 з 10 інженерів відповідають приблизно в такому форматі. Можливо тільки в мене така статистика, але пропоную зануритись трошки глибше.
❗️В 90% випадках, незалежно від бази даних (MySQL, Postgres, Mongo) для забезпечення своїх потреб ми будемо використовувати B-Tree або B+Tree індекси.
«Це ж бінарні дерева!» вигукують інженери. І так і ні.
👉 Ця структура - дійсно дерево, і замість того, щоб виконувати пошук по списку і перебирати всі дані O(n), змінивши структуру і розклавши дані у дерево ми будемо виконувати операцію зі складністю ~ O(log n). Якщо дерево бінарне, то і пошук буде бінарним.
❓ Чому важливо, що це не просто бінарне дерево?
При додаванні нового елемента в бінарне дерево - важливий порядок додавання. Перший елемент стає коренем дерева і від нього починають будуватись всі гілки.
Додаємо числа: 10, 5, 15, 3, 7, 12, 20
Крок 1: Додаємо 10 (корінь)
10
Крок 2: Додаємо 5 (менше 10, йде ліворуч)
10
/
5
Крок 3: Додаємо 15 (більше 10, йде праворуч)
10
/ \
5 15
Крок 4: Додаємо 3 (менше 5, йде ліворуч від 5)
10
/ \
5 15
/
3
Крок 5: Додаємо 7 (більше 5, йде праворуч від 5)
10
/ \
5 15
/ \
3 7
Крок 6: Додаємо 12 (менше 15, йде ліворуч від 15)
10
/ \
5 15
/ \ /
3 7 12
Крок 7: Додаємо 20 (більше 15, йде праворуч від 15)
10
/ \
5 15
/ \ / \
3 7 12 20
❗️ Це неминуче призводить до того, що деякі гілки будуть значно довші (вищі) ніж інші. Така структура не може гарантувати швидкість пошуку по всі таблиці з однаковою ефективністю. Ось приклад незбалансованого дерева (в гіршому випадку):
Додаємо числа в порядку зростання: 1, 2, 3, 4, 5, 6, 7
1
\
2
\
3
\
4
\
5
\
6
\
7
Таке дерево фактично стає зв'язним списком з складністю пошуку O(n).
👍 Для вирішення цієї проблеми придумали збалансовані дерева. Тут при кожній операції вставки алгоритм обертає значення таким чином, щоб як умога довше забезпечити однакову висоту по всьому дереву. Обертання - досить дорога операція, і це сильно сповільнює вставку.
Припустимо, у нас є незбалансоване дерево, яке "виросло" вліво:
30
/
20
/ \
10 25
Необхідно виконати праве обертання навколо кореня (30):
Крок 1: Беремо вузол 20 як новий корінь
Крок 2: Старий корінь (30) стає правим нащадком нового кореня
Крок 3: Правий нащадок нового кореня (якщо є) стає лівим нащадком
старого кореня (25 стає зліва)
Результат:
20
/ \
25 30
/
10
Тепер дерево збалансоване
Розглянемо складніший випадок з подвійним обертанням. Дано:
30
/
10
\
20
Тут праве обертання не виправить ситуацію. Потрібне подвійне обертання:
Спочатку ліве обертання навколо 10:
30
/
20
/
10
Потім праве обертання навколо 30:
20
/ \
10 30
✅️️️️️️️ Інженери пішли далі і сьогодні ми маємо такі різновиди збалансованих дерев як B-Tree та B+Tree. В них при операції вставки ми не одразу породжуємо нову ноду, а намагаємось вставити дані за певним алгоритмом, щоб зберегти висоту. Це породжує декілька значень на рівні однієї ноди:
[15, 50]
/ | \
[5] [20] [70]
🤓 Але про них ми більш подробно поговоримо в наступному пості. Отже, головний посил, що індекси - не магія і не просто "якась штука збоку". Це конкретні структури даних, що пришвидшують пошук.
#database #middle