Первые уровни журнала B помещаются в (одну страницу) памяти, и поэтому все, что происходит на этих уровнях, не требует ввода-вывода.(Это также устраняет проблему с анализом rrenaud, заключающуюся в том, что O (1) объединяется за вставку, поскольку вы начинаете платить за них только после первого объединения B.)
После объединения хотя бы B элементов,Факт 2 вступает в силу.
Рассмотрим работу с точки зрения элемента.Объединяется O (log N) раз.Он получает заряд O (1 / B) каждый раз, когда это происходит.Общая стоимость вставки составляет O ((log N) / B) (нужны дополнительные парены, чтобы отличаться от O (log N / B), что было бы довольно плохой производительностью вставки - даже хуже, чем у B-дерева).
«Средняя» стоимость - это действительно амортизированная стоимость - это сумма, которую вы взимаете с этого элемента за его вставку.Чуть более формально это общая работа по вставке N элементов, а затем делению на N. Амортизированная стоимость O ((log N) / B) действительно означает, что вставка N элементов - это O ((N log N) / B) I /Os - для всей последовательности.Это довольно выгодно для сравнения с B-деревьями, которые для N вставок выполняют всего O ((N log N) / log B) операций ввода-вывода.Деление на B, очевидно, намного лучше, чем деление на журнал B.
Вы можете жаловаться, что работа является комковатой, что вы иногда делаете вставку, которая вызывает большой каскад слияний.Это нормально.Вы не взимаете все слияния до последней вставки.Каждый платит свою небольшую сумму за каждое слияние, в котором он участвует. Поскольку (log N) / B, как правило, будет намного меньше 1, каждому начисляется намного меньше, чем один ввод / вывод в течение всех слияний, в которых он участвует.участвует.
Что произойдет, если вам не нравится амортизированный анализ, и вы говорите, что даже если пропускная способность увеличивается на пару порядков, вам не нравится, когда одна вставка можетвызывать огромное количество работы?Ага!Существуют стандартные способы деамортизации такой структуры данных, когда вы выполняете небольшое вытеснение во время каждой вставки.Вы получаете ту же сложность ввода / вывода (вам придется поверить на мое слово), но это довольно стандартная штука для людей, которым небезразличен амортизированный анализ и дезамортизация результата.
Полное раскрытие: яодин из авторов статьи COLA.Кроме того, Rrenaud был в моем классе алгоритмов.Кроме того, я основатель Tokutek.