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

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

Як це працює?

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

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

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

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

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

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

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

Примітка

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

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

На відміну від стандартної структури даних бінарного дерева пошуку, вузли 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,..);

Note

In SQL, when you create a table with a primary key constraint, most database management systems automatically create an index on the column(s) specified in the primary key. This index helps enforce the uniqueness constraint of the primary key and also improves the performance of queries that involve searching or joining based on the primary key column(s).