B+ дерево

Простий приклад B+ дерева, яке пов'язує ключі 1-7 до значень даних d₁-d₇. Зв'язаний список (червоний) дозволяє швидкий обхід в центрованому порядку.

B+ дерево (англ. B+ tree) або Бі плюс дерево — тип дерева, яке подає відсортовані дані в вигляді, що дозволяє швидке додавання, отримання і видалення записів, кожен з яких ототожнений ключем. Це динамічний, багаторівневий індекс, з верхньою та нижньою межами на кількість ключів в кожному сегменті індекса (блоці або вершині). В B+ дереві, на відміну від B-дерева, всі записи зберігаються на рівні листових вузлів дерева; у внутрішніх вузлах зберігаються лише ключі.

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

Файлові системи NTFS, ReiserFS, NSS, XFS, JFS і ReFS використовують цей тип дерева для індексування метаданих. Реляційні системи керування базами даних такі як IBM DB2, Informix, Microsoft SQL Server, Oracle 8, Sybase ASE, і SQLite підтримують цей тип дерев для табличних індексів. СКБД ключ-значення такі як CouchDB, Tokyo Cabinet підтримують цей тип дерева для доступу до даних.

Загальний огляд

Порядок або покажчик галуження b для B+ дерева вимірює місткість вершин (тобто кількість дочірніх вершин) для внутрішніх вузлів дерева. Поточна кількість дочірніх вершин, тут позначається як m, для внутрішніх вузлів обмежується $\lceil b/2\rceil \leq m\leq b$. Корінь становить виняток: йому дозволено мати всьог дві дочірні вершини. Наприклад, якщо порядок B+ дерева 7, кожна внутрішня вершина (за винятком кореня) може мати від 4 до 7 дочірніх. Листя не мають дітей, але мають містити від $\lfloor b/2\rfloor$ до $b-1$. У випадку якщо B+ дерево майже попрожнє, воно містить лише одну листову вершину, тоді корінь буде листом. Такій вершині дозволено містити від 1 до b ключів.

Тип вершини	Тип дитини	Мін. дочірніх	Макс. дочірніх	Припустимо b = 7	Припустимо b = 100
Корінь (коли це лише одна вершина в дереві)	Ключі	1	b	1 - 7	1 - 100
Корінь	Внутрішні або листя	2	b	2 - 7	2 - 100
Внутрішя вершина	Внутрішні або листя	$\lceil b/2\rceil$	b	4 - 7	50 - 100
Вершина лист	Ключі	$\lfloor b/2\rfloor$	b - 1	3 - 6	50 - 99

Характеристики

Для Б+ дерева з покажчиком галуження b та h рівнями індексів:

• Максимальная кількість записів, що зберігаються $n_{max}=b^{h}-b^{h-1}$
• Мінімальна кількість записів, що зберігаються $n_{min}=2\left\lceil {\frac {b}{2}}\right\rceil ^{h-1}$
• Мінімальна кількість ключів $n_{kmin}=2\left\lceil {\frac {b}{2}}\right\rceil ^{h}-1$
• Максимальна кількість ключів $n_{kmax}=n^{h}$
• Простір, необхідний для зберігання дерева $O(n)$
• Вставка запису потребує $O(\log _{b}n)$ операцій
• Пошук запису потребує $O(\log _{b}n)$ операцій
• Видалення (вже знайденого) запису потребує $O(\log _{b}n)$ операцій
• Виконання запиту, який отримує діапазон значень, що містить k елементів, потребує $O(\log _{b}n+k)$ операцій
• Виконання сторінкового запиту з розміром сторінки s та номером сторінки p потребує $O(p*s)$ операцій

Алгоритми

Пошук

Корінь Б+ дерева представляє весь діапазон значень в дереві, де кожен внутрішній вузол є підінтервалом. Нехай необхідно знайти значення k. Починаючи з кореня виконується пошук листа, який може містити значення k. На кожному вузлі необхідно з'ясувати, на який наступний внутрішній вузол необхідно слідувати. Внутрішній вузол Б+ дерева має не більше ніж b дітей, кожен з яких являє собою окремий підінтервал. Ми обираємо відповідний вузол за допомогою пошуку у ключових значеннях вузла.

Function: search (k)
  return tree_search (k, root);
 
Function: tree_search (k, node)
  if node is a leaf then
    return node;
  switch k do
  case k < k_0
    return tree_search(k, p_0);
  case k_i ≤ k < k_{i+1}
    return tree_search(k, p_{i+1});
  case k_d ≤ k
    return tree_search(k, p_{d+1});

Цей псевдокод розрахован на те, що дублікати не допускаються.

Додавання

В першу чергу необхідно знайти блок, в який необхідно додати новий запис.

• Якщо блок не повністю заповнений (кількість елементів після вставки не більше ніж $b-1$), то додати запис
• В іншому випадку необхідно розщепити блок
  • Додати новий блок, перемістити половину елементів з існуючого до нового
  • Додати найменший ключ та адресу з нового блоку до батьківського блоку
  • Якщо батьківський блок заповнено, аналогічно розділити його.
    • Додати середній ключ до батьківського блоку
  • Повторювати, поки батьківський блок не буде потребувати розщеплення.
• Якщо розщеплюється корінь — створити новий корінь, який має один ключ і два покажчика (значення, яке додається до кореня, видаляється з свого вузла)

Б-дерева розширюється зі сторони кореня, а не зі сторони листів.

Видалення

В першу чергу необхідно знайти блок, в якому знаходиться запис, який необхідно видалити.

• Видалити запис
  • Якщо блок хоча б наполовину заповнений – завершення алгоритму
  • Якщо блок має менше елементів
    • Виконати спробу перерозподілити елементи, тобто додати до вузла елемент з брата (вузла, з яким поточний має спільного батька)
    • Якщо виконати перерозподіл не вдалось, об'єднати вузол з братом
• Якщо відбулося об’єднання, видалити запис (який вказує на видалений блок або його брата) з батьківського блоку
• Об’єднання може поширюватись на корінь, тоді відбувається зменшення висоти дерева

Масове завантаження

Маючи набір записів даних необхідно створити індексне Б+ дерево за деяким ключовим полем. Один підхід полягає у вставці кожного запису в порожнє дерево окремо. Тим не менш, це досить дорого, тому що для додавання кожного запису необхідно виконати весь алгоритм – пройти від кореня до листового вузла. Ефективною альтернативою є використання масового завантаження:

• Відсортувати записи, що додаються, відповідно до ключів
• Створити порожній вузол, який буде кореневим, та додати до нього покажчик на перший блок записів
• Коли корінь повний – розщепити корінь, створити новий кореневий вузол
• Додавати записи в крайній правий індексний вузол, на рівень вище листового рівня, поки всі дані не будуть додані

Коли самі праві індексні вузли заповнюються – відбувається розщеплення. Це, в свою чергу, викликає розщеплення самого правого вузла на рівень вище до кореня. Тобто, розщеплення відбувається тільки у самому правому шляху від кореня до листових вузлів.