Зміст

• Порівняльна діаграма
• Визначення B-дерева
• Властивості B-дерева порядку М
• Визначення бінарного дерева
• Техніка обходу
• Висновок

B-дерево та Бінарне дерево - це типи нелінійної структури даних. Хоча терміни здаються схожими, але різні в усіх аспектах. Бінарне дерево використовується, коли записи або дані зберігаються в оперативній пам'яті замість диска, оскільки швидкість доступу оперативної пам’яті набагато вище, ніж на диску. З іншого боку, B-дерево використовується, коли дані зберігаються на диску, воно скорочує час доступу за рахунок зменшення висоти дерева та збільшення гілок у вузлі.

Ще одна відмінність між B-деревом і бінарним деревом полягає в тому, що B-дерево повинно мати всі його дочірні вузли на одному рівні, тоді як бінарне дерево не має таких обмежень. Бінарне дерево може мати максимум 2 підкресли або вузли, тоді як у B-дереві може бути M ні підтрубків, ні вузлів, де M - порядок B-дерева.

1. Порівняльна діаграма
2. Визначення
3. Ключові відмінності
4. Висновок

Порівняльна діаграма

Основа для порівняння	Б-дерево	Двійкове дерево
Суттєве обмеження	Вузол може мати максимум M кількість дочірніх вузлів (де M - порядок дерева).	Вузол може мати максимум 2 підпункти.
Б / в	Він використовується, коли дані зберігаються на диску.	Він використовується, коли записи та дані зберігаються в оперативній пам'яті.
Висота дерева	журналМ N (де m - порядок дерева M-шляху)	журнал2 N
Застосування	Структура даних індексації коду у багатьох СУБД.	Оптимізація коду, кодування Хаффмана тощо.

Визначення B-дерева

Дерево B - це збалансоване дерево M-шляху і також відоме як дерево збалансованого сортування. Він схожий з двійковим деревом пошуку, де вузли впорядковані на основі прохідного переходу. Просторова складність B-дерева становить O (n). Час складності вставки та вилучення становить O (log n).

Існують певні умови, які повинні відповідати дереву B:

• Висота дерева повинна лежати якомога менше.
• Над листям дерева не повинно бути порожніх підкреслив.
• Листя дерева повинні виходити на одному рівні.
• У всіх вузлах має бути найменша кількість дітей, крім залишків.

Властивості B-дерева порядку М

• Кожен вузол може мати максимальну кількість M дітей та мінімальну кількість M / 2 дітей або будь-яке число від 2 до максимального.
• Кожен вузол має на одну клавішу менше, ніж у дітей з максимальним клавішем M-1.
• Розташування клавіш здійснюється в певному порядку в межах вузлів. Усі клавіші піддерева, що знаходяться зліва від клавіші, є попередниками ключа, а ті, що знаходяться праворуч від ключа, називаються наступниками.
• Під час вставки повного вузла дерево розбивається на дві частини, а ключ із середнім значенням вставляється у батьківський вузол.
• Операція злиття відбувається при видаленні вузлів.

Визначення бінарного дерева

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

Існують певні варіанти двійкового дерева, такі як суворо бінарне дерево, повне бінарне дерево, розширене бінарне дерево тощо.

• Суворо бінарне дерево - це дерево, де кожен нетермінальний вузол повинен мати ліве піддерево і праве піддерево.
• Дерево називається повним бінарним деревом, коли воно задовольняє умові наявності 2 ⁱ вузли на кожному рівні, де i - рівень.
• Нитковий бінарний - це двійкове дерево, яке складається або з 0 без вузлів, або з 2 числа вузлів.

Техніка обходу

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

• Порядок - У цьому обході дерева ліве піддерево відвідується рекурсивно, потім відвідується кореневий вузол, а в останньому правому піддереві.
• Preorer - У цьому дереві обхід кореневого вузла спочатку відвідується лівим піддеревом і, нарешті, правим піддеревом.
• Порядок замовлення. Ця методика відвідує ліве піддерево, потім праве піддерево та нарешті кореневий вузол.

1. У B-дереві максимальна кількість дочірніх вузлів, які може мати нетермінальний вузол, є M, де M - порядок B-дерева. З іншого боку, бінарне дерево може мати не більше двох підрядів або дочірніх вузлів.
2. B-дерево використовується, коли дані зберігаються на диску, тоді як двійкове дерево використовується, коли дані зберігаються у швидкій пам'яті, як оперативна пам'ять.
3. Інша область застосування для B-дерева - це структура даних про індексацію коду в СУБД, на відміну від цього, Бінарне дерево використовується в оптимізації коду, кодування Хаффмана тощо.
4. Максимальна висота дерева B - це журнал_МN (M - порядок дерева). На противагу, максимальна висота бінарного дерева - це журнал₂N (N - кількість вузлів, а основа - 2, тому що це для двійкових).

Висновок

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