Optimalisatie

Inleiding

Ieder bestand op een computer is opgebouwd uit één lange reeks bytes (tekens). Een bestand kan vanaf een bepaalde positie gelezen worden, maar kan dat alleen wanneer die positie is opgegeven in bytes (Seek-opdracht).

Een database tabel vormt hierop geen uitzondering, maar heeft een belangrijke eigenschap waarmee het eenvoudig is de positie van een rij te bepalen:
Iedere rij in een database tabel heeft exact dezelfde breedte.
De positie van de de N^de rij is gelijk aan de breedte van de rij, keer N. Indices zijn op dit gegeven gebaseerd.

Een index is een extra, maar kleine, tabel die is opgebouwd uit zoekwaarden en de bijbehorende rijnummers (1^e, 2^e, 3^e,…). De index is bijzonder geraffineerd georganiseerd en de orde grootte van het aantal zoekakties is meestal logaritmisch (²log). De formule om te bepalen hoeveel zoekacties nodig zijn is databasesysteem-afhankelijk. Een voorbeeld van zo'n formule staat hiernaast.

Zoeken zonder index

Stel een database omvat 10.000 rijen. Wanneer geen index gebruikt wordt is er maar één mogelijkheid om een rij op te zoeken: Iedere rij doorlopen.

Gemiddeld is moet de halve tabel (5.000 rijen in het voorbeeld) worden doorlopen (soms is het de eerste, soms de laatste).
Een computer heeft ongeveer 10 milliseconden nodig om een rij op te zoeken.
Een zoekopdracht vraagt gemiddeld 5000 * 10 milliseconden = 50 seconden (100 seconden maximaal).

Zoeken met index

Gebruik makend van de index zijn in het voorbeeld niet meer dan 10 indexrijen nodig om te bepalen wat de plaats is van de gezochte rij.

Gelezen worden 10 rijen uit de index + 1 met de werkelijke gegevens uit de filmtabel.
Een zoekopdracht vraagt maximaal 11 * 10 milliseconden = 0.11 seconden. Dat is 910 keer sneller dan de maximum zoektijd zonder index.

Join

Bij een Join tussen twee tabellen worden de volgende leesacties uitgevoerd:

Via de index voor de eerste tabel wordt bepaald welk record uit de eerste tabel moet worden gelezen.
Het bijbehorende record wordt gelezen uit de eerste tabel. Dit record bevat de verwijzing naar de tweede tabel.
Via de index van de tweede tabel wordt bepaald welk record uit de tweede tabel moet worden gelezen.
Het bijbehorende record wordt gelezen uit de tweede tabel.

Indices definiëren

Indices worden altijd toegevoegd voor:

De kolom die de identificatie van de rij bevat.
Kolommen:
- Met waarden waarop regelmatig gezocht wordt.
- Die worden gebruikt in sorteervolgorden.
Kolommen die verwijzen naar andere tabellen.