і великі методи доступу до файлів, крім хешування. Ці багатоходові збалансовані дерева пошуку в даний час є стандартом організації файлів для додатків, що працюють з діапазоном ключів.
.1 Структура В +-дерева
+-дерево в деяких аспектах є узагальненням дерева двійкового пошуку (BST). Головна відмінність в тому, що вузли B +-дерева мають багато дочірніх вузлів, а не обмежуються тільки двома. Оскільки нашою метою є мінімізувати звернення до диску, то для ефективного пошуку записи, потрібно зробити висоту багатоходового дерева пошуку якомога менше. Ця мета досягається за рахунок того, що в кожному вузлі є велика кількість гілок. +-Дерево порядку b - це таке дерево, в якому кожен внутрішній вузол містить від b / 2 до b дочірніх вузлів і, кількість ключів в кожному вузлі (крім кореня ) повинна бути від b - 1 до 2b - 1. b також відомий як коефіцієнт розгалуження або розгалуження дерева. На малюнку (Рис.1) представлено B + дерево порядку 4.
.2 Характеристика
+-дерева зберігають покажчики на реальні записи тільки на кінцевих вузлах.
Кількість ключів в кожному вузлі (крім кореня) повинна бути від b - 1 до 2b - 1, де b - порядок дерева.
Кореневий вузол чи є листом або має не менше двох дітей.
Внутрішні вузли використовуються тільки як заповнювачі для «керівництва» пошуку. Кількість ключів в кожному внутрішньому вузлі на одиницю менше, ніж число непорожніх дітей. Ключі зберігаються в порядку убування (тобто відсортовані у лексикографічному порядку).
Кінцеві вузли в В +-дереві пов'язані один з одним, формуючи зв'язаний список. Це робиться для того, щоб записи могли бути отримані послідовно без повторного доступу до B +-дереву. Це також підтримує швидку обробку діапазону пошукових записів.
1.3 Твердження про висоті
дерево пошук висота запис
Затвердження.
Висота B + дерева з n? 1 ключами і мінімальним ступенем b? 2 в гіршому випадку не перевищує logb ((n + 1) / 2).
Доказ.
Позначимо висоту B + дерева через h.
Розглянемо максимально високу B + дерево: в корені такого дерева зберігається 1 ключ, а в інших вузлах по b - 1 ключу (мінімально можливу кількість)
На рівні 0 розміщений один вузол (корінь) з 1 ключем
На рівні 1: 2 вузла (у кожного по b - 1 ключу)
На рівні 2: 2b вузлів
На рівні 3: 2b2 вузлів
...
На рівні h: 2bh - 1 вузлів
Тоді, загальна кількість ключів є:
=1 + (b - 1) (2 + 2b + 2b2 + 2b3 +? + 2bh? 1)=
=1 + 2 (b - 1) (1 + b + b2 +? + bh? 1)
Сума h перших членів геометричної прогресії:
=d1 (qh? 1) / (q - 1)
Отже,
=1 + 2 (b - 1) (bh - 1) / (b - 1)=2b? ? 1 + 1=2bh
(n + 1) / 2=bh=logb ((n + 1) / 2)
Затвердження доведено.
2. Основні операції B + дерева
.1 Пошук запису...
