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

Související články

Pahýl

Tento článek je příliš stručný nebo postrádá důležité informace.
Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.

Stromové datové struktury

Vyhledávací stromy (dynamické množiny/ asociativní pole)	2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • B^x • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α])

Haldy	Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá

Trie	Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast

Prostorové indexační stromy	Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X

Jiné stromy	Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)

Kategorie:Stromy (dat. strukt.)