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. Du kan lære mere om BST'er i Kursus i Algoritmer og Datastrukturer – Oversigt.

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 til optimering af databaseydelse.

Hvordan fungerer det?

B-tree-indeks 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-træ-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 afsluttes 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 at følge bladnoderne sekventielt.

Bemærk

Nøglen, der bruges til søgning i et B-træ-indeks, stammer fra værdierne gemt i de indekserede kolonne(r) i databasetabellen. For eksempel, hvis indekset er på en kolonne som "client_id", vil søgenøglen være de faktiske "client_id"-værdier. Hver unik numerisk værdi i den indekserede kolonne fungerer som en nøgle i B-træ-indekset, hvilket gør det lettere at finde og hente de tilsvarende rækker i databasetabellen.

Fordele og ulemper

I modsætning til den standard binære søgetræ-datastruktur kan B-træ-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-træ-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-træ-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,..);

Bemærk

I SQL, når du opretter en tabel med en primær nøglebegrænsning, opretter de fleste databasehåndteringssystemer automatisk et indeks på de kolonne(r), der er angivet i primærnøglen. Dette indeks hjælper med at håndhæve unicitetsbegrænsningen for primærnøglen og forbedrer også ydeevnen for forespørgsler, der involverer søgning eller sammenkobling baseret på primærnøglekolonne(r).