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

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

  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
Отримано з http://uk.wikipedia.org/w/index.php?title=B%2B_дерево&oldid=11930861