B-puuindeksi on tasapainotettu puutietorakenne, jota käytetään yleisesti tietokannoissa suurten tietomäärien tehokkaaseen järjestämiseen ja hakemiseen.
B-puut muistuttavat hyvin paljon binäärihakupuita (BST), mutta B-puun solmulla voi olla useampi kuin kaksi lasta.

B-puu tallentaa avaimet lajiteltuun järjestykseen solmuihin, mikä mahdollistaa nopean tiedon haun hierarkkisen kulun kautta juurisolmusta lehtisolmuihin. B-puuindeksointi soveltuu erityisen hyvin aluekyselyihin ja yhtäsuuruushakuihin, minkä vuoksi se on suosittu valinta tietokantojen suorituskyvyn optimointiin.

Miten se toimii?

B-puuindeksi järjestää tiedot hierarkkisella tavalla, jossa jokainen solmu sisältää kiinteän määrän avaimia ja osoittimia lapsisolmuihin.
B-puut säilyttävät tasapainon varmistamalla, että kaikki lehtisolmut ovat samalla tasolla, mikä optimoi hakutoiminnot.
Kun tiettyä avainta haetaan, B-puun algoritmi kulkee puuta pitkin juurisolmusta lehtisolmuihin hyödyntäen binäärihakua halutun avaimen löytämiseksi tehokkaasti.

Indeksihaku tarkoittaa puun läpikäyntiä lehtisolmuihin asti, lehtisolmuketjun seuraamista vastaavien tietueiden löytämiseksi sekä varsinaisen datan hakemista levyltä.

Kuvassa on esitetty avaimen 302 haku:

1. Hakupuusta on kyseessä puutyyppi, jossa jokaisella solmulla on kaksi osoitinta: vasen osoitin osoittaa lapsisolmuihin, joiden arvot ovat pienempiä kuin emäsolmun arvo, ja oikea osoitin osoittaa lapsisolmuihin, joiden arvot ovat suurempia kuin emäsolmun arvo;

2. B-puussa juurisolmu voi sisältää useita indeksiarvoja. Esimerkiksi, jos juurisolmussa on kolme erillistä arvoa, sillä on kolme osoitinta, joista kukin osoittaa avainarvojen välisten arvojen alueelle;

3. Kun etsitään avainta, kuten 302, haku alkaa juurisolmusta ja seuraa sopivia osoittimia lehtisolmuihin asti. Haku päättyy kolmen puulohkon läpikäynnin jälkeen, kuten kuvassa punaisella korostettuna;

4. Kun etsitään arvoaluetta alkaen 302:sta, voidaan käyttää lehtisolmujen välisiä vaakasuuntaisia osoittimia. Esimerkiksi arvojen hakeminen välillä 302–502 tapahtuu seuraamalla lehtisolmuja peräkkäin.

Hyödyt ja haitat

Toisin kuin tavallisessa binäärihakupuussa, B-puun solmut voivat sisältää enemmän kuin 2 lasta. Solmun oletusarvoinen enimmäismäärä lapsia on tyypillisesti 16.

Indeksin toteutus

Voit luoda B-puu -indeksin sarakkeelle PostgreSQL:ssä seuraavalla SQL-komennolla:

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

Koska B-puu -indeksi on oletusindeksi SQL:ssä, voimme käyttää myös seuraavaa lauseketta sen luomiseen:

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