B-Tree та B+Tree індекси Саме вони є найбільш розповсюджени | Beer::PHP 🍺
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):
Створюється нова сторінка
Приблизно половина даних переміщується в нову сторінку
Середній ключ "піднімається" до батьківської сторінки
Батьківська сторінка оновлює свої посилання
Це і є супер дорога операція, бо вимагає виділення нової сторінки на диску, переміщення даних, оновлення посилань, можливе розщеплення батьківських сторінок (каскадний ефект).
Також налаштування 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
