Et B-tree-indeks er en balanceret trædatastruktur, der ofte anvendes i databaser til effektiv organisering og søgning i store datamængder.
B-træer minder meget om binære søgetræer (BST), men noderne i et B-træ kan have mere end to børn.

B-træet gemmer nøgler i sorteret rækkefølge inden for noderne, hvilket muliggør hurtig datahentning gennem hierarkisk gennemgang fra roden til bladnoderne. B-tree-indeksering egner sig godt til intervalforespørgsler og lighedssøgninger, hvilket gør det til et populært valg for optimering af databaseydelse.

Hvordan fungerer det?

B-tree-indekset organiserer data på en hierarkisk måde, hvor hver node indeholder et fast antal nøgler og pegere til underordnede noder.
B-træer opretholder balance ved at sikre, at alle bladnoder er på samme niveau, hvilket optimerer søgeoperationer.
Når der søges efter en bestemt nøgle, gennemløber B-tree-algoritmen træet fra rodnoden ned til bladnoderne og anvender binær søgning for effektivt at finde den ønskede nøgle.

Indekssøgning indebærer at traversere træet for at nå bladnoderne, følge bladnodekæden for at finde matchende poster og hente de faktiske data fra disken.

I figuren vises opslaget efter nøgle 302:

1. En søgetræstruktur er en type træ, hvor hver node har to pegepinde: venstre pegepind peger på underordnede noder med værdier mindre end forældrenoden, og højre pegepind peger på underordnede noder med værdier større end forældrenoden;

2. I et B-træ kan rodnoden indeholde flere indeksværdier. For eksempel, hvis roden indeholder tre forskellige værdier, vil den have tre pegepinde, som hver angiver intervallet af værdier mellem disse nøgleværdier;

3. For at søge efter en nøgle, såsom 302, starter søgningen ved rodnoden og følger de relevante pegepinde ned til bladnoderne. Søgningen er fuldført efter at have traverseret tre træblokke, som vist i diagrammet markeret med rødt;

4. For at søge efter et interval af værdier startende fra 302, kan du bruge de horisontale pegepinde mellem bladnoderne. For eksempel hentes værdier fra 302 til 502 ved sekventielt at følge bladnoderne.

Fordele og ulemper

I modsætning til den standard Binary Search Tree-datastruktur kan B-tree noder rumme mere end 2 børn. Det maksimale antal børn pr. node er som standard typisk sat til 16.

Indeksimplementering

For at oprette et B-tree-indeks på en kolonne i PostgreSQL kan du bruge følgende SQL-kommando:

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

Da B-tree-indekset er et standardindeks i SQL, kan vi også bruge følgende erklæring til at oprette det:

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