B-strom: Porovnání verzí

Strom je vyvažován požadavkem, aby byly všechny listy na stejné úrovni. Tato hloubka pozvolna logaritmicky roste s tím, jak do stromu přidáváme další data, nebo klesá spolu s vymazáváním dat ze stromu.

 

[[Soubor:Btree.svg|thumb|Ukázka B+ stromu (variace na B-strom, v které musí být všechny hodnoty umístěny až v listech)]]

Data jsou ve stromu uložena jako setříděné hodnoty, které rozdělují strom na jednotlivé [[Strom (datová struktura)#Podstrom|podstromy]]. Například pokud nějaký uzel má tři potomky, musí být v tomto uzlu uloženy dva klíče ''k''₁ a ''k''₂, které budou uzel rozdělovat. Všechny hodnoty které jsou menší než ''k''₁ musí být uloženy v levém podstromu, hodnoty které jsou větší než ''k''₁ a menší než ''k''₂ musí být uloženy v prostředním podstromu, a konečně všechny hodnoty větší než ''k''₂ musí být v pravém podstromu. Na tyto podstromy jsou samozřejmě v uzlu uloženy ukazatele.

;Varianty B- stromů jsou:

* klíče v listech nebo klíče uvnitř,

* B*

* B+

 

* [[Hašovací tabulka]]

 

[[Kategorie:Stromy (datové struktury)]]