• 1 Introduction
    • 1.1 The External-Memory Model
    • 1.2 Lazy Search Trees
    • 1.3 Related Work
    • 1.4 Contribution
  • 2 The Gap Structure: A New Restricted External Biased Search Tree
    • 2.1 Buckets by Weight and Searching by Element
    • 2.2 Updating the Weights
    • 2.3 Supporting Rank Queries
  • 3 The Interval Structure
  • 4 Lazy B-Trees
  • 5 Open Problems
  • A The Interval Structure
    • A.1 Invariants and Potential
      • A.1.1 Merging Intervals
      • A.1.2 Potential
    • A.2 Updating Elements of the Intervals
    • A.3 Splitting the Intervals
      • A.3.1 Gap i is 2-sided.
      • A.3.2 Gap i is 0-sided.
      • A.3.3 Total I/O Cost
  • B Supporting Lemmas