B-дерево-індекс — це збалансована деревоподібна структура даних, яка широко використовується в базах даних для ефективної організації та пошуку великих обсягів даних.
B-дерева дуже схожі на бінарні дерева пошуку (BST), але вузли в B-дереві можуть мати більше ніж двох нащадків.

B-дерево зберігає ключі у відсортованому порядку всередині вузлів, що дозволяє швидко отримувати дані шляхом ієрархічного проходження від кореня до листових вузлів. Індексація за B-деревом добре підходить для запитів діапазону та пошуку за рівністю, що робить її популярним вибором для оптимізації продуктивності бази даних.

Як це працює?

B-дерево-індекс організовує дані у ієрархічній структурі, де кожен вузол містить фіксовану кількість ключів і покажчиків на дочірні вузли.
B-дерева підтримують баланс, гарантуючи, що всі листові вузли знаходяться на одному рівні, що оптимізує операції пошуку.
Під час пошуку певного ключа алгоритм B-дерева проходить дерево від кореневого вузла до листових, використовуючи бінарний пошук для ефективного знаходження потрібного ключа.

Пошук за індексом передбачає проходження дерева до листових вузлів, подальше слідування ланцюжком листових вузлів для знаходження відповідних записів і отримання фактичних даних з диска.

На рисунку показано пошук ключа 302:

1. Структура дерева пошуку — це тип дерева, де кожен вузол має два покажчики: лівий вказує на дочірні вузли зі значеннями меншими за значення батьківського вузла, а правий — на дочірні вузли зі значеннями більшими за значення батьківського вузла;

2. У B-дереві кореневий вузол може містити кілька індексних значень. Наприклад, якщо корінь містить три різні значення, він матиме три покажчики, кожен з яких вказує на діапазон значень між цими ключами;

3. Для пошуку ключа, наприклад 302, пошук починається з кореневого вузла і слідує відповідними покажчиками до листових вузлів. Пошук завершується після проходження трьох блоків дерева, як показано на схемі, виділеній червоним;

4. Для пошуку діапазону значень, починаючи з 302, можна використовувати горизонтальні покажчики між листовими вузлами. Наприклад, отримання значень від 302 до 502 здійснюється послідовним проходженням листових вузлів.

Переваги та недоліки

На відміну від стандартної структури даних бінарного дерева пошуку, вузли B-дерева можуть містити більше ніж 2 нащадки. Типове максимальне число нащадків для одного вузла зазвичай встановлено на 16.

Реалізація індексу

Щоб створити індекс B-дерева для стовпця у PostgreSQL, можна використати наступну SQL-команду:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Оскільки індекс B-дерева є індексом за замовчуванням у SQL, також можна використати таку інструкцію для його створення:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);