Що таке B-Tree індекс?

B-Tree індекс - це основний і найпоширеніший тип індексу в СУБД. Він зберігає дані в збалансованому деревоподібному вигляді, щоб прискорити пошук, вставку, видалення й сортування.

#Як влаштоване B-Tree

• Дерево складається з вузлів (nodes): кореневого, проміжних і листових.
• Кожен вузол містить ключі (значення поля) і вказівники на дочірні вузли.
• Усі ключі всередині вузлів відсортовані, що дозволяє швидко знаходити потрібний діапазон.
• Листові вузли містять посилання на реальні рядки таблиці (або самі дані - за кластеризації).

Дерево збалансоване, тобто всі шляхи від кореня до листків мають однакову довжину -> пошук завжди займає O(log n) кроків, незалежно від розміру таблиці.

#Як працює пошук

Приклад: індекс за age

1. SQL іде від кореня і на кожному рівні обирає, куди рухатися (менше / більше).
2. Досягає листового вузла, де зберігається точне значення й посилання на рядок таблиці.
3. За діапазонних запитів (BETWEEN, >, <) - прохід листками послідовно, оскільки вони пов'язані між собою.

#Переваги

• Підходить для пошуку за діапазоном (>, <, BETWEEN), сортування (ORDER BY) і групування (GROUP BY).
• Забезпечує логарифмічну складність (O(log n)), навіть за мільйонів рядків.
• Автоматично підтримується в збалансованому стані під час вставок і видалень.

#Недоліки

• Потребує додаткової пам'яті.
• Вставки в середину діапазону трохи повільніші (дерево частково перебудовується).
• Менш підходить для точкових запитів за хеш-значеннями.

Підсумок: B-Tree - це основний тип індексу в SQL, що реалізує швидкий пошук за відсортованими значеннями. Він універсальний і використовується майже в усіх СУБД (MySQL InnoDB, PostgreSQL, Oracle, SQL Server) за замовчуванням.