Et B-tre-indeks er en balansert tre-datastruktur 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.

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 ut de faktiske dataene fra disken.

I figuren vises oppslag etter nøkkel 302:

1. En søketrestruktur er en type tre der hver node har to pekere: venstre peker til barnenoder med verdier mindre enn foreldrenoden, og høyre 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 verdiområdet 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 fullføres 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, henting av verdier fra 302 til 502 gjøres ved å følge bladnodene sekvensielt.

Fordeler og ulemper

I motsetning til den vanlige datastrukturen Binært Søk-tre, kan B-tre-noder ha mer enn 2 barn. Det maksimale antallet barn per node er 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,..);