BPC-ALD - Skripta_rev2019_2

Prvky uložené v uzlu jsou v něm seřazeny vzestupně dle velikosti. 

B-stromy jsou 
vyhledávací 
stromy s více 
prvky v uzlu. 

− 74 − 

Uzel je buďto list anebo má o jednoho následníka více, než je počet prvků v něm uložený. 

Přitom pro prvky v jednotlivých podstromech, které těmito následníky začínají, platí: 

Pro každý prvek d v podstromu začínajícího uzlem násl0 platí d<c1. 
Pro každý prvek d v podstromu začínajícího uzlem násl1 platí c1<d<c2. 
Pro každý prvek d v podstromu začínajícího uzlem násl2 platí c2<d<c3. 
………… 

Pro každý prvek d v podstromu začínajícího uzlem náslk-1 platí c k-1<d<ck. 
Pro každý prvek d v podstromu začínajícího uzlem náslk platí d>ck. 
A zbývá nám poslední vlastnost, jež určuje vyváženost B-stromu. Ta stanoví, že listy jsou v B-
stromu jen v jeho poslední vrstvě. 

Příklad. Na následujícím obrázku je B-strom pro r=4. Prvky uložené ve stromu jsou stejně jako 
ve všech dosavadních příkladech celá čísla. 

Postup vyhledávání 

1.  Počáteční krok 

Uzel,  který  je  v daném  okamžiku  vyhledávání  aktuální,  budeme  označovat  u.  Na  začátku  jím 
bude kořen stromu. 

Hledaná hodnota nechť je x. 

2.  Průběžný krok 

Provedeme  vyhledání  hodnoty  mezi  prvky  uloženými  v aktuálním  uzlu  u.  Protože  prvky  jsou 
v uzlu setříděné, lze k tomu použít binární vyhledávání. To použijeme v případě, kdy kapacita 
uzlů je zvolena dostatečně velká, aby se to vyplatilo (např. r

≥10). Vyhledání může skončit třemi 

způsoby: 

a)  Prvek byl v aktuálním uzlu u nalezen, čímž vyhledávání úspěšně končí. 

− 75 − 

b)  Prvek  nebyl  v aktuálním  uzlu  u  nalezen  a  tento  uzel  je  list.  Tím  vyhledávání  končí  –