B-strom
From Wikipedia, the free encyclopedia
B-strom je druh stromu. Je specifický tím, že má řád a limity na maximální (), i minimální () počet potomků vrcholu. B-strom je díky této vlastnosti vyvážený, operace přidání, vyjmutí i vyhledávání tedy probíhají v logaritmickém čase. Tato struktura je často používána v aplikacích, kdy není celá struktura uložena v operační paměti (RAM), ale v nějaké sekundární paměti, jako je pevný disk (například databáze). Protože přístup do tohoto typu paměti je náročný na čas (hlavně vyhledání náhodné položky), snažíme se minimalizovat počet přístupů do této paměti.
Příklad: Máme-li B-strom hloubky 2 a počet potomků každého uzlu je 1 001, můžeme do něj uložit miliardu klíčů (obsahuje milion uzlů) a ke každé položce se dostaneme maximálně po dvou diskových operacích.
B-strom je speciální případ (a,b)-stromu, který poskytuje větší volnost ve volbě minimálního a maximálního počtu potomků než B-strom.
Autoři algoritmu, Rudolf Bayer a Ed McCreight, nikdy nevysvětlili, co v názvu znamená písmeno B. Nejčastěji se předpokládá, že znamená balanced (v angličtině vyvážený), jelikož všechny listy jsou na stejné úrovni stromu. B může být také první písmeno jména Bayer, případně Boeing, oba totiž v té době pracovali ve výzkumném ústavu této firmy.