Lazy B-Trees
In this paper, we bring lazy search trees to external memory.
Lazy B-trees achieve the same I/O-cost speedup over lazy search tree as B-trees do over standard binary search trees, but they retain the faster insertions and rank-adaptiveness of queries from lazy search trees. They thus smoothly interpolate between B-trees and external-memory priority queues.
Illustration of a lazy search tree (Fig 1). Lazy B-trees require a novel biased search tree
The technical novelty is an external-memory biased search tree variant for the top level of lazy search trees that uses the optimal $O(N/B)$ block of space.
Erratum
The analysis of the I/O cost of pointer-based operations does not take into account the cost of keeping pointers in the blocked-linked-list up to date.
Therefore, the use of Lazy B-Trees as external-memory priority queue with decrease-key is not currently known to be as favorable as claimed in the conference version. Specifically, for the worst case of having to maintain pointers to all elements, the I/O cost of delete-min in a straight-forward implementation increases to $O(\log N)$ I/Os.