Що означає термін «індексне дерево»?

Індексне дерево - це внутрішня структура, у якій база даних зберігає індекси, щоб швидко шукати, вставляти й видаляти дані. Зазвичай використовується структура B-tree (або її варіанти: B+-tree, B*-tree).

#Принцип

• Дані в дереві відсортовані за ключем (наприклад, id, email);
• Кожен вузол зберігає ключі й посилання на дочірні вузли;
• Пошук іде від кореня до листків, кожен крок наближає до потрібного значення.

#Приклад на аналогії

Уяви телефонний довідник:

• букви А-Я - це «гілки дерева»;
• усередині кожної гілки імена відсортовані. Коли шукаєш «Сидоренко», не переглядаєш увесь довідник - одразу переходиш до букви «С», а потім - до потрібної сторінки.

#Переваги індексного дерева

• O(log n) складність пошуку (замість O(n) без індексу);
• ефективні операції вставки й видалення без повної перебудови;
• дані лишаються відсортованими, що прискорює ORDER BY і діапазонні запити (BETWEEN, >, <).

У сучасних СУБД (PostgreSQL, MySQL, Oracle) майже всі звичайні індекси побудовані саме на B-деревах, бо вони забезпечують баланс між швидкістю та стабільністю.