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.

• 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.

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.

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ň.

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

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.