Зачем нам нужна отдельная структура данных, такая как B-Tree для базы данных и файловой системы?

Я читаю B B Trees и, похоже, они выполняют операции динамического набора в O (lg n). Красное черное дерево (TreeMap в java) также выполняет такую же операцию асимптотически в тот же период времени. Поэтому я хотел бы знать, что делает деревья B более полезными для баз данных и файловых систем.

Ответ 1

Основная причина существования B-деревьев - лучше использовать поведение устройств, которые читают и записывают большие куски данных. Два свойства важны для того, чтобы B-Tree лучше, чем двоичные деревья, когда данные должны храниться на диске:

Доступ к диску очень медленный (по сравнению с памятью или кэшами, произвольный доступ к данным на диске на несколько порядков); и
Каждое отдельное чтение заставляет весь сектор загружаться с диска - при условии, что размер сектора составляет 4 КБ, это означает 1000 целых чисел или десятки некоторых более крупных объектов, которые вы храните.

Следовательно, мы можем использовать плюсы второго факта, а также минимизировать количество попыток доступа к диску.

Итак, вместо того, чтобы просто хранить один номер в каждом node, который говорит нам, следует ли нам продолжать левое или правое, мы можем создать более крупный индекс, который говорит нам, следует ли нам продолжать первый 1/100, ко второму или к 99-м (представить книги в библиотеке, отсортированные по их первой букве, затем по второй и т.д.). Пока все эти данные подходят для одного сектора, он будет загружен в любом случае, поэтому мы могли бы использовать его полностью.

Это приводит к грубому поиску журналов _b N, где N - количество записей. Это число, хотя и асимптотически такое же, как log ₂ N, на самом деле в несколько раз меньше при достаточно больших N и b - и поскольку мы говорим о хранении данных на диске для использования в базах данных и т.д., объем данных обычно достаточно велик, чтобы оправдать это.

Остальная часть дизайнерского решения в основном делается для того, чтобы сделать эту работу эффективной, так как изменение N-арного дерева сложнее двоичного.

Ответ 2

Деревья RB - это двоичные деревья поиска. Деревья B могут иметь более двух дочерних узлов. Фактически, число дочерних узлов является переменной.

Таким образом, вы можете изменить количество дочерних узлов таким образом, чтобы размер node всегда был кратным размеру блока файловой системы. Это уменьшает количество отходов при чтении: вы все равно не можете читать менее одного блока, вам всегда нужно прочитать полный блок, чтобы вы могли просто заполнить его полезными данными. Увеличение количества дочерних узлов также уменьшит глубину дерева, что уменьшит среднее число "переходов" (то есть чтение диска), что еще больше увеличивает производительность.

Помните: деревья B обычно используются для хранения структур данных, которые на порядки больше, чем память, тогда как деревья RB обычно используются для хранения структур данных, которые на порядки меньше, чем память. Фактически, деревья B специально разработаны как структура данных на диске, а не структура данных в памяти.

Это ключевое предложение из статьи в Википедии (выделено мной):

B-дерево оптимизировано для систем, которые считывают и записывают большие блоки данных

Ответ 3

Нам нужны разные алгоритмы, поскольку скорость доступа в памяти намного быстрее, чем на диске. Красное/черное дерево делает много доступа к памяти, поэтому оно хорошо работает с быстродействующей скоростью памяти. B-дерево делает меньше и больше доступа, потому что доступ к диску медленный.