B+ дерево

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

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

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

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

Загальний огляд[ред. | ред. код]

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

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

Видалення[ред. | ред. код]

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

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

Масове завантаження[ред. | ред. код]

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

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

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

Примітки[ред. | ред. код]

↑ ^а ^б ^в ^г ^д Ramakrishnan Raghu, Gehrke Johannes — Database Management Systems, McGraw-Hill Higher Education (2000), 2ге видання (en) сторінка 267
↑ SQLite Version 3 Overview. Архів оригіналу за 21 січня 2012. Процитовано 21 січня 2012.
↑ CouchDB Guide (дивись заувагу після 3го параграфа). Архів оригіналу за 19 січня 2012. Процитовано 21 січня 2012.
↑ Tokyo Cabinet reference. Архів оригіналу за 12 вересня 2009. Процитовано 21 січня 2012.

[DMS-1] а ^б ^в ^г ^д Ramakrishnan Raghu, Gehrke Johannes — Database Management Systems, McGraw-Hill Higher Education (2000), 2ге видання (en) сторінка 267

[SQLite-2] SQLite Version 3 Overview. Архів оригіналу за 21 січня 2012. Процитовано 21 січня 2012.

[CouchDB-3] CouchDB Guide (дивись заувагу після 3го параграфа). Архів оригіналу за 19 січня 2012. Процитовано 21 січня 2012.

[TC-4] Tokyo Cabinet reference. Архів оригіналу за 12 вересня 2009. Процитовано 21 січня 2012.

[1]

[2]

[3]

[4]