D05.8. Comparison of B-tree and binary trees

[AristokratM]

D05.8. Comparison of B-tree and binary trees The benefits of B-tree? Benefits of self-balancing BST?

D05.8. Порівняння B-tree та бінарних дерев Переваги B-tree? Переваги self-balancing BST?

[AristokratM]

Переваги B-tree?

константа в оцінці O(log n) для висоти B-дерева менша, ніж для червоно-чорних дерев

всі вузли на одному рівні= ідеальна збалансованість

B-tree оптимальні для швидкого доступу до великих масивів даних на диску, так як мають дуже малу висоту, пошук у кілька кроків. Переваги self-balancing BST?

В b-tree вставка складніша

В бінарному обхід можна робити різними способами, в b-tree не можна

Всі інші обходи крім inorder працюють однаково для бінарних та n-архних дерев

Для дерев пошуку інші обходи не потрібні

[AristokratM]

Переваги B-tree?

Якщо зчитування повільне

Якщо читаємо блоками

Однакова глибина

Менше додаткових вказівників Переваги self-balancing BST?

Простіше в реалізації?

Працюють швидше в пам’ яті

[glbter]

• B-tree ідеальні для баз даних, для файлових систем, через
  • швидкий пошук
    • можливість зчитування блоками
  • теоретично, ці блоки можуть містити в собі інші структури, що пришвидшить доступ
• binary trees гарно підходять для RAM, відображення та сприйняття
  • бо вони набагато зрозуміліші (не враховуючи алгоритми балансування)

в цілому бінарні дерева можуть містити у собі підструктуру (блок даних), хоча RB дерево є частинним випадком B дерева. Тому з цієї точки зору щось із них не може бути кращим, та на практиці різниця є.

[RedBarboriska]

Можна додати, що B-tree...

• зберігають ключі в відсортованому порядку для послідовного траверса
• використовують ієрархічний індекс, щоб мінімізувати кількість операцій читання з диску
• використовують частково повні блоки для прискорення вставок і вилучень
• зберігають індекс збалансований з рекурсивним алгоритмом
• "дуже відсортовані" і за рахунок цього B-tree мають швидший пошук ніж відсортовані бінарні дерева

[khilchuk-ol]

B-дерева були розроблені для жорстких дисків, які мають великий час доступу (переміщення голівки в положення триває довго), після чого відбувається зчитування (зчитується фізичний сектор). Збільшення розмірів вузлів B дерева до розмірів такого сектора робить зчитування ефективнішим.

Порівняємо дерева, використовуючи цифри. Наприклад, можна розглянути структуру даних для зберігання 2^20 ключів по 1 слову.

Двійкове дерево пошуку матиме 2^20 вузлів, кожен з яких має один ключ та два посилання. Глибина буде log_2 (2^20) = 20. Під час пошук потрібно буде прочитати ключ і одне із посилань для кожного вузла на шляху від кореня до листочка = 40 слів.

В B-tree кожен вузол може зберігати масив з 256-512 пар ключ-подальше посилання. В середньому вузли заповнені на 3/4, тоді кожен вузол буде містити 384 записи, і його внутрішній бінарний пошук повинен буде відвідувати в середньому log_2 (384) = 5,95 ключів. Середня глибина буде log_384 (2^20) = 2,33, тому для пошуку потрібно буде прочитати в середньому 14 слів.

У випадку B-дерева з низьким коефіцієнтом розгалуження (branching factor), кожен вузол (має від 16 до 32 ключів) в середньому буде містити 24 ключі, середня глибина log_24 (2^20) = 4,36, двійковий пошук у кожному вузлі зробить log_2 (24) = 4,58 порівняння, і загальний середній пошук повинен буде прочитати близько 20 слів.

Багато нових мов і бібліотек використовують 32-ключові B-tree як вбудовану структуру даних.