B-Puu-Indeksointi

B-puuindeksi on tasapainotettu puutietorakenne, jota käytetään yleisesti tietokannoissa suurten tietomäärien tehokkaaseen järjestämiseen ja hakemiseen.
B-puut muistuttavat paljon binäärihakupuita (BST), mutta B-puun solmuilla 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 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 etsitään tiettyä avainta, B-puun algoritmi kulkee puuta pitkin juurisolmusta lehtisolmuihin hyödyntäen binäärihakua halutun avaimen tehokkaaseen löytämiseen.

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

Kuvassa on esitetty avaimen 302 haku:

1. Hakupuusta on kyseessä 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 alueen;

3. Kun haetaan avainta, kuten 302, haku aloitetaan juurisolmusta ja edetään sopivia osoittimia pitkin 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.

Edut 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

B-puuindeksin luominen sarakkeelle 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ä, voidaan käyttää myös seuraavaa komentoa sen luomiseen:

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