Знову про індекси

- Що робити, якщо ваш запит в БД відпрацьовує повільно?
- Ну я б спробував(ла) додати індекс.
- Чудово, а чому індекс пришвидшує пошук?
- Нуууу, просто це якась відсортована штука збоку. Ось вона відсортована, пошук швидше.

На моїй практиці 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

B-Tree та B+Tree індекси

👉 Саме вони є найбільш розповсюдженими в нашому повсякденному житті. Майже всі популярні БД (PostgreSQL, MySQL/InnoDB, SQLite, MongoDB і т.д.) використовують B+Tree для зберігання індексів. Як зазначено в попередньому пості, це різновиди збаланосованих дерев. Головна особливість в тому, що кожен вузол може мати більше двох нащадків (на відміну від бінарного дерева), а також може мати кілька ключів (значень) в одному вузлі.

Порядок B-Tree (зазвичай позначається як m) визначає максимальну кількість нащадків, які може мати вузол.
- Кожна нода (крім кореня) має від ceil(m/2)-1 до m-1 ключів
- Корінь має від 1 до m-1 ключів
- Нода з k ключами має k+1 дочірніх нод

❗️У нашому прикладі ми використовуємо B-Tree порядку 3, це значить, що може бути до 2 ключів у кожному вузлі, і до 3 нащадків для кожного вузла відповідно.

📍 B+Tree відрізняється від B-Tree тим, що всі дані зберігаються тільки в листкових вузлах, які додатково пов'язані між собою як зв'язний список, що значно пришвидшує послідовне читання а значить і кращу продуктивність при пошуку близьких значень.

Алгоритм вставки:

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

[5, 15]
/ | \
[3] [10,20,30] [40]

1. У нас є переповнена нода: [10, 20, 30]
2. Медіана: 20
3. Розділяємо на: [10] і [30]
4. 20 піднімається до батьківської ноди

[5, 15, 20]
/ / \ \
[3] [10] [30] [40]


Продовжуємо процес, бо [5, 15, 20] теж переповнена:

1. Медіана: 15
2. Розділяємо на: [5] і [20]
3. 15 піднімається вище

Припустимо, що раніше наше дерево мало корінь з одним елементом [50], до якого ми додаємо 15:

Проміжний результат:

[15, 50]
/ | \
[5] [20] [...]

Остаточно структура виглядає так:
[15, 50]
/ | \
[5] [20] [...]
/ \ / | \
[3] [10] [...] [30] [40]
При цьому складність пошуку гарантовано буде O(log_m n), де m — порядок дерева, як я зазначав вище.

❓ "Перебудова індексу", або чому вставки такі дорогі?

🔥 Основна причина популярності цих індексів - оптимізація роботи з диском. Диск читається блоками (вони ж сторінки індексу фіксованого розміру, зазвичай 4KB, 8KB або 16KB залежно від БД), і B-дерева чудово це використовують, зберігаючи багато ключів в одному вузлі.

Fill Factor (фактор заповнення) - параметр, який визначає, наскільки заповненими будуть сторінки індексу при їх створенні. Наприклад, fill factor 70% означає, що сторінки заповнюються на 70%, залишаючи 30% вільного місця для майбутніх вставок.
Коли сторінка індексу заповнюється повністю (через вставки даних), відбувається операція розщеплення сторінки (page split):

1️⃣ Створюється нова сторінка
2️⃣ Приблизно половина даних переміщується в нову сторінку
3️⃣ Середній ключ "піднімається" до батьківської сторінки
4️⃣ Батьківська сторінка оновлює свої посилання

❗️Це і є супер дорога операція, бо вимагає виділення нової сторінки на диску, переміщення даних, оновлення посилань, можливе розщеплення батьківських сторінок (каскадний ефект).

Також налаштування fill factor може підвищити продуктивність бази даних:

Для таблиць з частими вставками — низький fill factor (70-80%)
Для таблиць тільки для читання — високий fill factor (90-100%)

# Postgres

CREATE TABLE my_table (
 id serial PRIMARY KEY,
 data text
 ) WITH (fillfactor = 70);

# Для InnoDB доступний параметр fillfactor на рівні сервера
# в my.cnf або my.ini

[mysqld]
innodb_fill_factor = 80

👍 Сподіваюсь, у світі стало трошки менше магії, і трошки більше розуміння того, як працюють системи, якими ми користуємось щодня.

#database #middle