Mitä ovat B-puut ja B+ puut ja miksi tietokannat käyttävät niitä?

Question

IT Interview Practice · Accepted Answer

**B-puu** on itsestään tasapainottava hakupuu, jossa jokainen solmu sisältää **monia avaimia** ja joilla on **monia lapsia** (korkea *fanout*). Tämä pitää puun **matalana**, minimoiden **levyjen lukumäärän** — juuri sitä mitä tietokannat ja tiedostojärjestelmät tarvitsevat. ## Miksi korkea fanout voittaa binääripuun ```text Binary BST over 1,000,000 keys -> height ~20 (20 disk seeks) B-tree, 100 keys/node -> height ~3 (3 disk seeks) Each node = one disk block/page read. ``` ## Rakenne (B-puu järjestys 4) ```text [ 17 | 35 ] / | \ [4|9|12] [20|28] [40|50|60] each node packs many keys -> few levels ``` ## B+ puun parantaminen **B+ puussa** *kaikki arvot asuvat lehdissä* ja lehdet ovat **linkitettyjä**, joten alueen skannaamiset kävelevät linkitettynä lehtien luettelona — ihanteellinen kyselyille kuten `WHERE age BETWEEN 20 AND 40`. ```text internal nodes: keys only (routing) leaves: [..]<->[..]<->[..] <- linked for fast range scans ``` ## Monimutkaisuus | Operaatio | Aika | Disk I/O | |---|---|---| | search | O(log n) | O(height) | | insert / delete | O(log n) | O(height) | | range scan | O(log n + k) | sequential leaves | ## Miksi sillä on merkitystä Levyn ja SSD-käyttö on useita kertaluokkia hitaampaa kuin muisti, joten mittari joka merkitsee on **I/O-luku, ei vertailut**. Korkea fanout vähentää I/O:ta dramaattisesti pitämällä puun vain muutaman tason syvyytenä. Tämä on syy siihen, että lähes jokainen relaatiotietokannan indeksi (ja monet tiedostojärjestelmät) on rakennettu B+ puille binäärihakupuiden sijaan.

Operaatio	Aika	Disk I/O
search	O(log n)	O(height)
insert / delete	O(log n)	O(height)
range scan	O(log n + k)	sequential leaves

Miksi korkea fanout voittaa binääripuun

Rakenne (B-puu järjestys 4)

B+ puun parantaminen

Monimutkaisuus

Miksi sillä on merkitystä

Aiheeseen liittyvät kysymykset