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

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

Як це працює?

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

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

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

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

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

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

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

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

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

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

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

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

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

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