B-Agacında arama neden doğrusal taramadan daha hızlıdır?

B-ağaçta arama, yapısının, karşılaştırma ve disk işlemlerinin sayısını en aza indirecek şekilde tasarlandığı için daha hızlıdır.

• Logaritmik karmaşıklık: B-ağaçlar, her düğümde birkaç anahtar içeren dengeli bir ağaç biçiminde veri temsil edilerek, N öğe sayısına göre O(log N) zaman karmaşıklığıyla arama sağlar.
• Dallanma: Her düğüm, birkaç anahtar ve çocuk göstericisi içerebilir. Arama sırasında, aranan anahtarı mevcut düğümdeki anahtarlarla karşılaştırırız ve doğru çocuk düğümüne geçiş yaparız. Bu, ziyaret edilmesi gereken düğüm sayısını önemli ölçüde azaltır.
• Disk erişimi optimizasyonu: B-ağaçtaki düğüm boyutu genellikle disk bloğu boyutuna uygun seçilir. Bu, düğüm yüklendiğinde büyük veri bloklarını doğrudan okuyarak, yavaş disk giriş/çıkış işlemlerini en aza indirir. Doğrusal tarama ise her öğeyi sıralı şekilde okuma gerektirir.