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 👍 Сподіваюсь, у світі стало трошки мен