Ett B-trädsindex är en balanserad träd-datastruktur som ofta används i databaser för att effektivt organisera och söka igenom stora datamängder.
B-träd liknar mycket binära sökträd (BST), men noderna i ett B-träd kan ha fler än två barn. Du kan läsa mer om BST i kursen Översikt av algoritmer och datastrukturer.

B-träd lagrar nycklar i sorterad ordning inom noderna, vilket möjliggör snabb hämtning av data genom hierarkisk traversering från roten till lövnoderna. B-trädsindexering är väl lämpad för intervallfrågor och likhetsökningar, vilket gör det till ett populärt val för att optimera databasprestanda.

Hur fungerar det?

B-trädsindex organiserar data på ett hierarkiskt sätt, där varje nod innehåller ett fast antal nycklar och pekare till barnnoder.
B-träd upprätthåller balans genom att säkerställa att alla lövnoder är på samma nivå, vilket optimerar sökoperationer.
Vid sökning efter en viss nyckel traverserar B-trädsalgoritmen trädet från roten ner till lövnoderna och använder binärsökning för att effektivt hitta önskad nyckel.

Indexuppslag innebär att traversera trädet för att nå bladnoder, följa bladnodkedjan för att hitta matchande poster och hämta den faktiska datan från disken.

I figuren visas uppslaget för nyckeln 302:

1. En sökträdstruktur är en typ av träd där varje nod har två pekare: vänster pekare pekar på barnnoder med värden mindre än föräldranoden, och höger pekare pekar på barnnoder med värden större än föräldranoden;

2. I ett B-träd kan rotknuten innehålla flera indexvärden. Om roten till exempel innehåller tre distinkta värden, kommer den att ha tre pekare, var och en som indikerar intervallet av värden mellan dessa nyckelvärden;

3. För att söka efter en nyckel, såsom 302, börjar sökningen vid rotknuten och följer de lämpliga pekarna ner till bladnoderna. Sökningen är klar efter att ha traverserat tre trädblickar, som visas i diagrammet markerat i rött;

4. För att söka efter ett intervall av värden med start från 302, kan du använda de horisontella pekarna mellan bladnoderna. Till exempel hämtas värden från 302 till 502 genom att följa bladnoderna sekventiellt.

Observera

Nyckeln som används för sökning i ett B-trädsindex kommer från värdena som lagras i de indexerade kolumnerna i databastabellen. Om till exempel indexet är på en kolumn som "client_id", kommer söknyckeln att vara de faktiska "client_id"-värdena. Varje unikt numeriskt värde i den indexerade kolumnen fungerar som en nyckel i B-trädsindexet, vilket gör det enklare att hitta och hämta motsvarande rader i databastabellen.

Fördelar och nackdelar

Till skillnad från den vanliga datastrukturen Binärt Sökträd kan B-trädnoder rymma fler än 2 barn. Det maximala antalet barn per nod är vanligtvis satt till 16.

Indeximplementering

För att skapa ett B-trädsindex på en kolumn i PostgreSQL kan du använda följande SQL-kommando:

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

Eftersom B-trädsindex är ett standardindex i SQL kan vi även använda följande sats för att skapa det:

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

Observera

I SQL, när du skapar en tabell med en primärnyckelsbegränsning, skapar de flesta databashanteringssystem automatiskt ett index på kolumnen/kolumnerna som anges i primärnyckeln. Detta index hjälper till att upprätthålla unikhetsbegränsningen för primärnyckeln och förbättrar även prestandan för frågor som involverar sökning eller join baserat på primärnyckelkolumnen/kolumnerna.