Een B-tree-index is een gebalanceerde boomdatastructuur 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.

Een 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 bijzonder geschikt voor bereikqueries en gelijkheidszoekopdrachten, waardoor het een populaire keuze is voor het optimaliseren van databaseprestaties.

Hoe werkt het?

Een B-tree-index organiseert gegevens op een hiërarchische manier, waarbij elk knooppunt een vast aantal sleutels en verwijzingen naar kindknooppunten bevat.
B-trees blijven in 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 binaire zoekopdrachten worden gebruikt om de gewenste sleutel efficiënt te vinden.

Index-opzoeking omvat het doorlopen van de boom om de bladknopen te bereiken, 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 het opzoeken van 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.

Voor- en nadelen

In tegenstelling tot de standaard Binaire Zoekboom datastructuur, kunnen B-tree knooppunten meer dan 2 kinderen bevatten. Het standaard maximum aantal kinderen per knooppunt 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 aan te maken:

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