B*-strom je typ B-stromu, ve kterém je každý uzel stromu alespoň z ⅔ plný (na rozdíl od B-stromu, kde je toto číslo 1/2).
B*-stromy navrhli Rudolf Bayer a Edward McCraith , kteří studovali problém kompaktnosti B-stromů . B*-strom je relativně kompaktnější, protože každý uzel je plně využit. V ostatních ohledech se tento typ stromu neliší od jednoduchého B-stromu.
Pro splnění požadavku „uzel je zaplněný alespoň ze 2/3“ je třeba opustit jednoduchý postup dělení přetékajícího uzlu. Místo toho dochází k „transfuzi“ do sousedního uzlu. Pokud je zaplněn i sousední uzel, pak se klíče přibližně rovnoměrně rozdělí na 3 nové uzly.
B + -strom , který splňuje tyto požadavky, se nazývá B *+ -strom [1] .
| Strom (datová struktura) | |
|---|---|
| Binární stromy | |
| Samovyrovnávací binární stromy |
|
| B-stromy |
|
| předponové stromy |
|
| Binární dělení prostoru | |
| Nebinární stromy |
|
| Rozbití prostoru |
|
| Jiné stromy |
|
| Algoritmy |
|