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. Voit oppia lisää BST:istä Algoritmit ja tietorakenteet -yleiskatsaus -kurssilla.

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

Miten se toimii?

B-puuindeksi järjestää tiedot hierarkkisella tavalla, ja 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 etsitään tiettyä avainta, 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. Hakupuuta kuvaava rakenne on puu, jossa jokaisella solmulla on kaksi osoitinta: vasen osoitin viittaa lapsisolmuihin, joiden arvot ovat pienempiä kuin vanhemman solmun arvo, ja oikea osoitin viittaa lapsisolmuihin, joiden arvot ovat suurempia kuin vanhemman 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 haetaan avainta, kuten 302, haku aloitetaan juurisolmusta ja seurataan sopivia osoittimia lehtisolmuihin asti. Haku päättyy kolmen puulohkon läpikäynnin jälkeen, kuten kuvassa punaisella korostettuna;

4. Kun haetaan arvojoukkoa alkaen arvosta 302, voidaan käyttää lehtisolmujen välisiä vaakasuuntaisia osoittimia. Esimerkiksi arvojen 302–502 hakeminen tapahtuu seuraamalla lehtisolmuja peräkkäin.

Huom

B-puuindeksin hakua varten käytetty avain perustuu tietokantataulun indeksoidun sarakkeen arvoihin. Esimerkiksi, jos indeksi on sarakkeessa "client_id", hakua varten käytetään todellisia "client_id"-arvoja. Jokainen yksilöllinen numeerinen arvo indeksoidussa sarakkeessa toimii avaimena B-puuindeksissä, mikä helpottaa vastaavien rivien löytämistä ja hakemista tietokantataulusta.

Hyödyt ja haitat

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

Indeksin toteutus

B-puuindeksin luominen PostgreSQL:ssä onnistuu seuraavalla SQL-komennolla:

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

Koska B-puuindeksi on oletusindeksi SQL:ssä, sen voi luoda myös seuraavalla lauseella:

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

Huom

SQL:ssä, kun tauluun luodaan primary key -rajoite, useimmat tietokantajärjestelmät luovat automaattisesti indeksin niille sarakkeille, jotka on määritelty primary key -rajoitteessa. Tämä indeksi auttaa varmistamaan primary keyn yksikäsitteisyyden ja parantaa myös sellaisten kyselyiden suorituskykyä, joissa haetaan tai yhdistetään primary key -sarakkeen perusteella.