Et B-tre-indeks er en balansert trestruktur som ofte brukes i databaser for å organisere og søke gjennom store datamengder på en effektiv måte.
B-trær ligner mye på binære søketrær (BST), men nodene i et B-tre kan ha flere enn to barn. Du kan lære mer om BST-er i Kurs i algoritmer og datastrukturer: Oversikt.

B-tre lagrer nøkler i sortert rekkefølge innenfor nodene, noe som gir rask gjenfinning av data gjennom hierarkisk traversering fra roten til bladnodene. B-tre-indeksering egner seg godt for intervallspørringer og likhetssøk, og er derfor et populært valg for å optimalisere databaseytelse.

Hvordan fungerer det?

B-tre-indeks organiserer data på en hierarkisk måte, der hver node inneholder et fast antall nøkler og pekere til underordnede noder.
B-trær opprettholder balanse ved å sikre at alle bladnoder er på samme nivå, noe som optimaliserer søkeoperasjoner.
Når man søker etter en bestemt nøkkel, traverserer B-tre-algoritmen treet fra roten og ned til bladnodene, og benytter binærsøk for effektivt å finne ønsket nøkkel.

Indeksoppslag innebærer å traversere treet for å nå bladnodene, følge bladnodekjeden for å finne samsvarende poster, og hente de faktiske dataene fra disken.

I figuren vises oppslag etter nøkkel 302:

1. En søketruktur er en type tre der hver node har to pekere: venstre peker peker til barnenoder med verdier mindre enn foreldrenoden, og høyre peker peker til barnenoder med verdier større enn foreldrenoden;

2. I et B-tre kan roten inneholde flere indeksverdier. For eksempel, hvis roten inneholder tre distinkte verdier, vil den ha tre pekere, hver som indikerer området av verdier mellom disse nøkkelverdiene;

3. For å søke etter en nøkkel, som 302, starter søket i roten og følger de riktige pekerne ned til bladnodene. Søket er fullført etter å ha traversert tre treblokker, som vist i diagrammet markert med rødt;

4. For å søke etter et verdiområde som starter fra 302, kan du bruke de horisontale pekerne mellom bladnodene. For eksempel, å hente verdier fra 302 til 502 gjøres ved å følge bladnodene sekvensielt.

Merk

Nøkkelen som brukes for søk i en B-tre-indeks kommer fra verdiene lagret i de indekserte kolonnene i databasetabellen. For eksempel, hvis indeksen er på en kolonne som "client_id", vil søkenøkkelen være de faktiske "client_id"-verdiene. Hver unik numerisk verdi i den indekserte kolonnen fungerer som en nøkkel i B-tre-indeksen, noe som gjør det enklere å finne og hente de tilsvarende radene i databasetabellen.

Fordeler og ulemper

I motsetning til den vanlige datastrukturen Binært Søk-tre, kan B-tre-noder ha mer enn 2 barn. Maksimalt antall barn per node er som standard vanligvis satt til 16.

Indeksimplementering

For å opprette en B-tre-indeks på en kolonne i PostgreSQL, kan du bruke følgende SQL-kommando:

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

Siden B-tre-indeksen er en standardindeks i SQL, kan vi også bruke følgende setning for å opprette den:

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

Merk

I SQL, når du oppretter en tabell med en primærnøkkel-kontroll, vil de fleste databasesystemer automatisk opprette en indeks på kolonnen(e) som er spesifisert i primærnøkkelen. Denne indeksen hjelper til med å håndheve unikhetskravet til primærnøkkelen og forbedrer også ytelsen til spørringer som involverer søk eller sammenkobling basert på primærnøkkelkolonnen(e).