Loading AI tools
З Вікіпедії, вільної енциклопедії
Б-дерева (англ. 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 - це дерево, яке задовольняє такі властивості:
Ключі кожного внутрішнього вузла діють як значення розділення, які розділяють його піддерева.
Б-дерево глибини n+1 може містити приблизно в U разів більше елементів, ніж Б-дерево глибини n, але вартість операцій пошуку, вставки та видалення зростає з глибиною дерева. Як і в будь-якому збалансованому дереві, вартість зростає набагато повільніше, ніж кількість елементів.
Деякі збалансовані дерева зберігають значення лише в листі і використовують різні типи вузлів для листя і внутрішніх вузлів. Б-дерева зберігають значення в кожному вузлі дерева, за винятком листя.
Якщо x — внутрішній вузол, то він містить покажчики c1[x], c2[x] cn(x)+1[x], на його дітей в кількості n[x]+1.
Ключі keyi[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 стане медіаною нового вузла).
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
