Index (database)

Een database-index is een structuur die tot doel heeft selecties en selectieve bewerkingen op een database te versnellen. Een index reduceert het aantal vergelijkingen dat nodig is om een of meer database-records te vinden. Zo wordt voorkomen dat een zogeheten full table scan moet worden gedaan, waarbij alle records in de tabel sequentieel moeten worden doorlopen. Een database-index is functioneel, maar niet qua structuur, vergelijkbaar met een index in een boek. Door gebruik te maken van een index in een boek hoeven immers niet alle pagina's te worden doorgelezen om een onderwerp te vinden.

Probleemstelling

Databases dienen veel gegevens te kunnen bevatten en dienen gelijktijdig door veel gebruikers en processen te kunnen worden gebruikt. Verwerkingssnelheid van een dergelijk systeem is zeer belangrijk. Selecties in ongeïndexeerde tabellen zouden per selectie of bewerking een full table scan initiëren. Dit kost per operatie onnodig veel tijd. Zo zal de snelheid van het systeem sterk verminderen indien meer gebruikers tegelijkertijd een tabel gebruiken en ook wanneer het aantal records in de tabel toeneemt. Het is soms ook een vereiste dat de waarden in een kolom uniek zijn. Bij iedere toevoeging of wijziging in de betreffende kolom dient de kolom te worden doorzocht om te controleren of de waarde niet reeds bestaat. Dit zou zonder index inhouden dat een full table scan nodig is bij ieder van deze operaties. Een full table scan is voor kleine tabellen van enkele records overigens geen probleem.

Werking

Een index bevat de waarden of afgeleiden waarden, zoals hashes, van een of meer kolommen en een verwijzing naar records of de records zelf. Dit laatste is vaak het geval voor clustered indexes, een index waarbij een kolom de fysieke volgorde van de records op het opslagmedium bepaalt. Behalve clustered indexes zijn er ook unclustered indexes. Dit zijn alle indexen die niet bepalend zijn voor de volgorde van de records zoals ze zijn opgeslagen.

Een index (in geval van een boomstructuur: op bladniveau) kan ook waarden bevatten van een record. Dit zijn covering indexes. Hierbij bestaat het record ook los van de index, maar bevat de index dus ook kopieën van kolommen van de tabel. Hierdoor hoeft het record niet meer te worden gezocht als deze via de covering index is gevonden en de opgevraagde waarden al zijn opgenomen in de index. Deze index verhoogt mits goed geconfigureerd de snelheid meer dan non-covering indexes, maar heeft wel invloed op het bijwerken van gegevens in de database-tabel. De waarden in de index moeten dan immers ook worden bijgewerkt.

Met behulp van de waarden waaruit de index bestaat kunnen de bijbehorende records worden gevonden. Indexen die uit meer kolommen bestaan kunnen meestal alleen of alleen efficiënt worden gebruikt indien wordt gezocht op al deze kolommen of de eerste kolommen uit deze index. De volgorde waarin de kolommen zijn opgenomen in de index zijn dan ook belangrijk.

Structuur

Er zijn in theorie veel manieren om een index op te bouwen, maar in de praktijk wordt meestal een boomstructuur, bijvoorbeeld een balanced tree of B+ tree, of een hashtabel of een combinatie hiervan gebruikt. De verschillende structuren hebben ieder hun eigen voor- en nadelen. Het juiste indextype en de exacte indeling van de index hangen af van verschillende factoren, zoals welke gegevens in de tabel is opgeslagen, het type ervan, het gebruik van de index en de hoeveelheid beschikbaar geheugen in het systeem.

In de meeste gevallen worden boomstructuren gebruikt als index. De grootste voordelen hiervan zijn:

• snel zoeken
• wijzigingen in de tabel vereisen meestal geen structurele bijwerking van de index, waarbij knooppunten in de boom dienen te worden aangemaakt, verwijderd, gesplitst of samengevoegd
• de index hoeft niet per se in zijn geheel in het geheugen te zijn ingeladen, maar kan in een aantal leesacties stukje voor stukje worden ingelezen, waarbij alleen de relevante delen worden ingelezen. Dit is vooral een groot voordeel bij veel records. Bij een groot aantal records zal de index namelijk ook erg groot worden. Met hedendaagse CPU-snelheden is doorgaans het aantal leesacties van het opslagmedium bepalend voor de snelheid van de index.

Hashtabellen zijn erg snel en kunnen in sommige gevallen sneller zijn dan een boom, maar hebben als nadeel dat ze veel extra geheugen verbruiken.

Nadelen

Het nadeel van indexen is dat ze geheugen en schijfruimte gebruiken. Daarnaast dienen ze te worden bijgewerkt indien records worden toegevoegd, verwijderd en bijgewerkt in de tabel. Dit laatste is doorgaans echter geen groot probleem tenzij de frequentie aan wijzigingsoperaties op een tabel erg hoog is, zoals bijvoorbeeld een tabel die de hits van webpagina's bijhoudt van een drukbezochte website. Indien dit niet het geval is zal er geen merkbaar prestatieverschil zijn voor de meeste hedendaagse database-systemen, omdat die hun indexes kunnen bijwerken op het moment dat het systeem minder zwaar wordt belast. Ook zijn de benodigde index-wijzigingen vaak klein tenzij een boomstructuur opnieuw dient te worden gerangschikt wat bij een geoptimaliseerde tabel weinig voorkomt.

Bij het aanmaken en configureren van indexes dient altijd een goede afweging te worden gemaakt tussen serverbelasting en snelheidswinst.

Zie ook

• Databasenormalisatie
• Meerdimensionale index
• Relationele database
• Sorteeralgoritme
• Soundex

Databases

databasemanagementsysteem · databasemodel · databasenormalisatie · referentiële integriteit · relationele algebra · relationele database · relationeel model

Begrippen:	database · ACID · CRUD · null · vreemde sleutel · primaire sleutel · kandidaatsleutel · axioma's van Armstrong
Objecten:	tabel · relatie · view · transactie · trigger · index · opgeslagen procedure · cursor · partitie
SQL:	Select · Insert · Update · Merge · Delete · From · Join · Union · Create · Drop · Commit · Rollback · Truncate · Alter · Where · DDL · DML · DCL
Producten:	relationele databases