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