Kodėl paieška B-medyje yra greitesnė nei linijinė paieška?

B-medžio paieška yra greitesnė dėl savo struktūros, kuri sumažina palyginimų ir disko operacijų skaičių.

• Lyginamosios sudėtingumas: B-medžiai turi lyginamosios paieškos laiko sudėtingumą, O(log N), kur N yra elementų skaičius. Tai pasiekiama vaizduojant duomenis kaip subalansuotą medį su keliais rakteliais kiekviename mazge.
• Šakotumas: Kiekvienas mazgas gali turėti kelis raktus ir nuorodas į vaikus. Paieškos metu lyginame ieškomą raktą su dabartinio mazgo raktais, nustatydami tinkamą vaikų mazgą tęsti paiešką. Tai žymiai sumažina lankomų mazgų skaičių.
• Optimizavimas disko prieigai: B-medžio mazgų dydis dažniausiai pasirenkamas taip, kad atitiktų disko bloko dydį. Tai leidžia įkelti vienu metu didelį duomenų kiekį į atmintį, sumažinant lėtus disko įvesties/išvesties veiksmus. Linijinė paieška, priešingai, reikalauja sekos skaityti kiekvieną elementą.