Definition

Das Modell besteht aus einem internen Speicher welcher ${\displaystyle M}$ Datenelemente fasst, sowie einem unbegrenzten externen Speicher welcher aus ${\displaystyle D}$ Festplatten besteht. Der wesentliche Performance-Indikator ist die I/O-Komplexität: die Anzahl von Zugriffen auf den externen Speicher zur Lösung eines Problems mit ${\displaystyle N}$ Datenelementen. Bei jedem Zugriff auf den externen Speicher kann von jeder der ${\displaystyle D}$ Festplatten ein Block von ${\displaystyle B}$ Datenelementen in den internen Speicher geladen werden. Analog kann vom internen in den externen Speicher geschrieben werden. Des Weiteren soll gelten ${\displaystyle M<N}$ sowie ${\displaystyle 1\leq DB\leq M/2}$.

Bei ${\displaystyle D>1}$ Festplatten müssen für eine effiziente Verarbeitung die Eingabedaten des Problems im striped (en) Format auf den ${\displaystyle D}$ Platten verteilt vorliegen (siehe die nebenstehende Abbildung für ein Beispiel). Die Ausgabe des Algorithmus soll dem gleichen Format folgen. Hierdurch können ${\displaystyle N}$ Datenelemente mit der optimalen Anzahl von ${\displaystyle \Theta (N/DB)}$ I/Os in den externen Speicher geschrieben oder von ihm gelesen werden.

Oft können die Formeln der resultierenden Anzahl von I/Os vereinfacht werden, wenn statt der oben verwendeten Größen in Anzahl von Datenelementen die jeweilige Größe in Anzahl von Blöcken verwendet werden. Hieraus ergeben sich die abgeleiteten Größen ${\displaystyle n=N/B}$ sowie ${\displaystyle m=M/B}$.

Fundamentale Operationen

Die I/O-Komplexität vieler Algorithmen wird im Wesentlichen bestimmt durch die Performance einiger fundamentaler Operationen:

1. Scanning (auch streaming oder touching) – Lesen oder schreiben von ${\displaystyle N}$ sequentiellen Datenelementen
2. Sortieren von ${\displaystyle N}$ Datenelementen (vergleichsbasiert)

Schranken für die I/O-Komplexität dieser Operationen finden sich in folgender Tabelle:

Schranken für die I/O-Komplexität fundamentaler Operationen

Operation	I/O-Schranke, D = 1	I/O-Schranke, D ≥ 1
${\displaystyle {\textit {Scan}}(N)}$	${\displaystyle \Theta (N/B)=\Theta (n)}$	${\displaystyle \Theta (N/DB)=\Theta (n/D)}$
${\displaystyle {\textit {Sort}}(N)}$	${\displaystyle \Theta (N/B\log _{M/B}N/B)=\Theta (n\log _{m}n)}$	${\displaystyle \Theta (N/DB\log _{M/B}N/B)=\Theta (n/D\log _{m}n)}$

Merge Sort

Als ein einfaches Beispiel für einen I/O-optimalen External Memory Sortieralgorithmus soll External Memory Merge Sort mit ${\displaystyle D=1}$ dienen. Dieser Algorithmus arbeitet in zwei Phasen.

Die erste Phase namens run formation erhält als Eingabe eine unsortierte Folge von Elementen im externen Speicher und erzeugt als Ausgabe ebendort eine Permutation dieser Folge, partitioniert in ${\displaystyle N/M}$ sortierte Teilfolgen der Länge ${\displaystyle M}$ (die sogenannten runs). Jede dieser Teilfolgen wird erzeugt, indem ${\displaystyle m}$ der ${\displaystyle n}$ Eingabeblöcke in den internen Speicher eingelesen, dort sortiert und anschließend wieder zurück in den externen Speicher geschrieben werden.

In der zweiten Phase des Algorithmus werden die existierenden runs rekursiv verschmolzen bis nur noch ein vollständig sortierter run existiert. Dazu werden pro Rekursionsebene jeweils ${\displaystyle m}$ runs gleichzeitig Blockweise durch den internen Speicher gestreamt, und dabei zu einem sortierten run verschmolzen. Pro Ebene werden alle Elemente je einmal gelesen und geschrieben, was ${\displaystyle 2n}$ I/Os entspricht. Nach ${\displaystyle \Theta (\log _{m}n)}$ Merge-Phasen ist nur noch ein sortierter run übrig, das Ergebnis.

Insgesamt benötigt der Algorithmus also ${\displaystyle \Theta (n\log _{m}n)}$ I/Os und ist somit optimal.