Б-дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
B-tree
Тип Дерево
Винайдено 1970[1]
Винайшли Рудольф Байер[en], Едвард МакКрейт[en]
Обчислювальна складність
у записі великого О
Середня Найгірша
Простір O(n) O(n)
Пошук O(log n) O(log n)
Вставляння O(log n) O(log n)
Видалення O(log n) O(log n)
Зображення Б-дерева

Б-дерева (англ. B-tree) — це збалансована деревоподібна структура даних, яка підтримує відсортовані дані та дозволяє здійснювати пошук, послідовний доступ, вставки та видалення в логарифмічному часі. Б-дерево узагальнює двійкове дерево пошуку, допускаючи вузли з більше ніж двома дочірніми елементами.[2] На відміну від інших самобалансуючих двійкових дерев пошуку, Б-дерево добре підходить для систем зберігання даних, які читають і записують відносно великі блоки даних, таких як бази даних і файлові системи. Б-дерево забезпечує ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на червоно-чорні, різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому константа в оцінці 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 році Рудольфом Байером[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;
  • 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 стане медіаною нового вузла).

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

  1. Bayer, R.; McCreight, E. (July 1970). Organization and maintenance of large ordered indices. 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.

Першоджерела[ред. | ред. код]

Див. також[ред. | ред. код]