Б-дерево

Не плутати з бінарне дерево.

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

B-tree
Тип	Дерево
Винайдено	1970
Винайшли	^[en], ^[en]
Обчислювальна складність у записі великого О
	Середня	Найгірша
Простір	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 році ^[en] та ^[en].

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

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

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

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

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

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

Визначення

Згідно з визначенням Кнута, B-дерево порядку m - це дерево, яке задовольняє такі властивості:

1. Кожен вузол має щонайбільше m нащадків.
2. Кожен внутрішній вузол має принаймні ⌈m/2⌉ нащадків.
3. Кожен нелистковий вузол має принаймні двох дочірніх вузлів.
4. Усі листочки розташовані на одному рівні.
5. Нелистовий вузол з k дочірніми елементами містить k−1 ключів.

Ключі кожного внутрішнього вузла діють як значення розділення, які розділяють його піддерева.

Внутрішні вузли

Внутрішні вузли — це всі вузли за винятком листових вузлів і кореневого вузла. Зазвичай вони представлені у вигляді впорядкованого набору елементів і дочірніх покажчиків. Кожен внутрішній вузол містить максимум U нащадків і мінімум L нащадків. Таким чином, кількість елементів завжди на 1 менше, ніж кількість дочірніх покажчиків (кількість елементів знаходиться між L−1 та U−1). U має бути або 2L, або 2L−1; тому кожен внутрішній вузол заповнений принаймні наполовину. Зв’язок між U та L означає, що два напівзаповнені вузли можуть бути об’єднані, щоб скласти вузол, а один повний вузол можна розділити на два вузли (якщо є місце, щоб підштовхнути один елемент до батьківського). Ці властивості дозволяють видаляти та вставляти нові значення в Б-дерево та налаштувати дерево, щоб зберегти властивості Б-дерева.

Кореневий вузол

Кількість дочірніх елементів кореневого вузла має ту саму верхню межу, що й внутрішні вузли, але не має нижньої межі. Наприклад, якщо у всьому дереві менше ніж L-1 елементів, корінь буде єдиним вузлом у дереві, у якому взагалі немає нащадків.

Листя

Листя — це вузли, що є фактичними об’єктами даних або фрагментами. Інші автори також називають листям рівні вище цих листів.

Б-дерево глибини n+1 може містити приблизно в U разів більше елементів, ніж Б-дерево глибини n, але вартість операцій пошуку, вставки та видалення зростає з глибиною дерева. Як і в будь-якому збалансованому дереві, вартість зростає набагато повільніше, ніж кількість елементів.

Деякі збалансовані дерева зберігають значення лише в листі і використовують різні типи вузлів для листя і внутрішніх вузлів. Б-дерева зберігають значення в кожному вузлі дерева, за винятком листя.

Б-дерево

Б-деревом називають кореневе дерево, влаштоване наступним чином. Кожен вузол 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 вибирають досить великим. Число звернень до диска для більшості операцій пропорційно висоті Б-дерева.

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

${\displaystyle 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 стане медіаною нового вузла).

Примітки

1. Bayer, R.; McCreight, E. (July 1970). Organization and maintenance of large ordered indices (PDF). Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70. Boeing Scientific Research Laboratories. с. 107. doi:10.1145/1734663.1734671. S2CID 26930249.
2. Comer, 1979.

• ; (1972), (PDF), Acta Informatica, 1 (3): 173—189, doi:10.1007/bf00288683, архів оригіналу (PDF) за 10 червня 2017, процитовано 24 січня 2017
• (June 1979), The Ubiquitous B-Tree, Computing Surveys, 11 (2): 123—137, doi:10.1145/356770.356776, ISSN 0360-0300.
• Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN .
• Folk, Michael J.; Zoellick, Bill (1992), File Structures (вид. 2nd), Addison-Wesley, ISBN 
• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.). Section 6.2.4: Multiway Trees, pp. 481–491. Also, pp. 476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

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

• ; (July 1970), (PDF), т. Mathematical and Information Sciences Report No. 20, Boeing Scientific Research Laboratories, архів оригіналу (PDF) за 14 серпня 2020, процитовано 24 січня 2017.
• (1971), , Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California, архів оригіналу за 31 серпня 2015, процитовано 24 січня 2017

Див. також

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