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
Part of the technical novelties 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.