Що означає "B-tree структура індексу"?

B-tree - це базовий тип структури індексу в СУБД, який дозволяє виконувати пошук, вставку й видалення за логарифмічний час O(log n). Він використовується в PostgreSQL, MySQL (InnoDB), Oracle та ін. Його завдання - зберігати ключі у відсортованому вигляді й давати змогу швидко знаходити потрібний діапазон значень.

Якщо по суті, без води, на рівні middle:

#1. Що таке B-tree в контексті індексу

Це збалансоване деревоподібне сховище, в якому:

• кожен вузол містить відсортовані ключі
• вузли мають посилання на дочірні вузли
• дерево завжди збалансоване за висотою (зазвичай 2-4 рівні навіть при мільйонах рядків)
• листки містять посилання на фізичні рядки таблиці (або самі дані - залежить від реалізації)

#2. Як B-tree пришвидшує пошук

Алгоритм пошуку працює як у телефонному довіднику:

• БД іде від кореня
• за ключами всередині вузла розуміє, у якого "нащадка" потрібно спуститися
• повторює крок, поки не дійде до листка
• отримує адресу рядка, не перебираючи всю таблицю

Замість N порівнянь - ~log₂(N). На великих обсягах різниця величезна: замість 1 000 000 порівнянь - близько 20.

#3. Чому саме B-tree, а не звичайне бінарне дерево

Тому що звичайне дерево пошуку легко "складається" в лінію й деградує до O(n). B-tree жорстко контролює баланс, тому ефективність стабільна й передбачувана.

#4. Для яких запитів B-tree ідеальний

• WHERE column = X
• діапазони: BETWEEN, >, <
• ORDER BY, якщо порядок збігається з індексом
• JOIN за індексованими ключами

#5. Важливий нюанс

B-tree погано підходить для LIKE '%text' (символ підстановки на початку), тому що такий запит не можна шукати за сортуванням - там потрібен повний перебір чи інші типи індексів (GIN, GiST, FTS).

#Підсумок

B-tree - це самобалансована індексна структура, яка зберігає відсортовані ключі й дозволяє шукати значення за O(log n), тому запити за умовою, діапазоном, сортуванням і join'ами працюють швидко незалежно від розміру таблиці.

Якщо потрібно - можу в наступному повідомленні намалювати B-tree на прикладі реального індексу й покроково показати, як відбувається WHERE value = 42 на рівні вузлів.