Іншою відмінністю між B-деревом і бінарним деревом є те, що B-дерево повинно мати всі свої дочірні вузли на одному рівні, тоді як бінарне дерево не має такого обмеження. Бінарне дерево може мати максимум 2 піддерева або вузли, тоді як у B-дереві може бути M без піддерев або вузлів, де M - порядок дерева B.
Діаграма порівняння
| Основа для порівняння | B-дерево | Двійкове дерево |
|---|---|---|
| Істотні обмеження | Вузол може мати максимум М число дочірніх вузлів (де М - порядок дерева). | Вузол може мати максимум 2 кількість піддерев. |
| Використовується | Він використовується, коли дані зберігаються на диску. | Він використовується, коли записи та дані зберігаються в оперативній пам'яті. |
| Висота дерева | log M N (де m - порядок дерева M-way) | log 2 N |
| Застосування | Структура даних індексування коду в багатьох СУБД. | Оптимізація коду, кодування Хаффмана тощо. |
Визначення B-дерева
B-дерево є збалансованим деревом M-way, також відомим як дерево збалансованого сортування. Він подібний до бінарного дерева пошуку, де вузли організовані на основі обходу. Просторова складність B-дерева - це O (n). Час складності введення і видалення становить O (log n).
Існують певні умови, які повинні відповідати для B-дерева:
- Висота дерева повинна бути максимально мінімальною.
- Над листям дерева не повинно бути жодних порожніх піддерев.
- Листя дерева повинні прийти на один рівень.
- У всіх вузлах має бути найменша кількість дітей, за винятком залишення вузлів.
Властивості B-дерева порядку М
- Кожен вузол може мати максимальне число М дітей і мінімальне число дітей М / 2 або будь-яке число від 2 до максимуму.
- Кожен вузол має один ключ менше, ніж діти з максимальними ключами M-1.
- Розташування ключів знаходиться в певному порядку в межах вузлів. Всі клавіші в піддереві, присутній в лівій частині ключа, є попередниками ключа, і що присутні в правій частині ключа називаються наступниками.
- Під час вставки повного вузла дерево розбивається на дві частини, а ключ із значенням медіани вставляється в батьківський вузол.
- Операція злиття відбувається, коли вузли видаляються.
Визначення двійкового дерева
Двійкове дерево - це деревоподібна структура, яка може мати не більше двох покажчиків для своїх дочірніх вузлів. Це означає, що найвищий ступінь, який може мати вузол, дорівнює 2, і може бути нуль або один ступінь.
Існують певні варіанти бінарного дерева, такі як строго бінарне дерево, повне бінарне дерево, розширене двійкове дерево і т.д.
- Строго бінарне дерево - дерево, в якому кожен нетермінальний вузол повинен мати ліве піддерево і правий піддерево.
- Дерево називається повним двійковим деревом, якщо воно задовольняє умові наявності 2 i вузлів на кожному рівні, де i - рівень.
- Різьбовий двійковий файл - це двійкове дерево, яке складається з 0 або 2 вузлів.
Техніка обходу
Обхід дерев є однією з найбільш частих операцій, що виконується на деревній структурі даних, в якій кожен вузол систематично відвідується точно один раз.
- Inorder- У цьому обході дерева ліве піддерево відвідується рекурсивно, після чого відвідається кореневий вузол, а в останньому правому піддереві відвідано.
- Preorer- У цьому обході дерева кореневий вузол відвідується спочатку потім лівим піддеревом і, нарешті, правим піддеревом.
- Postorder - Ця методика відвідує ліве піддерево, а потім правий піддерев і останній кореневий вузол.
Ключові відмінності між B-деревом і двійковим деревом
- У B-дереві максимальна кількість дочірніх вузлів, які може мати нетерміновий вузол, - M, де M - порядок дерева B. З іншого боку, бінарне дерево може мати не більше двох піддерев або дочірніх вузлів.
- B-дерево використовується, коли дані зберігаються на диску, тоді як бінарне дерево використовується, коли дані зберігаються в швидкій пам'яті, такі як оперативна пам'ять.
- Ще однією областю застосування для B-дерева є структура даних індексування коду в СУБД, навпаки, бінарне дерево використовується в оптимізації коду, кодування huffman і т.д.
- Максимальна висота B-дерева - це log M N (M - порядок дерева). На відміну від цього, максимальна висота бінарного дерева - log 2 N (N - кількість вузлів, а база - 2, тому що це для двійкового).
Висновок
B-дерево використовується над двійковим і двійковим деревом пошуку, головною причиною цього є ієрархія пам'яті, в якій CPU підключений до кешу з каналами високої пропускної здатності, а CPU підключений до диска через канал низької пропускної здатності. Двійкове дерево використовується, коли записи зберігаються в оперативній пам'яті (малі і швидкі), а B-дерево використовується, коли записи зберігаються на диску (великому і повільному). Таким чином, використання B-дерева замість бінарного дерева значно скорочує час доступу через високий коефіцієнт розгалуженості і зменшення висоти дерева.
