B+ дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Простий приклад B+ дерева, яке пов'язує ключі 1-7 до значень даних d1-d7. Зв'язаний список (червоний) дозволяє швидкий обхід в центрованому порядку.

B+ дерево (англ. B+ tree) або Бі плюс дерево — тип дерева, яке подає відсортовані дані в вигляді, що дозволяє швидке додавання, отримання і видалення записів, кожен з яких ототожнений ключем. Це динамічний, багаторівневий індекс, з верхньою та нижньою межами на кількість ключів в кожному сегменті індекса (блоці або вершині). В 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 \le m \le 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_bn) операцій
  • Пошук запису потребує O(\log_bn) операцій
  • Видалення (вже знайденого) запису потребує O(\log_bn) операцій
  • Виконання запиту, який отримує діапазон значень, що містить k елементів, потребує O(\log_bn+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), то додати запис
  • В іншому випадку необхідно розщепити блок
    • Додати новий блок, перемістити половину елементів з існуючого до нового
    • Додати найменший ключ та адресу з нового блоку до батьківського блоку
    • Якщо батьківський блок заповнено, аналогічно розділити його.
      • Додати середній ключ до батьківського блоку
    • Повторювати, поки батьківський блок не буде потребувати розщеплення.
  • Якщо розщеплюється корінь — створити новий корінь, який має один ключ і два покажчика (значення, яке додається до кореня, видаляється з свого вузла)

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

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

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

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

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

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

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

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

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

  1. а б в г д Ramakrishnan Raghu, Gehrke Johannes — Database Management Systems, McGraw-Hill Higher Education (2000), 2ге видання (en) сторінка 267
  2. SQLite Version 3 Overview
  3. CouchDB Guide (дивись заувагу після 3го параграфа)
  4. Tokyo Cabinet reference