Цель b-дерева - минимизировать количество обращений к диску. Если размер кластера файловой системы равен 4 КБ, то идеальный размер для узлов - 4 КБ. Кроме того, узлы должны быть правильно выровнены. Неверно выровненный узел приведет к считыванию двух кластеров, что снизит производительность.
При использовании схемы хранения на основе журнала выбор размера узла 4 КБ, вероятно, является наихудшим выбором, если в журнале не созданы пробелы для улучшения выравнивания. В противном случае 99,98% времени один узел хранится в двух кластерах. При размере узла 2 К шансы на это составляют чуть менее 50%. Однако существует проблема с небольшим размером узла: средняя высота b-дерева увеличивается, а время, затраченное на чтение дискового кластера, используется не полностью.
Большие размеры узлов уменьшают высоту дерева, но они также увеличивают количество обращений к диску. Большие узлы также увеличивают издержки на поддержание записей в узле. Представьте себе b-дерево, в котором размер узла достаточно велик для инкапсуляции всей базы данных. Вам нужно встроить лучшую структуру данных в сам узел, возможно, в другое b-дерево?
Я потратил некоторое время на создание прототипа реализации b-дерева в формате журнала, доступном только для добавления, и в итоге полностью отверг эту концепцию. Чтобы компенсировать потери производительности из-за смещения узла / кластера, вам необходимо иметь очень большой кэш. Более традиционный подход к хранению может лучше использовать оперативную память.
Последний удар произошел, когда я оценил производительность случайно упорядоченных вставок. Это убивает производительность любой дисковой системы хранения, но основанные на журналах форматы страдают гораздо больше. Запись даже самой маленькой записи вынуждает записывать несколько узлов в журнал, а внутренние узлы становятся недействительными вскоре после записи. В результате бревно быстро заполняется мусором.
BerkeleyDB-JE (BDB-JE) также основан на журнале, и я также изучил его характеристики производительности. У него та же проблема, что и у моего прототипа - быстрое накопление мусора. BDB-JE имеет несколько «чистых» потоков, которые повторно добавляют выжившие записи в журнал, но случайный порядок сохраняется. В результате новые «чистые» записи уже создали файлы журналов, заполненные мусором. Общая производительность системы снижается до такой степени, что единственное, что работает, - это чище, и оно забирает все системные ресурсы.
Форматы на основе журналов очень привлекательны, поскольку можно быстро создать надежную базу данных. Ахиллесова пята - чистящее средство, которое нетривиально. Стратегии кеширования также сложно понять правильно.