Prečo je vyhľadávanie v B-strome rýchlejšie ako lineárne prehľadávanie?

Vyhľadávanie v B-strome je rýchlejšie vďaka jeho štruktúre, ktorá minimalizuje počet porovnaní a diskových operácií.

• Logaritmická zložitosť: B-stromy majú logaritmickú časovú zložitosť vyhľadávania, O(log N), kde N je počet prvkov. Toho sa dosahuje reprezentáciou dát vo vyváženom strome s viacerými kľúčmi v každom uzle.
• Väzba: Každý uzol môže obsahovať niekoľko kľúčov a ukazovateľov na deti. Počas vyhľadávania porovnávame hľadaný kľúč s kľúčmi v aktuálnom uzle, určujúc správny potomok na pokračovanie. To výrazne znižuje počet uzlov, ktoré je potrebné navštíviť.
• Optimalizácia pre prístup na disk: Veľkosť uzlov v B-strome je zvyčajne nastavená tak, aby zodpovedala veľkosti bloku na disku. To umožňuje pri načítaní uzla do pamäti načítať naraz veľké množstvo dát, minimalizujúc pomalé operácie vstupu/výstupu na disk. Lineárne vyhľadávanie naopak vyžaduje sekvenčné čítanie každého prvku.