Beer::Code🍺

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

👍38🔥9⚡2🗿1

3.08K viewsKyrylo Sulimovskyi, 17:32