10.6. Een index op een kolom; performance

Er zijn veel instellingen en bedrijven die werken met databases die bestaan uit miljoenen records.
En er zijn meestal heel veel mensen, die die database tegelijk raadplegen.
Dan is het wel belangrijk dat het niet te lang duurt voordat je iets gevonden hebt in die database.
De snelheid van verwerken noem je de performance.
Bij het opzetten van een database kun je maatregelen nemen om ervoor te zorgen dat de performance zo hoog mogelijk is.

Er zijn verschillende manieren om iets op te zoeken in een database.

Sequentieel zoeken.

Sequentieel zoeken betekent: op de rij af zoeken.
We leggen het uit aan de hand van een eenvoudig voorbeeldje.

Stel je hebt 15 getallen in een rij: 5 12 9 15 2 7 12 5 6 14 4 23 10 8 37.
En stel dat je in deze rij op zoek moet naar het getal 4.
Als je gewoon op de rij afgaat dan is het de 11-de keer raak, want het 11-de getal is 4.
Maar als je in deze rij op zoek gaat naar het getal 3, en je gaat gewoon de rij af, dan moeten er 15 getallen vergeleken worden.
En dan kom je na de 15-de keer tot de ontdekking dat het getal 3 helemaal niet voorkomt in de rij.

Nu is dat bij een aantal van 15 niet zo erg, maar als een computer in 10 miljoen records bijvoorbeeld naar een bepaald telefoonnummer moet zoeken dan kan dat wel even duren als het gewoon op de rij af gaat.

Er zijn veel handiger manieren van zoeken.
Maar dan moeten de gegevens wel gesorteerd zijn.
Bij zoeken in gesorteerde rijen moet je een zogenaamde halveringsalgoritme gebruiken. Dat wordt dan binair zoeken genoemd.

Binair zoeken

We nemen dezelfde getallen als zonet, maar nu zijn ze gesorteerd, ze staan van klein naar groot:
2 4 5 5 6 7 8 9 10 12 12 15 14 23 37.
Stel dat we weer naar het getal 4 willen zoeken.

We kijken eerst naar het achtste getal (15 / 2 = 7,5 afgerond 8)
Dat is 9. Dat is te groot, en dus moet het getal 4 ervoor zitten. We kunnen de zoektocht voortzetten in de eerste helft.
We kijken nu naar het vierde getal (8 / 2 = 4)
Dat is 5. Dat is te groot, en dus moet het getal 4 ervoor zitten. Weer is het aantal waarin we moeten zoeken gehalveerd.
We bekijken het tweede getal (4 / 2 = 2)
Dat is 4. We zijn er! En nu in drie keer.

Stel dat we ook weer naar het getal 3 willen zoeken.

We kijken eerst naar het achtste getal.
Dat is 9. Dat is te groot, en dus moet het getal 3 ervoor zitten.
We kijken nu naar het vierde getal (8 / 2 = 4)
Dat is 5. Dat is te groot, en dus moet het getal 3 ervoor zitten.
We bekijken het tweede getal (4 / 2 = 2)
Dat is 4. Dat is te groot, en dus moet het getal 3 ervoor zitten.
We bekijken het eerste getal (2 / 2 = 1)
Dat is 2. Dat is te klein, en dus moet het getal 3 erna komen, als het er is.
Het zou dus tussen het eerste en tweede getal moeten zitten, maar daar zitten geen getallen tussen en dus zit het getal 3 er niet bij.
Dat hebben we nu in 4 stappen ontdekt.

Bij deze strategie halveer je steeds het aantal overgebleven mogelijkheden.
Als je bijvoorbeeld zoekt in 1000 records begin je met record nummer 500.
Als je record nr. 500 bekeken hebt weet je of je verder moet zoeken in record 1 t/m 499 of in record 501 t/m 1000.
Je bent dus van 1000 naar 500 mogelijkheden gegaan.
Daarna moet je nog zoeken in 250 records, dan 125, dan 63, 32, 16, 8, 4, 2, 1.
Na tien pogingen ben je er zeker van of het gezochte er is of niet.
Je zou ook andersom kunnen rekenen. Beginnen aan het uiteinde (één mogelijkheid over) en steeds verdubbelen: 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024. Je krijgt dan machten van 2, en bij 2 tot de tiende zit je boven de 1000, tien records bekijken is dus genoeg.
In wiskundige termen: Het maximale aantal records dat je bekijkt is de 2-logaritme van het totaal aantal records.

Dit werkt natuurlijk alleen als de rij gesorteerd is.
Daarom wordt er in een tabel vaak verschillende sorteringen bijgehouden. Als je de tabel in beeld hebt dan kan hij maar op één manier gesorteerd zijn. Maar vaak is er een extra bestand waarin de sorteervolgorde op een ander veld is vastgelegd.
Dat wordt een index genoemd.
Een index maakt dat je snel kunt zoeken in een tabel. Maar het betekent wel dat die index moet worden bijgehouden, elke keer als er iets in de database wordt gewijzigd moet de index worden bijgewerkt.