Wahlfreier Zugriff
Unter wahlfreiem Zugriff (englisch random access, auch „direkter Zugriff“, „Direktzugriff“) wird in der Informatik die Möglichkeit verstanden, in konstanter (oder unter-linearer) Zeit einen lesenden und/oder schreibenden Speicherzugriff auf ein beliebiges Element eines Datenspeichers oder einer Datenstruktur durchführen zu können.
Wahlfreier Zugriff muss hardwareseitig durch eine (beispielsweise Bit- oder inhaltsbasierte) Adressierung unterstützt sein. Darauf aufbauend können softwareseitige Datenstrukturen das Zugriffsverhalten optimieren.
Ein Beispiel zur Veranschaulichung eines wahlfreien Zugriffs ist ein Buch, bei dem jede beliebige Seite direkt aufgeschlagen werden kann, im Gegensatz zu einer Pergamentrolle, die abgerollt werden muss und somit nur einen sequentiellen Zugriff (auch Folgezugriff) ermöglicht.
Durch die Bezeichnung Random-Access Memory (RAM) wird für diesen Speichertyp neben der allgemeinen Definition von „random access“ heutzutage meist auch die Eigenschaft als Schreib-Lese-Speicher (in diesem Fall genauer als read-write random-access memory – RWRAM bezeichnet) im Gegensatz zum Festwertspeicher (ROM, Read Only Memory) verstanden.
Datenspeicher
Beispiele für Datenspeicher mit wahlfreiem (statt sequentiellem) Zugriff in Computern sind Arbeitsspeicher, Disketten, Festplatten und USB-Speichersticks.
Ein sequentieller Zugriff ist ebenfalls möglich; er kann schneller sein (als günstiges Zugriffsmuster) als aufeinanderfolgende wahlfreie Zugriffe auf verteilte Adressen. Vergleichbar ist das mit einem Buch, bei dem man für den nächsten „Datenblock“ nur umblättert und nicht erst die nächste passende Stelle suchen muss.
Optische Speichermedien
Heute allgemein übliche Medien für optische Laufwerke sind eine Mischung. Die Musik-CD wurde als eher sequentielles Medium mit spiralförmiger Datenaufzeichnung geschaffen, bei der zu bestimmten Punkten gesprungen werden kann – den durch Zeitangaben definierten Track-Anfängen. Bei der Einführung der CD-ROM wurde der Fokus auf das direkte Ansprechen der (spiralförmig aufgezeichneten) Sektoren verschoben; ein Teil deren Bits sind zusätzliche Verwaltungsdaten. (Bei radial organisierten Festplatten und Speichern ist die interne Sektorbezeichnung durch den physischen Ort vorgegeben.)
Eine CD-R wird sequentiell beschrieben, früher durfte auch der Schreibvorgang nicht unterbrochen werden (Disc-At-Once, Track-At-Once, Session-At-Once), eine Unterbrechung des Datenstroms und damit ein Buffer-Underrun waren gefürchtet. Um als vollwertige Daten-CD in jedem Laufwerk erkannt zu werden, ist es auch nötig, das Inhaltsverzeichnis einer Session zum Schluss zu schreiben, also die CD abzuschließen. Gelesen werden kann sie dann quasi wieder im wahlfreien Zugriff.
Auch CD-RWs wurden erst sequentiell beschrieben und abgeschlossen. Sie konnten gelöscht und wieder beschrieben werden. Nachdem man nun technisch in der Lage ist, den Schreibvorgang ohne Nachteile zu unterbrechen und wieder aufzunehmen, sowie das Packet-Writing eingeführt hat, kann auch der Schreibzugriff immer wieder unterbrochen werden, und die Daten-CD bleibt gültig. Bei CD-Rs können nur Sektoren logisch als gelöscht markiert werden. Um die CDs in Laufwerken zu lesen, die diese Techniken nicht unterstützen, ist auch hier ein Abschließen erforderlich oder von vornherein eine gesamte CD zusammenzustellen. Musik-CDs sind noch immer mindestens Track-weise zu schreiben.
Ähnliches gilt für die DVD und deren Abarten. Nur die DVD-RAM hat von vornherein physisch markierte Sektoren, die sogar optisch erkennbar sind.
Datenstrukturen
In Datenstrukturen bedeutet der wahlfreie Zugriff, dass es konstante Zeitschranken für den Zugriff auf ein beliebiges Element gibt. Nur wenige Datenstrukturen wie Arrays können dies garantieren. Wahlfreier Zugriff ist entscheidend für viele Algorithmen wie Quicksort und die binäre Suche. Andere Datenstrukturen, wie Listen, opfern den wahlfreien Zugriff, um andere Operationen wie zum Beispiel das Einfügen, Löschen und Suchen einfacher durchführen zu können.
Es gibt Datenstrukturen, die Operationen wie Einfügen und Löschen stark beschleunigen gegenüber einem Array, und dabei dennoch schnellen Zugriff („Suchen“) erlauben, mit ähnlichem Aufwand wie eine binäre Suche; beispielsweise balancierte Bäume.
