Waarom is zoeken in een B-boom sneller dan lineair zoeken?

De zoekactie in een B-boom is sneller dankzij de structuur, die het aantal vergelijkingen en schijfbewerkingen minimaliseert.

• Logaritmische complexiteit: B-bomen hebben een logaritmische zoektijdcomplexiteit, O(log N), waarbij N het aantal elementen is. Dit wordt bereikt door de gegevens weer te geven als een gebalanceerde boom met meerdere sleutels in elke knoop.
• Vertakking: Elke knoop kan meerdere sleutels en aanwijzingen naar kinderen bevatten. Tijdens de zoektocht vergelijken we de gezochte sleutel met de sleutels in de huidige knoop, waardoor we de juiste kindknoop bepalen. Dit vermindert het aantal te bezoeken knopen aanzienlijk.
• Optimalisatie voor schijftoegang: De grootte van de knopen in de B-boom wordt meestal gekozen zodat deze overeenkomt met de grootte van een schijfblok. Dit maakt het mogelijk om bij het laden van een knoop meteen grote hoeveelheden gegevens te lezen, waardoor trage schijf-I/O-operaties worden geminimaliseerd. Lineair zoeken vereist daarentegen het sequentieel lezen van elk element.