Б-дерево

B-tree
Тип	Дерево
Винайдено	1972
Винайшли	Рудольф Байер, Едвард МакКрейт
Обчислювальна складність у записі великого О
	Середня	Найгірша
Простір	O(n)	O(n)
Пошук	O(log n)	O(log n)
Вставляння	O(log n)	O(log n)
Видалення	O(log n)	O(log n)

Зображення Б-дерева

Б-дерева (англ. B-tree) — це один з видів збалансованих дерев, що забезпечують ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на червоно-чорні, різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому константа в оцінці O(log n) для висоти дерева менша, ніж для червоно-чорних дерев. Як і червоно-чорні дерева, Б-дерева дозволяють реалізувати багато операцій з множинами розміру n за час O(log n).

Вузол x, який зберігає n[x] ключів, має n[x]+1 дітей. Ключі, що зберігаються в x служать границями, що розділяють всіх його нащадків на n[x]+1 груп; за кожну групу відповідає один з нащадків x. При пошуку в Б-дереві ми порівнюємо шуканий ключ з n[x] ключами, що зберігаються в x, і за результатами порівняння вибираємо одного з n[x]+1 нащадків.

Історія

Б-дерево було розроблене у 1972 році Рудольфом Байером та Едвардом МакКрейтом.

Особливості роботи з інформацією, що розміщується на диску

Алгоритми, що працюють з Б-деревами, зберігають в оперативній пам'яті лише невелику частину всієї інформації (фіксоване число секторів).

Диск розглядається як велика ділянка пам'яті, робота з яким відбувається наступним чином: перед тим як працювати з об'єктом x, виконується спеціальна операція Disk — Read(x) (читання з диска). Після внесення змін в об'єкт x виконується операція Disk — Write(x) (запис на диск).

Час роботи програми в основному визначається кількістю цих операцій, так що має сенс читати / записувати як можна більше інформації за один раз і зробити так, щоб вузол Б-дерева заповнював повністю один сектор диска. Таким чином, ступінь розгалуження (число дітей вузла) визначається розміром сектора.

Типова ступінь розгалуження Б-дерев знаходиться між 50 і 2000 в залежності від розміру елемента. Збільшення ступеня розгалуження різко скорочує висоту дерева, і тим самим число звернень до диску, при пошуку. Наприклад, Б-дерево ступеня 1001 і висоти 2 може зберігати понад мільярд ключів. Враховуючи, що корінь можна постійно зберігати в оперативній пам'яті, достатньо двох звернень до диска при пошуку потрібного ключа.

Вважаємо, що прикладна інформація, пов'язана з ключем, зберігається в тому ж вузлі дерева. На практиці це не завжди зручно, і в реальному алгоритмі вузол може містити лише посилання на сектор, де вона зберігається.

Визначення Б-дерева

Б-деревом називають кореневе дерево, влаштоване наступним чином. Кожен вузол x містить наступні поля:

• n[x] — кількість ключів, що зберігаються у вузлі x;
• key₁[x], key₂[x], … ,key_n(x)[x] — самі ключі в не спадаючому порядку;
• leaf[x] — булеве значення, істинне, коли вузол x є листом.

Якщо x — внутрішній вузол, то він містить покажчики c₁[x], c₂[x] c_n(x)+1[x], на його дітей в кількості n[x]+1.

• У листів дітей немає, і ці поля для них не визначені.
• Усі листя знаходяться на одній і тій же глибині, що дорівнює висоті дерева.
• Можлива кількість ключів, що зберігаються в одному вузлі, визначається параметром t≥2, яке називається мінімальним ступенем Б-дерева.
• Для кожного некореневого вузла x виконується нерівність (t-1)≤n[x]≤(2t-1). Таким чином, число дітей у будь-якого внутрішнього вузла (крім кореня) знаходиться в межах від t до 2t.
• Якщо дерево не пусте, то в корені повинен зберігатися хоча б один ключ. Вузол, який зберігає рівно 2t-1 ключів, буде називатися повним.

Ключі key_i[x] служать границями, що розділяють значення ключів в піддеревах. Точніше,

• c₁[x] посилається на піддерево, ключі в якому менше, ніж key₁[x];
• c_i[x] при i=2,3n посилається на піддерево, ключі в якому знаходяться в межах від key_i-1[x] до key_i[x];
• c_n(x)+1[x] посилається на піддерево, ключі в якому більше, ніж key_n(x)[x].

У випадку, коли t=2, у кожного внутрішнього вузла 2, 3 або 4 нащадка, виходить так зване 2-3-4 — дерево. Для ефективної роботи з диском на практиці t вибирають досить великим. Число звернень до диска для більшості операцій пропорційно висоті Б-дерева.

Для висоти $h$ Б-дерева з $n$ елементами даних:

$h\leq \log _{t}\left({n+1 \over 2}\right)$

Основні операції з Б-деревами

Корінь Б-дерева розміщують в оперативній пам'яті, при цьому читання з диска для кореня ніколи не потрібно, а проте всякий раз, коли змінюється корінь, його зберігають на диску. Усі вузли, що передаються як параметри, вже зчитані з диска. Всі процедури обробляють дерево за один прохід від кореня до листів.

Пошук в Б-дереві

Пошук в Б-дереві схожий на пошук в двійковому дереві пошуку. Різниця в тому, що в кожному вузлі x вибирається один варіант з (n[x]+1), а не з двох. При пошуку проглядаються вузли дерева від кореня до листа. Тому число звернень до диску є O(h)=O(log_tn), де h — висота дерева, а n — кількість ключів. Так як n[x]≤2t, то час обчислень дорівнює O(th)=O(t×log_tn) .

Створення порожнього Б-дерева

Створення порожнього Б-дерева здійснюється за допомогою процедури, яка знаходить місце на диску для нового вузла та розміщує його. Це можна реалізувати за час O(1) і не використовувати операцію читання з диска.

Додавання елемента в Б-дерево

Додавання елемента в Б-дерево здійснюється з використанням процедури розбиття повного (з 2t-1 ключами) вузла y на два вузли, що мають по t-1 елементів у кожному. При цьому ключ-медіана key t[y] відправляється до батька x вузла y і стає роздільником двох отриманих вузлів. Це можливо, якщо вузол x не вичерпний. Якщо y — корінь, процедура працює аналогічно. В цьому випадку висота дерева збільшується на одиницю.

Процедура додавання нового елемента проходить один раз від кореня до листа, на це потрібен час O(th)=O(t×log_tn) і O(h) звернень до диска, де h — висота дерева. По ходу справи поділяються повні вузли, що зустрічаються на шляху. Зауважимо, що якщо повний вузол має неповного батька, то його можна розділити, тому що в батька є місце для додаткового ключа, тому, піднімаючись вгору, доходимо до неповного листа, куди і додаємо новий елемент.

Видалення елемента

Видалення елемента з B-дерева відбувається аналогічно додаванню, хоча трохи складніше. Видалення ключа з В-дерева, хоча і аналогічно вставці, являє собою складнішу задачу. Це пов'язано з тим, що ключ може бути видалений з будь-якого вузла, а не тільки з листа, а видалення з внутрішнього вузла вимагає певної перебудови дочірніх вузлів. Як і у випадку вставки, ми повинні забезпечити, щоб при виконанні операції видалення не були порушені властивості В-дерева. Аналогічно тому, як ми мали можливість переконатися, що вузли не надто сильно заповнені для вставки нового ключа, нам належить переконатися, що вузол не стає занадто мало заповнений в процесі видалення ключа (за винятком кореневого вузла, який може мати менше t — 1 ключів, хоча і не може мати більше 2t — 1 ключів).

Отже, нехай процедура B_TREE_DELETE повинна видалити ключ k з піддереві, коренем якого є вузол x. Ця процедура розроблена таким чином, що при її рекурсивному виклику для вузла х гарантована наявність в цьому вузлі принаймні t ключів. Ця умова вимагає наявності у вузлі більшої кількості ключів, ніж мінімальна в звичайному В-дереві, так що іноді ключ може бути переміщений в дочірній вузол перед тим, як рекурсія звернеться до цього дочірньому вузлу. Таке посилення властивості В-дерева (наявність «запасного» ключа) дає нам можливість виконати видалення ключа за один спадний прохід по дереву (з єдиним винятком, який буде пояснено пізніше). Слід також врахувати, що якщо корінь дерева х стає внутрішнім вузлом, що не містить жодного ключа (така ситуація може виникнути в розглянутих нижче випадках 2в і 36), то вузол х віддаляється, а його єдиний дочірній вузол С₁[х] стає новим коренем дерева (при цьому зменшується висота В-дерева і зберігається його властивість, що вимагає, щоб кореневий вузол непорожнього дерева містив як мінімум один ключ).

Замість того щоб представити вам повний псевдокод процедури видалення вузла з В-дерева, ми просто накидаємо послідовність виконуваних дій.

1. Якщо вузол k знаходиться у вузлі x і x є листом — видаляємо k з х.

2. Якщо вузол k знаходиться у вузлі х і х є внутрішнім вузлом, виконуємо наступні дії: а) Якщо дочірній по відношенню до х вузол у, попередній ключу k у вузлі x, містить не менше t ключів, то знаходимо до k' попередника k в піддереві, коренем якого є у. Рекурсивно видаляємо k' і замінюємо k в х ключем k'. (Пошук ключа k' і видалення його можна виконати в процесі одного спадного проходу.)

б) Ситуація, симетрична ситуації а: якщо дочірній по відношенню до х вузол z, наступний за ключем k в вузлі x, містить не менше t ключів, то знаходимо k' — наступний за k ключ в піддереві, коренем якого є z. Рекурсивно видаляємо k' і замінюємо k в х ключем k'. (Пошук ключа k' і видалення його можна виконати в процесі одного спадного проходу.)

в) У противному випадку, якщо і y, і z містять по t — 1 ключів, вносимо k і всі ключі z в у (при цьому з х видаляється k і покажчик на z, а вузол у після цього містить 2t — 1 ключів), а потім звільняємо z і рекурсивно видаляємо k з у.

3. Якщо ключ k відсутній у внутрішньому вузлі х, знаходимо корінь c_і[х] піддерева, яке повинно містити k (якщо такий ключ є в даному В-дереві). Якщо c_і[х] містить тільки t — 1 ключів, виконуємо крок 3а або 3б для того, щоб гарантувати, що далі ми переходимо в вузол, що містить як мінімум t ключів. Потім ми рекурсивно видаляємо k з піддерева з коренем c_і[х].

а) Якщо c_і[х] містить тільки t — 1 ключів, але при цьому один з її безпосередніх сусідів (під яким ми розуміємо дочірній по відношенню до х вузол, відокремлений від розглянутого рівно одним ключем-роздільником) містить як мінімум t ключів, передамо в c_і[х] ключ-роздільник між даними вузлом і його безпосереднім сусідом з x, на його місце помістимо крайній ключ із сусіднього вузла і перенесемо відповідний покажчик із сусіднього вузла в c_і[х].

б) Якщо і c_і[х] і обидва його безпосередніх сусіда містять по t — 1 ключів, об'єднаємо c_і[х] з одним з його сусідів (при цьому колишній ключ-роздільник з x стане медіаною нового вузла).

Примітки

• Bayer, R.; McCreight, E. (1972), Organization and Maintenance of Large Ordered Indexes (PDF), Acta Informatica, 1 (3): 173—189, doi:10.1007/bf00288683
• Comer, Douglas (June 1979), The Ubiquitous B-Tree, Computing Surveys, 11 (2): 123—137, doi:10.1145/356770.356776, ISSN 0360-0300.
• Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2001), Introduction to Algorithms (вид. друге), MIT Press and McGraw-Hill, с. 434—454, ISBN 0-262-03293-7. Chapter 18: B-Trees.
• Folk, Michael J.; Zoellick, Bill (1992), File Structures (вид. 2nd), Addison-Wesley, ISBN 0-201-55713-4
• Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, т. Volume 3 (вид. друге), Addison-Wesley, ISBN 0-201-89685-0. Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

Першоджерела

• Bayer, Rudolf; McCreight, E. (July 1970), Organization and Maintenance of Large Ordered Indices (PDF), т. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories.
• Bayer, Rudolf (1971), Binary B-Trees for Virtual Memory, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California

Див. також

• Список структур даних
• Список алгоритмів
• Двійкове дерево пошуку
• Дерева пошуку
• Збалансоване дерево
• Червоно-чорне дерево