B+ дерево

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

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

Головне значення 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
CouchDB Guide (дивись заувагу після 3го параграфа)
Tokyo Cabinet reference. Архів оригіналу за 12 вересня 2009. Процитовано 21 січня 2012.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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

[SQLite-2] SQLite Version 3 Overview

[CouchDB-3] CouchDB Guide (дивись заувагу після 3го параграфа)

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