Opslaan en terughalen

Opslaan en terughalen

Opslaan en terughalen zijn twee verschillende processen, die wel een direct verband hebben. Je kunt, na het opslaan van de informatie, deze op allerlei manieren organiseren, om het terughalen efficiënter te maken. Denk bijvoorbeeld aan sorteren, het gebruik van hashing, of het gebruik van speciale boomstructuren.

De organisatie bij het opslaan kan afwijken van het terughalen. Je kunt informatie langs verschillende manieren terughalen, bijvoorbeeld door gebruik te maken van verschillende “keys”.

Adresseren

Een adres stelt ons in staat om een gegeven (vorm) op te slaan en terug te halen zonder te zoeken. De toegangstijd (vertraging) is constant (O(1)), en niet afhankelijk van het aantal gegevens in het geheugen, of van het gegeven dat we opslaan of terughalen. We spreken dan ook wel over Random Access.

• geheugen-ic
• primair geheugen
• secondair geheugen (harde schijf, SSD)
• programma: array; pointer
• file systeem (filenaam, padnaam)
• database: index

Opmerking: op het fysische niveau speelt de omvang van het geheugen (of van de schijf) wel een rol: hoe groter het geheugen, des te groter de vertraging. Dit heeft te maken met twee effecten: voor een groter geheugen heb je te maken met langere verbindingen; en, snelle geheugens zijn veel duurder (chip-oppervlak, energie-verbruik). In de praktijk heb je daarom te maken met een geheugen-hiërarchie: een reeks stappen van zeer snelle registers naar bulk-geheugen. Bij moderne processoren hebben we een aantal niveau's van caching. Een dergelijke caching werkt alleen als we het geheugen op een bepaalde manier gebruiken: locality of reference is essentieel voor het voordeel van caching.

Ook bij het transporteren hebben we te maken met adressen. Deze worden gebruikt bij routering. Ook hier geldt dat we dankzij een adres niet hoeven te zoeken. De vertraging is wel afhankelijk van de omvang van het netwerk.

Absolute adressen

Een absoluut adres is onafhankelijk van de context.

Relatieve adressen

Een relatief adres is afhankelijk van de context.

Indirectie

Een adres kan verwijzen naar een adres, in plaats van naar het eigenlijke gegeven dat we zoeken. In zo'n geval is er sprake van indirectie.

Zoeken

Zoeken in een gesloten verzameling

Een voorbeeld van een gesloten verzameling is het filesysteem op je harde schijf: je weet precies welke bestanden hierin horen, en welke niet. Als je een bestand zoekt op je harde schijf, en je vindt het niet, dan weet je zeker dat het bestand er niet is.

Zoeken in een open verzameling

Een voorbeeld van een open verzameling is het web: je weet niet precies welke bestanden hiertoe behoren, en je weet vrijwel zeker dat je het niet volledig kunt doorzoeken. (Google loopt altijd wat achter bij het indiceren van het web.)

Als je in het web zoekt naar bepaalde informatie, en je vindt deze niet, dan betekent dat niet dat deze informatie er niet is.