Unit 7: External Memory

This unit covers:

• external-memory basics: sorting, lists, B-trees
• buffer trees
• cache-oblivious model

Material

• slides

• lecture notes

• Animationen:
  • vEB Layout
  • vEB Layout Analysis
  • File-maintenance data structure
     
• Video 7-1 (2026-07-06): External memory model, external sorting

• Video 7-2 (2026-07-07): Basic External Memory Data Structures

• Video 7-3 (2026-07-07): Basic External Memory Data Structures

• Video 7-4 (2026-07-07): Cache-oblivious B-trees, vEB layout, file-maintenance

Further sources

The presentation is my own, but takes inspiration from

• Pagh: External Memory Data Structures (chapter)
• Demaine: Cache-Oblivious Algorithms and Data Structures (summer school lecture notes)

---

Unit 6  ⋅  Syllabus