B* strom je stromová datová struktura používaná v souborových systémech Reiser4, HFS a HFS+. Je variací na B-strom, přičemž více omezuje spodní hranicí potomků; v B* stromu řádu N musí mít všechny uzly ve stromu mimo kořene minimálně 2/3*N dětí místo původního počtu 1/2*N u B-stromu.
Tato změna způsobí že se tento strom nerozpadá tak rychle jako B-strom. Když je uzel úplně plný a chceme přidat další klíč, u B-stromu se uzel rozpadne ve dva zpola zaplněné. U B* stromu se klíč místo toho sdílí se sourozeneckým uzlem. Teprve když se zcela zaplní i tento sourozenecký uzel, tak se tyto dva zcela zaplněné uzly rozpadnou na tři uzly zaplněné jen ze 2/3. Tento způsob implementace stromu také vyžaduje, aby bylo vždy volné místo pro nejlevější klíč.
Související články
