Защо търсенето в B-дървото е по-бързо от линейното търсене?

Търсенето в B-дървото е по-бързо благодарение на структурата си, която минимизира броя на сравненията и дисковите операции.

• Логаритмична сложност: B-дерветата имат логаритмична времева сложност на търсене, O(log N), където N е броят на елементите. Това се постига чрез представяне на данните като балансирано дърво с няколко ключа във всеки възел.
• Разклоняване: Всеки възел може да съдържа няколко ключа и указатели към деца. По време на търсенето сравняваме търсения ключ с ключовете в текущия възел, определяйки правилния дъщерен възел за продължаване. Това значително намалява броя на възлите, които трябва да посетим.
• Оптимизация за достъп до диска: Размерът на възлите в B-дървото обикновено се избира така, че да съответства на размера на диск блок. Това позволява при зареждане на възел в паметта да се чете веднага голям обем данни, минимизирайки бавните дискови операции за вход/изход. Линейното търсене, от друга страна, изисква последователно четене на всеки елемент.