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 meerdere 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.

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 meerdere gebruikers tegelijkertijd een tabel gebruiken en ook wanneer het aantal records in de tabel toeneemt.

Ook is het soms 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 dan 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.

Een index bevat de waarden, of afgeleiden waarden (zoals hashes), van een of meerdere kolommen en een verwijzing naar records of de records zelf. Dit laatste is vaak het geval voor zogeheten clustered indexes: een index waarbij een kolom de fysieke volgorde van de records op het opslagmedium bepaalt. Naast 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 de snelheid meer dan non-covering indexes (mits goed geconfigureerd), 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 meerdere 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.

In theorie zijn er vele manieren om een index op te bouwen. In de praktijk wordt meestal een boomstructuur (bijvoorbeeld EEN balanced tree of B+ tree) of een hash-tabel 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 data in de tabel is opgeslagen, het type van de data, 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.

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

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.

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