Random access
Under random access ( English random access , also called "direct access", "random access") is used in the computer science understood the way in constant (or under-linear ) time a read and / or write memory access to any element of a data memory or a To be able to carry out data structure .
Random access must be supported on the hardware side by addressing (for example bit or content-based ) . Based on this, software-based data structures can optimize the access behavior.
An example to illustrate random access is a book in which any page can be opened directly, in contrast to a roll of parchment, which has to be unrolled and thus only allows sequential access (also subsequent access ).
The designation Random-Access Memory (RAM) for this type of memory is used nowadays, in addition to the general definition of "random access", for the property of read-write memory (in this case more precisely referred to as read-write random-access memory - RWRAM ) as opposed to read only memory (ROM).
Data storage
Examples of data storage devices with random (instead of sequential) access in computers are main memories , floppy disks , hard disks and USB memory sticks .
Sequential access is also possible; it can be faster (as a favorable access pattern ) than successive random accesses to distributed addresses. It is comparable to a book in which you only have to turn the pages for the next "data block" and do not have to look for the next suitable passage.
Optical storage media
Commonly used media for optical drives today are a mixture. The music CD was created as a rather sequential medium with spiral-shaped data recording, with which you can jump to certain points - the track beginnings defined by time information. With the introduction of the CD-ROM , the focus was shifted to the direct addressing of the (spiral recorded) sectors; part of their bits are additional management data. (In the case of radially organized hard disks and memories, the internal sector designation is determined by the physical location.)
A CD-R is written to sequentially; in the past, the writing process was not allowed to be interrupted ( disc-at-once , track-at-once , session-at-once ), an interruption in the data stream and thus a buffer underrun were feared. In order to be recognized as a full data CD in every drive, it is also necessary to write the table of contents of a session at the end, i.e. to close the CD. It can then be read again with random access.
CD-RWs were also written to and locked sequentially. They could be deleted and rewritten. Now that you are technically able to interrupt and resume the writing process without any disadvantages, as well as having introduced packet writing , write access can also be interrupted again and again and the data CD remains valid. With CD-Rs, only sectors can be logically marked as erased. In order to read the CDs in drives that do not support these technologies, you have to lock them or compile an entire CD from the start. Music CDs must still be written at least one track at a time.
The same applies to the DVD and its variants. Only the DVD-RAM has physically marked sectors from the outset, which are even optically recognizable.
Data structures
In data structures , random access means that there are constant time limits for access to any element. Few data structures such as arrays can guarantee this. Random access is critical to many algorithms such as quicksort and binary search . Other data structures, such as lists , sacrifice random access in order to make other operations such as insert, delete, and search easier to perform.
There are data structures that greatly accelerate operations such as inserting and deleting compared to an array, and yet allow fast access (“search”) with a similar effort as a binary search; for example balanced trees .