Б-дерево
Б-дерева (англ. B-tree) — це один з видів збалансованих дерев, що забезпечують ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на червоно-чорні, різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому константа в оцінці O(log n) для висоти дерева менша, ніж для червоно-чорних дерев. Як і червоно-чорні дерева, Б-дерева дозволяють реалізувати багато операцій з множинами розміру n за час O(log n).
| 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) |
Вузол 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;
- key1[x], key2[x], … ,keyn(x)[x] — самі ключі в не спадаючому порядку;
- leaf[x] — булеве значення, істинне, коли вузол x є листом.
Якщо x — внутрішній вузол, то він містить покажчики c1[x], c2[x] cn(x)+1[x], на його дітей в кількості n[x]+1.
- У листів дітей немає, і ці поля для них не визначені.
- Усі листя знаходяться на одній і тій же глибині, що дорівнює висоті дерева.
- Можлива кількість ключів, що зберігаються в одному вузлі, визначається параметром t≥2, яке називається мінімальним ступенем Б-дерева.
- Для кожного некореневого вузла x виконується нерівність (t-1)≤n[x]≤(2t-1). Таким чином, число дітей у будь-якого внутрішнього вузла (крім кореня) знаходиться в межах від t до 2t.
- Якщо дерево не пусте, то в корені повинен зберігатися хоча б один ключ. Вузол, який зберігає рівно 2t-1 ключів, буде називатися повним.
Ключі keyi[x] служать границями, що розділяють значення ключів в піддеревах. Точніше,
- c1[x] посилається на піддерево, ключі в якому менше, ніж key1[x];
- ci[x] при i=2,3n посилається на піддерево, ключі в якому знаходяться в межах від keyi-1[x] до keyi[x];
- cn(x)+1[x] посилається на піддерево, ключі в якому більше, ніж keyn(x)[x].
У випадку, коли t=2, у кожного внутрішнього вузла 2, 3 або 4 нащадка, виходить так зване 2-3-4 — дерево. Для ефективної роботи з диском на практиці t вибирають досить великим. Число звернень до диска для більшості операцій пропорційно висоті Б-дерева.
Для висоти Б-дерева з елементами даних:
Основні операції з Б-деревами
Корінь Б-дерева розміщують в оперативній пам'яті, при цьому читання з диска для кореня ніколи не потрібно, а проте всякий раз, коли змінюється корінь, його зберігають на диску. Усі вузли, що передаються як параметри, вже зчитані з диска. Всі процедури обробляють дерево за один прохід від кореня до листів.
Пошук в Б-дереві
Пошук в Б-дереві схожий на пошук в двійковому дереві пошуку. Різниця в тому, що в кожному вузлі x вибирається один варіант з (n[x]+1), а не з двох. При пошуку проглядаються вузли дерева від кореня до листа. Тому число звернень до диску є O(h)=O(logtn), де h — висота дерева, а n — кількість ключів. Так як n[x]≤2t, то час обчислень дорівнює O(th)=O(t×logtn) .
Створення порожнього Б-дерева
Створення порожнього Б-дерева здійснюється за допомогою процедури, яка знаходить місце на диску для нового вузла та розміщує його. Це можна реалізувати за час O(1) і не використовувати операцію читання з диска.
Додавання елемента в Б-дерево
Додавання елемента в Б-дерево здійснюється з використанням процедури розбиття повного (з 2t-1 ключами) вузла y на два вузли, що мають по t-1 елементів у кожному. При цьому ключ-медіана key t[y] відправляється до батька x вузла y і стає роздільником двох отриманих вузлів. Це можливо, якщо вузол x не вичерпний. Якщо y — корінь, процедура працює аналогічно. В цьому випадку висота дерева збільшується на одиницю.
Процедура додавання нового елемента проходить один раз від кореня до листа, на це потрібен час O(th)=O(t×logtn) і O(h) звернень до диска, де h — висота дерева. По ходу справи поділяються повні вузли, що зустрічаються на шляху. Зауважимо, що якщо повний вузол має неповного батька, то його можна розділити, тому що в батька є місце для додаткового ключа, тому, піднімаючись вгору, доходимо до неповного листа, куди і додаємо новий елемент.
Видалення елемента
Видалення елемента з B-дерева відбувається аналогічно додаванню, хоча трохи складніше. Видалення ключа з В-дерева, хоча і аналогічно вставці, являє собою складнішу задачу. Це пов'язано з тим, що ключ може бути видалений з будь-якого вузла, а не тільки з листа, а видалення з внутрішнього вузла вимагає певної перебудови дочірніх вузлів. Як і у випадку вставки, ми повинні забезпечити, щоб при виконанні операції видалення не були порушені властивості В-дерева. Аналогічно тому, як ми мали можливість переконатися, що вузли не надто сильно заповнені для вставки нового ключа, нам належить переконатися, що вузол не стає занадто мало заповнений в процесі видалення ключа (за винятком кореневого вузла, який може мати менше t — 1 ключів, хоча і не може мати більше 2t — 1 ключів).
Отже, нехай процедура B_TREE_DELETE повинна видалити ключ k з піддереві, коренем якого є вузол x. Ця процедура розроблена таким чином, що при її рекурсивному виклику для вузла х гарантована наявність в цьому вузлі принаймні t ключів. Ця умова вимагає наявності у вузлі більшої кількості ключів, ніж мінімальна в звичайному В-дереві, так що іноді ключ може бути переміщений в дочірній вузол перед тим, як рекурсія звернеться до цього дочірньому вузлу. Таке посилення властивості В-дерева (наявність «запасного» ключа) дає нам можливість виконати видалення ключа за один спадний прохід по дереву (з єдиним винятком, який буде пояснено пізніше). Слід також врахувати, що якщо корінь дерева х стає внутрішнім вузлом, що не містить жодного ключа (така ситуація може виникнути в розглянутих нижче випадках 2в і 36), то вузол х віддаляється, а його єдиний дочірній вузол С1[х] стає новим коренем дерева (при цьому зменшується висота В-дерева і зберігається його властивість, що вимагає, щоб кореневий вузол непорожнього дерева містив як мінімум один ключ).
Замість того щоб представити вам повний псевдокод процедури видалення вузла з В-дерева, ми просто накидаємо послідовність виконуваних дій.
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. Acta Informatica 1 (3): 173–189. doi:10.1007/bf00288683.
- Comer, Douglas (June 1979). The Ubiquitous B-Tree. Computing Surveys 11 (2): 123–137. ISSN 0360-0300. doi:10.1145/356770.356776..
- 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. 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.
Див. також
- Список структур даних
- Список алгоритмів
- Двійкове дерево пошуку
- Дерева пошуку
- Збалансоване дерево
- Червоно-чорне дерево