Перегляд вихідного коду сторінки Б-дерево

{{distinguish|бінарне дерево}}
{{Infobox data structure
|name=B-tree
|type=tree
|invented_by={{Нп|Рудольф Байер|||Rudolf Bayer}}, {{Нп|Едвард МакКрейт|||Edward M. McCreight}}
|invented_year=1970<ref name="bayer-mccreight-1970">{{Cite book
|last1=Bayer|first1=R.|last2=McCreight|first2=E.
|title=Proceedings of the 1970 ACM SIGFIDET (Now SIGMOD) Workshop on Data Description, Access and Control - SIGFIDET '70|date=July 1970
|chapter=Organization and maintenance of large ordered indices
|page=107|chapter-url=https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf
|publisher=Boeing Scientific Research Laboratories
|doi=10.1145/1734663.1734671
|s2cid=26930249}}</ref>
|
|space_avg= O(''n'')
|space_worst= O(''n'')
|search_avg= O(log ''n'')
|search_worst= O(log ''n'')
|insert_avg= O(log ''n'')
|insert_worst= O(log ''n'')
|delete_avg= O(log ''n'')
|delete_worst= O(log ''n'')
}}
[[Файл:B-Baum.svg|thumb|320px|right|Зображення Б-дерева]]
'''Б-дерева''' ({{lang-en|B-tree}})&nbsp;— це [[Збалансоване дерево|збалансована деревоподібна]] структура даних, яка підтримує відсортовані дані та дозволяє здійснювати пошук, [[Послідовний доступ|послідовний доступ]], вставки та видалення в [[Часова_складність|логарифмічному часі]]. Б-дерево узагальнює [[Двійкове дерево пошуку|двійкове дерево пошуку]], допускаючи [[Вузол (інформатика)|вузли]] з більше ніж двома дочірніми елементами.{{sfn|Comer|1979}}
На відміну від інших самобалансуючих двійкових дерев пошуку, Б-дерево добре підходить для систем зберігання даних, які читають і записують відносно великі блоки даних, таких як бази даних і файлові системи. Б-дерево забезпечує ефективне збереження інформації на магнітних дисках та інших пристроях з прямим доступом. Б-дерева схожі на [[Червоно-чорне дерево|червоно-чорні]], різниця в тому, що в Б-дереві вузол може мати багато дітей, на практиці до тисячі, залежно від характеристик використовуваного диска. Завдяки цьому [[константа]] в оцінці ''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 році {{Нп|Рудольф Байер|Рудольфом Байером||Rudolf Bayer}} та {{Нп|Едвард МакКрейт|Едвардом МакКрейтом||Edward M. McCreight}}.

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

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

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

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

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

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

== Визначення ==
Згідно з визначенням [[Дональд Кнут|Кнута]], B-дерево порядку m - це дерево, яке задовольняє такі властивості:
# Кожен вузол має щонайбільше ''m'' нащадків.
# Кожен внутрішній вузол має принаймні ⌈''m''/2⌉ нащадків.
# Кожен нелистковий вузол має принаймні двох дочірніх вузлів.
# Усі листочки розташовані на одному рівні.
# Нелистовий вузол з ''k'' дочірніми елементами містить ''k''&minus;1 ключів.

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

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

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

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

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

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

;Б-дерево
: Б-деревом називають [[кореневе дерево]], влаштоване наступним чином. Кожен вузол ''x'' містить наступні поля:

* ''n[x]''&nbsp;— кількість ключів, що зберігаються у вузлі ''x'';
* ''key<sub>1</sub>[x], key<sub>2</sub>[x], … ,key<sub>n(x)</sub>[x]''&nbsp;— самі ключі в не спадаючому порядку;
* ''leaf[x]''&nbsp;— булеве значення, істинне, коли вузол ''x'' є листом.

Якщо ''x''&nbsp;— внутрішній вузол, то він містить покажчики ''c<sub>1</sub>[x], c<sub>2</sub>[x] c<sub>n(x)+1</sub>[x]'', на його дітей в кількості ''n[x]+1''.

* У листів дітей немає, і ці поля для них не визначені.
* Усі листя знаходяться на одній і тій же глибині, що дорівнює висоті дерева.
* Можлива кількість ключів, що зберігаються в одному вузлі, визначається параметром t≥2, яке називається мінімальним ступенем Б-дерева.
* Для кожного некореневого вузла ''x'' виконується нерівність ''(t-1)≤n[x]≤(2t-1)''. Таким чином, число дітей у будь-якого внутрішнього вузла (крім кореня) знаходиться в межах від ''t'' до ''2t''.
* Якщо дерево не пусте, то в корені повинен зберігатися хоча б один ключ. Вузол, який зберігає рівно ''2t-1'' ключів, буде називатися повним.

Ключі ''key<sub>i</sub>[x]'' служать границями, що розділяють значення ключів в піддеревах. Точніше,

* ''c<sub>1</sub>[x]'' посилається на піддерево, ключі в якому менше, ніж ''key<sub>1</sub>[x]'';
* ''c<sub>i</sub>[x]'' при ''i=2,3n'' посилається на піддерево, ключі в якому знаходяться в межах від ''key<sub>i-1</sub>[x]'' до ''key<sub>i</sub>[x]'';
* ''c<sub>n(x)+1</sub>[x]'' посилається на піддерево, ключі в якому більше, ніж ''key<sub>n(x)</sub>[x]''.

У випадку, коли ''t=2'', у кожного внутрішнього вузла 2, 3 або 4 нащадка, виходить так зване 2-3-4&nbsp;— дерево. Для ефективної роботи з диском на практиці t вибирають досить великим. Число звернень до диска для більшості операцій пропорційно висоті Б-дерева.

Для висоти <math>h</math> Б-дерева з <math>n</math> елементами даних:

: <math>h \leq \log_t \left({n+1 \over 2} \right)</math>

== Основні операції з Б-деревами ==

Корінь Б-дерева розміщують в [[Оперативна пам'ять|оперативній пам'яті]], при цьому читання з диска для кореня ніколи не потрібно, а проте всякий раз, коли змінюється корінь, його зберігають на диску. Усі вузли, що передаються як параметри, вже зчитані з диска. Всі [[Процедура (програмування)|процедури]] обробляють дерево за один прохід від кореня до листів.

=== Пошук в Б-дереві ===

Пошук в Б-дереві схожий на пошук в [[Двійкове дерево пошуку|двійковому дереві пошуку]]. Різниця в тому, що в кожному вузлі ''x'' вибирається один варіант з ''(n[x]+1)'', а не з двох. При пошуку проглядаються вузли дерева від кореня до листа. Тому число звернень до диску є ''O(h)=O(log<sub>t</sub>n)'', де ''h''&nbsp;— висота дерева, а ''n''&nbsp;— кількість ключів. Так як ''n[x]≤2t'', то час обчислень дорівнює ''O(th)=O(t×log<sub>t</sub>n)'' .

=== Створення порожнього Б-дерева ===

Створення порожнього Б-дерева здійснюється за допомогою процедури, яка знаходить місце на диску для нового вузла та розміщує його. Це можна реалізувати за час ''O(1)'' і не використовувати операцію читання з диска.

=== Додавання елемента в Б-дерево ===

Додавання елемента в Б-дерево здійснюється з використанням процедури розбиття повного (з ''2t-1'' ключами) вузла ''y'' на два вузли, що мають по ''t-1'' елементів у кожному. При цьому ключ-медіана ''key t[y]'' відправляється до батька ''x'' вузла ''y'' і стає роздільником двох отриманих вузлів. Це можливо, якщо вузол ''x'' не вичерпний. Якщо ''y''&nbsp;— корінь, процедура працює аналогічно. В цьому випадку висота дерева збільшується на одиницю.

Процедура додавання нового елемента проходить один раз від кореня до листа, на це потрібен час ''O(th)=O(t×log<sub>t</sub>n)'' і ''O(h)'' звернень до диска, де ''h''&nbsp;— висота дерева. По ходу справи поділяються повні вузли, що зустрічаються на шляху. Зауважимо, що якщо повний вузол має неповного батька, то його можна розділити, тому що в батька є місце для додаткового ключа, тому, піднімаючись вгору, доходимо до неповного листа, куди і додаємо новий елемент.

=== Видалення елемента ===

Видалення елемента з B-дерева відбувається аналогічно додаванню, хоча трохи складніше. Видалення ключа з В-дерева, хоча і аналогічно вставці, являє собою складнішу задачу. Це пов'язано з тим, що ключ може бути видалений з будь-якого вузла, а не тільки з листа, а видалення з внутрішнього вузла вимагає певної перебудови дочірніх вузлів. Як і у випадку вставки, ми повинні забезпечити, щоб при виконанні операції видалення не були порушені властивості В-дерева. Аналогічно тому, як ми мали можливість переконатися, що вузли не надто сильно заповнені для вставки нового ключа, нам належить переконатися, що вузол не стає занадто мало заповнений в процесі видалення ключа (за винятком кореневого вузла, який може мати менше ''t&nbsp;— 1'' ключів, хоча і не може мати більше ''2t&nbsp;— 1'' ключів).

Отже, нехай [[Процедура (програмування)|процедура]] '''B_TREE_DELETE''' повинна видалити ключ ''k'' з піддереві, коренем якого є вузол ''x''. Ця процедура розроблена таким чином, що при її [[Рекурсивні функції|рекурсивному]] виклику для вузла ''х'' гарантована наявність в цьому вузлі принаймні ''t'' ключів. Ця умова вимагає наявності у вузлі більшої кількості ключів, ніж мінімальна в звичайному В-дереві, так що іноді ключ може бути переміщений в дочірній вузол перед тим, як рекурсія звернеться до цього дочірньому вузлу. Таке посилення властивості В-дерева (наявність «запасного» ключа) дає нам можливість виконати видалення ключа за один спадний прохід по дереву (з єдиним винятком, який буде пояснено пізніше). Слід також врахувати, що якщо корінь дерева ''х'' стає внутрішнім вузлом, що не містить жодного ключа (така ситуація може виникнути в розглянутих нижче випадках 2в і 36), то вузол ''х'' віддаляється, а його єдиний дочірній вузол ''С<sub>1</sub>[х]'' стає новим коренем дерева (при цьому зменшується висота В-дерева і зберігається його властивість, що вимагає, щоб кореневий вузол непорожнього дерева містив як мінімум один ключ).<br/>

Замість того щоб представити вам повний [[псевдокод]] процедури видалення вузла з В-дерева, ми просто накидаємо послідовність виконуваних дій.

1. Якщо вузол ''k'' знаходиться у вузлі ''x'' і ''x'' є листом&nbsp;— видаляємо ''k'' з ''х''.

2. Якщо вузол ''k'' знаходиться у вузлі ''х'' і ''х'' є внутрішнім вузлом, виконуємо наступні дії:

а) Якщо дочірній по відношенню до ''х'' вузол ''у'', попередній ключу ''k'' у вузлі ''x'', містить не менше ''t'' ключів, то знаходимо до k' попередника ''k'' в піддереві, коренем якого є ''у''. Рекурсивно видаляємо k' і замінюємо ''k'' в ''х'' ключем k'. (Пошук ключа k' і видалення його можна виконати в процесі одного спадного проходу.)

б) Ситуація, [[Симетрія|симетрична]] ситуації а: якщо дочірній по відношенню до ''х'' вузол ''z'', наступний за ключем ''k'' в вузлі ''x'', містить не менше ''t'' ключів, то знаходимо k'&nbsp;— наступний за ''k'' ключ в піддереві, коренем якого є ''z''. Рекурсивно видаляємо k' і замінюємо ''k'' в ''х'' ключем k'. (Пошук ключа k' і видалення його можна виконати в процесі одного спадного проходу.)

в) У противному випадку, якщо і ''y'', і ''z'' містять по ''t&nbsp;— 1'' ключів, вносимо ''k'' і всі ключі ''z'' в ''у'' (при цьому з ''х'' видаляється ''k'' і покажчик на ''z'', а вузол ''у'' після цього містить ''2t&nbsp;— 1'' ключів), а потім звільняємо ''z'' і рекурсивно видаляємо ''k'' з ''у''.

3. Якщо ключ k відсутній у внутрішньому вузлі ''х'', знаходимо корінь ''c<sub>і</sub>[х]'' піддерева, яке повинно містити ''k'' (якщо такий ключ є в даному В-дереві). Якщо ''c<sub>і</sub>[х]'' містить тільки ''t&nbsp;— 1'' ключів, виконуємо крок 3а або
3б для того, щоб гарантувати, що далі ми переходимо в вузол, що містить як мінімум ''t'' ключів. Потім ми рекурсивно видаляємо ''k'' з піддерева з коренем ''c<sub>і</sub>[х]''.

а) Якщо ''c<sub>і</sub>[х]'' містить тільки t&nbsp;— 1 ключів, але при цьому один з її безпосередніх сусідів (під яким ми розуміємо дочірній по відношенню до ''х'' вузол, відокремлений від розглянутого рівно одним ключем-роздільником) містить як мінімум ''t'' ключів, передамо в ''c<sub>і</sub>[х]'' ключ-роздільник між даними вузлом і його безпосереднім сусідом з ''x'', на його місце помістимо крайній ключ із сусіднього вузла і перенесемо відповідний покажчик із сусіднього вузла в ''c<sub>і</sub>[х]''.

б) Якщо і ''c<sub>і</sub>[х]'' і обидва його безпосередніх сусіда містять по ''t&nbsp;— 1'' ключів, об'єднаємо ''c<sub>і</sub>[х]'' з одним з його сусідів (при цьому колишній ключ-роздільник з ''x'' стане медіаною нового вузла).

== Примітки ==
{{reflist}}
* {{Citation
 | last = Bayer
 | first = R.
 | author-link = Рудольф Байер
 | last2 = McCreight
 | first2 = E.
 | author2-link = Едвард МакКрейт
 | title = Organization and Maintenance of Large Ordered Indexes
 | journal = Acta Informatica
 | volume = 1
 | issue = 3
 | pages = 173–189
 | date = 
 | year = 1972
 | url = http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf
 | doi = 10.1007/bf00288683
 | ref = harv
 | accessdate = 24 січня 2017
 | archive-date = 10 червня 2017
 | archive-url = https://web.archive.org/web/20170610190151/http://www.minet.uni-jena.de/dbis/lehre/ws2005/dbs1/Bayer_hist.pdf
 }}
* {{Citation
 | last = Comer
 | first = Douglas
 | author-link = Дуглас Комер
 | title = The Ubiquitous B-Tree
 | journal = Computing Surveys
 | volume = 11
 | issue = 2
 | pages = 123–137
 | date = June 1979
 | issn = 0360-0300
 | url =
 | doi = 10.1145/356770.356776
 | ref = harv}}.
* {{CLRS|chapter|18. Б-дерева}}
* {{Citation
 | last =Folk
 | first =Michael J.
 | author-link =
 | last2 =Zoellick
 | first2 =Bill
 | author2-link =
 | title =File Structures
 | place =
 | publisher =Addison-Wesley
 | year =1992
 | volume =
 | edition =2nd
 | page =
 | pages =
 | url =https://archive.org/details/filestructures00folk
 | doi =
 | isbn =0-201-55713-4
 | ref =harv
 | url-access =registration
 }}
* {{TAOCP.v3}}. Section 6.2.4: Multiway Trees, pp.&nbsp;481–491. Also, pp.&nbsp;476–477 of section 6.2.3 (Balanced Trees) discusses 2-3 trees.

== Першоджерела ==
* {{Citation
 | last = Bayer
 | first = Rudolf
 | author-link = Рудольф Байер
 | last2 = McCreight
 | first2 = E.
 | author2-link = Edward M. McCreight
 | title = Organization and Maintenance of Large Ordered Indices
 | place = 
 | publisher = Boeing Scientific Research Laboratories
 | volume = Mathematical and Information Sciences Report No. 20
 | edition = 
 | page = 
 | pages = 
 | url = http://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf
 | doi = 
 | date = July 1970
 | isbn = 
 | accessdate = 24 січня 2017
 | archive-date = 14 серпня 2020
 | archive-url = https://web.archive.org/web/20200814021820/https://infolab.usc.edu/csci585/Spring2010/den_ar/indexing.pdf
 }}.
* {{Citation
 | last = Bayer
 | first = Rudolf
 | author-link = Едвард МакКрейт
 | title = Binary B-Trees for Virtual Memory
 | series = Proceedings of 1971 ACM-SIGFIDET Workshop on Data Description, Access and Control
 | year = 1971
 | pages = 
 | place = San Diego, California
 | publisher = 
 | url = http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1457&context=cstech
 | doi = 
 | accessdate = 24 січня 2017
 | archive-date = 31 серпня 2015
 | archive-url = https://web.archive.org/web/20150831180503/http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1457&context=cstech
 }}

== Див. також ==
* [[Список структур даних]]
* [[Список алгоритмів]]
* [[Двійкове дерево пошуку]]
* [[Дерева пошуку]]
* [[Збалансоване дерево]]
* [[Червоно-чорне дерево]]

{{Перекласти|en|B-tree}}
{{Compu-stub}}

{{Дерева (інформатика)}}

[[Категорія:B-дерево|*]]
[[Категорія:З'явилися 1971]]
[[Категорія:Підходи до індексування баз даних]]