====== B-strom (B-Tree) ======

**B-strom** je zobecněním binárního vyhledávacího stromu. Na rozdíl od něj však může mít každý uzel více než dvě děti (potomky) a obsahovat více než jeden klíč. Písmeno "B" v názvu nebylo nikdy autory (Rudolf Bayer a Edward M. McCreight) přesně vysvětleno, ale nejčastěji se interpretuje jako **Balanced** (vyvážený), protože strom automaticky udržuje všechny své listy ve stejné hloubce.

Hlavní výhodou B-stromu je minimalizace počtu operací čtení z disku, což je u velkých databází nejpomalejší část procesu.

----

====== Klíčové vlastnosti ======

  * **Vysoký stupeň větvení:** Uzly mohou mít stovky i tisíce potomků. To znamená, že strom je velmi "nízký" (mělký). I v miliardě záznamů lze najít konkrétní prvek na 3 až 4 průchody uzly.
  * **Vždy vyvážený:** Algoritmus vkládání a mazání zajišťuje, že vzdálenost od kořene k jakémukoliv listu je vždy stejná.
  * **Efektivita disku:** Velikost jednoho uzlu v B-stromu se obvykle nastavuje tak, aby odpovídala velikosti bloku na disku (např. 4 KB nebo 8 KB). Při jednom čtení z disku se tak načte celý uzel s mnoha klíči.



----

====== Jak probíhá vyhledávání ======

Vyhledávání v B-stromu je podobné listování v telefonním seznamu:
  1. Začnete v **kořenovém uzlu**.
  2. Porovnáte hledaný klíč s klíči v uzlu.
  3. Najdete interval, do kterého váš klíč patří (např. klíč je mezi 10 a 20).
  4. Sledujete ukazatel na odpovídajícího potomka (podstrom).
  5. Opakujete, dokud nenajdete shodu nebo nedosáhnete listu.

Díky tomu, že jsou klíče v každém uzlu seřazené, lze uvnitř uzlu použít binární vyhledávání, což proces dále urychluje.

----

====== Vkládání a štěpení uzlů ======

Když se do B-stromu přidávají nová data, strom roste "odspodu nahoru":
  1. Data se vloží do příslušného listu.
  2. Pokud je list plný, dojde k jeho **štěpení** (split). Prostřední prvek se přesune o úroveň výš do rodičovského uzlu.
  3. Pokud se tím zaplní i rodičovský uzel, štěpí se i ten. Takto se může zaplnit až kořen, což je jediný okamžik, kdy se výška stromu zvýší o 1 úroveň.



----

====== Varianty B-stromu ======

V praxi se nejčastěji setkáme s variantami, které základní model vylepšují:

^ Varianta ^ Rozdíl oproti základnímu B-stromu ^ Použití ^
| **B+ strom** | Skutečná data jsou pouze v listech. Listy jsou navzájem propojeny lineárně. | Nejpoužívanější v [[mysql|MySQL]], PostgreSQL, NTFS. |
| **B* strom** | Vyžaduje, aby uzly byly zaplněny alespoň ze 2/3 (místo 1/2), což šetří místo. | Souborové systémy (HFS+). |



----

====== Proč je to důležité? ======

Bez B-stromů by operace typu "najdi všechny objednávky od 1. ledna do 15. ledna" vyžadovaly prohledání celého pevného disku. B+ strom díky propojení listů umožní najít začátek intervalu a pak prostě "přečíst" sousední listy, což je bleskové.

----
//Související pojmy: Indexování, RDBMS, Databáze, Latence, RAM, SQL, Binární strom.//