B* strom

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íč.

[editovat] Související články

• B-strom
• B+ strom
• UB strom

Tento článek o algoritmu nebo datové struktuře je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.