Proč je hledání v B-stromu rychlejší než lineární průchod?

Vyhledávání v B-stromu je rychlejší díky své struktuře, která minimalizuje počet porovnání a diskových operací.

• Logaritmická složitost: B-stromy mají logaritmickou časovou složitost hledání, O(log N), kde N je počet prvků. Toho se dosahuje reprezentací dat ve vyváženém stromu s více klíči v každém uzlu.
• Větvení: Každý uzel může obsahovat několik klíčů a ukazatelů na potomky. Při hledání porovnáváme hledaný klíč s klíči v aktuálním uzlu, určujíc správný potomek pro pokračování. To výrazně snižuje počet uzlů, které je třeba navštívit.
• Optimalizace pro přístup na disk: Velikost uzlů v B-stromu je obvykle nastavena tak, aby odpovídala velikosti bloku na disku. To umožňuje při načtení uzlu do paměti načíst najednou velké množství dat, minimalizujíc pomalé operace vstupu/výstupu na disk. Lineární prohledávání naopak vyžaduje sekvenční čtení každého prvku.