Een B-tree-index is een gebalanceerde boom datastructuur die veel wordt gebruikt in databases om grote hoeveelheden gegevens efficiënt te organiseren en te doorzoeken.
B-trees lijken sterk op binaire zoekbomen (BST), maar de knooppunten in een B-tree kunnen meer dan twee kinderen hebben. Meer informatie over BST's is te vinden in de Overzicht van Algoritmen en Datastructuren cursus.

B-tree slaat sleutels op in gesorteerde volgorde binnen knooppunten, waardoor snelle gegevensopvraging mogelijk is via hiërarchische traversering van de wortel naar de bladknooppunten. B-tree-indexering is zeer geschikt voor bereikvragen en gelijkheidszoekopdrachten, waardoor het een populaire keuze is voor het optimaliseren van databaseprestaties.

Hoe werkt het?

B-tree-index organiseert gegevens op een hiërarchische manier, waarbij elk knooppunt een vast aantal sleutels en verwijzingen naar kindknooppunten bevat.
B-trees behouden balans door ervoor te zorgen dat alle bladknooppunten zich op hetzelfde niveau bevinden, wat zoekbewerkingen optimaliseert.
Bij het zoeken naar een bepaalde sleutel doorloopt het B-tree-algoritme de boom van het wortelknooppunt naar de bladknooppunten, waarbij gebruik wordt gemaakt van binaire zoekopdrachten om de gewenste sleutel efficiënt te vinden.

Index-opzoeking omvat het doorlopen van de boomstructuur naar de bladknopen, het volgen van de keten van bladknopen om overeenkomende records te vinden, en het ophalen van de daadwerkelijke gegevens van de schijf.

In de afbeelding wordt de opzoeking voor sleutel 302 weergegeven:

1. Een zoekboomstructuur is een type boom waarbij elke knoop twee verwijzingen heeft: de linker verwijzing wijst naar kindknopen met waarden kleiner dan de ouderknoop, en de rechter verwijzing wijst naar kindknopen met waarden groter dan de ouderknoop;

2. In een B-tree kan de wortelknoop meerdere indexwaarden bevatten. Bijvoorbeeld, als de wortel drie verschillende waarden bevat, heeft deze drie verwijzingen, die elk het bereik van waarden tussen die sleutelwaarden aangeven;

3. Om naar een sleutel te zoeken, zoals 302, begint de zoekopdracht bij de wortelknoop en volgt de juiste verwijzingen naar de bladknopen. De zoekopdracht is voltooid na het doorlopen van drie boomblokken, zoals weergegeven in het diagram gemarkeerd in rood;

4. Om naar een bereik van waarden te zoeken vanaf 302, kun je de horizontale verwijzingen tussen de bladknopen gebruiken. Bijvoorbeeld, het ophalen van waarden van 302 tot 502 gebeurt door de bladknopen opeenvolgend te volgen.

Opmerking

De sleutel die wordt gebruikt voor het zoeken in een B-tree-index is afkomstig van de waarden die zijn opgeslagen in de geïndexeerde kolom(men) van de databasetabel. Bijvoorbeeld, als de index op een kolom zoals "client_id" staat, zal de zoekopdracht gebruikmaken van de daadwerkelijke "client_id"-waarden. Elke unieke numerieke waarde in de geïndexeerde kolom fungeert als een sleutel in de B-tree-index, waardoor het eenvoudiger wordt om de bijbehorende rijen in de databasetabel te vinden en op te halen.

Voor- en nadelen

In tegenstelling tot de standaard binaire zoekboom datastructuur kunnen B-tree-knopen meer dan 2 kinderen bevatten. Het standaard maximum aantal kinderen per knoop is doorgaans ingesteld op 16.

Indeximplementatie

Om een B-tree-index op een kolom in PostgreSQL te maken, kun je het volgende SQL-commando gebruiken:

CREATE INDEX index_name ON table_name USING BTREE (column_name1, column_name2,...);

Aangezien de B-tree-index een standaardindex is in SQL, kunnen we ook de volgende instructie gebruiken om deze te maken:

CREATE INDEX index_name ON table_name(column_name1, column_name2,..);

Opmerking

In SQL, wanneer je een tabel maakt met een primary key constraint, maken de meeste databasebeheersystemen automatisch een index aan op de kolom(men) die in de primary key zijn gespecificeerd. Deze index helpt bij het afdwingen van de uniekheidsbeperking van de primary key en verbetert tevens de prestaties van zoekopdrachten of joins die gebaseerd zijn op de primary key-kolom(men).