B stromy

• B stromy jsou zobecněným BST
• B strom je balancovaný, všechny listy mají stejnou délkou
• uzly stromy můžou obsahovat více klíčů
• jestliže vnitřní uzel stromu obsahuje $k$ klíčů, tak má $k + 1$ následníků
• klíče ve vnitřních uzlech stromu zároveň vymezují $k + 1$ intervalů, do kterých patří klíče každého z jeho $k + 1$ podstromů.

Využití B stromů

• databázové systémy = snaha minimalizace přístupů na disk

počet klíčů v disku

• $\log_2 1 000 000 = 20$
• $\log_{100} 1 000 000 = 3$
• velikost uzlu, velikost databáze, počet přístupů

Stupeň B stromu

• minimální stupeň stromu je číslo $t$, které definuje dolní a horní hranici na počet klíčů uložených v uzlu
• každý uzel (s výjimkou kořene) musí obsahovat alespoň $t - 1$ klíčů
• každý vnitřní uzel (s výjimkou kořene) musí mít alespoň $t$ následníků a nejvýš $2t$
• každý uzel může obsahovat nejvýše $2t - 1$ klíčů
• uzel, který má přesně $2t - 1$, se nazývá plný

• počet následníků vnitřního uzlu je o 1 větší než počet klíčů které obsahuje

Výška B stromy

• všechny listy B stromu mají stejnou hloubku
• jestliže B strom s $n \ge 1$ klíči a minimálním stupněm $t \ge 2$ má hloubku $h$, tak $\color{orange} h \le \log_t \frac{n+1}{2}$

Klíče v B stromu

• každý uzel $x$ má atributy
  • $x.n$ - počet klíčů uložených v uzlu $x$
  • $x.key_1,x.key_2,…,x.key_{x.n}$ - klíče, které jsou uspořádány v neklesajícím pořadí, tj. $xkey_1 \le x.key_2 \le … \le x.key_{x.n}$
  • $x.leaf$ - booleovská proměnná nabývající hodnotu true právě když uzel $x$ je listem stromu
  • každý vnitřní uzel $x$ má navíc atributy
    • $x.c_1,x.c_2,…,x.c_{x.n+1}$ - $x.n + 1$ ukazatelů na syny

Operace nad B stromem

• před každou operací, která přistupuje k objektu $x$, se nejdříve musí cykunat operace DiskRead(x), která zkopíruje objekt do paměti (v případě, že tam není)
• symetricky operace DiskWrite(x) se použije pro uložení všech změn vykonaných nad objektem $x$
• kořen B stromu je vždy uložený v operační paměti
• z důvodu optimalizace počtu přístupů na externí disk jsou všechny operace navrženy tak, aby se uzel stromu navštívil nejvýše jednou

Vyhledávání

• argumentem operace je ukazatel $T.root$ a hledaný klíč $k$
• jestliže klíč $k$ je v B stromě, tak operace vrátí (y,i), kde $y$ je uzel a $i$ index takový, že $y.key_i = k$
• v opačném případě vrátí hodnotu None

Vkládání klíče

• podobně jako u BST hledáme list, do kterého uložíme nový klíč

• když vložením klíče dojde k porušení vlastnosti maximálního počtu klíčů, tak
  • list rozdělíme na dva nové listy
  • rozdělením se zvýčí počet následníků předchůdce původního listu
  • pokud se tím poruší vlastnost max. počtu následníků, tak musíme rekurzivně rozdělit i předchůdce
  • proces rozdělování uzlů se v nejhorším případě zastaví až v kořeni stromu

Optimalizace

• “Nikdy nevstoupíš do plného uzlu!”
• funkce Split
• chceme při vkládání jít přes uzel, který je plný
• tak daný uzel rozdělím na 2 a prostředí prvek vložím na pozici otce
• výjimka v případě, že je kořen plný - nový uzel, který je medián původního kořenu - zvětší se hloubka stromu

Složitost

• Celková složitost je $\mathcal{O}(th) = O(t \log_t n)$

Odstranění

• jestliže se klíč určený k odstranění nachází v listu, odstraníme ho jestliže se klíč určený k odstranění nachází v uzlu, který není listem, nahradíme ho jeho následníkem (resp. předchůdcem) a následníka (resp. předchůdce) odstraníme z listu be kterém se původně nacházel
• samotné mazání klíče se vždy realizuje v listu

• odstranění klíče $k$ z listu $x$, list $x$ obsahuje alespoň $t$ klíčů anebo je kořenem stromu
  • klíč $k$ odstraníme
• odstranění klíče $k$ z listu $x$, list $x$ není kořenem a obsahuje přesně $t - 1$ klíčů
  • musíme přidat následníka / předchůdce ze sousedních uzlů
    • má si od koho půjčit - přeskládá prvky
    • nemá si od koho půjčit - vše z daného uzlu, vše z bratra + klíč mezi uzlem a bratrem

Optimalizace

• “Nikdy nevstoupíš do uzlu, který obsahuje minimální počet klíčů!”

Složitost

• Celková složitost je $\mathcal{O}(th) = O(t \log_t n)$