Б-дерево — Вікіпедія

Б-дерева (англ. 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;
• 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 стане медіаною нового вузла).

• Bayer, R.; McCreight, E. (1972), Organization and Maintenance of Large Ordered Indexes (PDF), Acta Informatica, 1 (3): 173—189, doi:10.1007/bf00288683, архів оригіналу (PDF) за 10 червня 2017, процитовано 24 січня 2017
• Comer, Douglas (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 0-262-03384-4.
• Folk, Michael J.; Zoellick, Bill (1992), File Structures (вид. 2nd), Addison-Wesley, ISBN 0-201-55713-4
• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — 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, архів оригіналу (PDF) за 14 серпня 2020, процитовано 24 січня 2017.
• Bayer, Rudolf (1971), Binary B-Trees for Virtual Memory, Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control, San Diego, California, архів оригіналу за 31 серпня 2015, процитовано 24 січня 2017

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

В іншому мовному розділі є повніша стаття B-tree(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. Дивитись автоперекладену версію статті з мови «англійська». Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії! Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії. Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті. Докладні рекомендації: див. Вікіпедія:Переклад.

Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її.