Ключова відмінність: У комп'ютерах двійкові дерева - це структури даних дерева, які зберігають дані, і дозволяють користувачеві отримувати доступ, шукати, вставляти і видаляти дані в алгоритмічний час. Різниця між деревом B і B + полягає в тому, що в B-дереві ключі і дані можуть зберігатися як у внутрішньому, так і в лівому вузлах, тоді як у дереві B + дані і ключі можуть зберігатися тільки в вузлах листа. .
Двійкові дерева є збалансованими деревами пошуку, які призначені для роботи на вторинних пристроях зберігання прямого доступу, таких як магнітні диски. Рудольф Байєр і Ед Маккрейт винайшли концепцію B-дерева.
B-дерево є узагальненим двійковим деревом пошуку, в якому будь-який вузол може мати більше двох дітей. Кожен внутрішній вузол у B-дереві містить декілька ключів. Ці ключі відокремлюють значення і далі формують під-дерева. Внутрішні вузли в B-дереві можуть мати змінні числа дочірніх вузлів, які розташовані в межах заздалегідь визначеного діапазону. У той час, коли будь-які дані вставляються або видаляються з будь-якого відповідного вузла, відбувається зміна кількості дочірніх вузлів. Для того, щоб підтримувати попередньо визначений діапазон, внутрішні вузли можуть бути з'єднані або розділені. У B-дереві дозволений діапазон дочірніх вузлів, завдяки чому повинен бути збережений попередньо визначений діапазон.
У B-дерев не потрібно часто врівноважуватися, на відміну від інших самобалансуючих дерев пошуку. Вузли цих дерев не завжди повні; отже, простір витрачається непотрібно в цих деревах, що призводить до втрати простору. Тільки нижня і верхня межі кількості дочірніх вузлів зазвичай фіксуються для конкретної реалізації. Наприклад, у 2-3-B-дереві (часто просто називається 2-3 деревом), кожен внутрішній вузол може мати тільки 2 або 3 дочірні вузли.
Крім того, B-дерево оптимізовано для систем, які читають і записують великі блоки даних. Зазвичай використовується в базах даних і файлових системах. У дереві B всі вузли зберігаються на однакових глибинах балансування від кореневих вузлів. Ці глибини поступово зростають при збільшенні кількості елементів; це призводить до того, що всі листові вузли є ще одним вузлом, далі від кореня. Крім того, B-дерева є більш вигідними в порівнянні з іншими реалізаціями щодо часу, необхідного для доступу до даних.
Дерево B + є деревом n-масивів з вузлом, який складається з великої кількості дітей на вузол. Корінь може бути листом або вузлом, що містить більше двох дітей. Дерево B + складається з кореня, внутрішніх вузлів і листя.
Дерево B + є таким же, як дерево B; Єдина відмінність полягає в тому, що в дереві В + внизу додається додатковий рівень з пов'язаними листами. Крім того, на відміну від дерева B, кожен вузол у дереві B + містить лише ключі, а не пари ключ-значення.
Крім того, коефіцієнт балансування або порядок дерева B + вимірює ємність для внутрішніх вузлів дерева, тобто кількість вузлів, які вони можуть мати. Фактична кількість дітей для вузла обмежена внутрішніми вузлами. Корінь, однак, є винятком, оскільки дозволено мати більше двох дітей. Наприклад, якщо порядок дерева B + дорівнює 7, кожен внутрішній вузол (за винятком кореня) може мати від 4 до 7 дітей; в той час як кореневий може мати від 2 до 7. Основне значення дерева B + полягає в збереженні даних для ефективного пошуку в блочно-орієнтованому контексті зберігання і, зокрема, в файлових системах.
Основне значення дерева B + полягає в збереженні та збереженні даних, щоб дані не були втрачені. Цей підхід особливо застосовується в блочно-орієнтованому контексті зберігання і в деяких окремих файлових системах. Листи, які є найнижчими індексними блоками дерева B +, часто пов'язані один з одним у зв'язаному списку; отже, це робить спроби діапазону або упорядкована ітерація через блоки простішими та ефективнішими. Крім того, коефіцієнт простору не витрачається на деревах В +. Дерево B + забезпечує ефективний формат структури даних про житло, що робить їх простими в доступі та зберіганні. Дерева B + особливо корисні як індекс системи баз даних, де дані зазвичай розташовані на диску.
Порівняння між деревом B і деревом B +:
B Дерево | B + Дерево | |
Короткий веб-опис | Дерево AB - це організаційна структура для зберігання та пошуку інформації у вигляді дерева, в якому всі кінцеві вузли знаходяться на однаковій відстані від бази, а всі нетермінальні вузли мають між n та 2 n під-дерев або покажчиків ( n - ціле число). | Дерево B + - дерево n-масиву з змінною, але часто великою кількістю дітей на вузол. Дерево B + складається з кореня, внутрішніх вузлів і листя. Корінь може бути або листом, або вузлом з двома або більше дітьми. |
Також відомий як | Збалансоване дерево. | B плюс дерево. |
Простір | O (n) | O (n) |
Пошук | O (log n) | O (log b n) |
Вставити | O (log n) | O (log b n) |
Видалити | O (log n) | O (log b n) |
Зберігання | У дереві B виконується пошук ключів і даних, що зберігаються у внутрішніх або листових вузлах. | У дереві B + дані зберігаються тільки в вузлах аркуша. |
Дані | Вузли листя трьох зберігають покажчики на записи, а не на фактичні записи. | Листові вузли дерева зберігають фактичний запис, а не покажчики до записів. |
Простір | Ці дерева відходів простору | Там дерева не витрачають місця. |
Функція листкових вузлів | У дереві B лист вузла не може зберігати за допомогою пов'язаного списку. | У дереві B + дані листового вузла впорядковуються в послідовному зв'язаному списку. |
Пошук | Тут пошук у B-дереві стає складним, оскільки дані не можуть бути знайдені у вузлі аркуша. | Тут пошук будь-яких даних у дереві B + дуже простий, оскільки всі дані знаходяться у вузлах листа. |
Пошук доступності | Тут, у дереві B, пошук не такий простий у порівнянні з деревом B +. | Тут в B + дерево пошук стає легким. |
Надлишковий ключ | Вони не зберігають надлишковий ключ пошуку. | Вони зберігають надлишковий ключ пошуку. |
Програми | Вони є більш старою версією і не є такою перевагою порівняно з B + деревами. | Багато реалізаторів системи баз даних віддають перевагу структурній простоті дерева B +. |
