Неліктен B-деректе іздеу сызықтық іздеуге қарағанда жылдамырақ жұмыс істейді?

B-деревіндегі іздеу оның құрылымының арқасында тезірек жұмыс істейді, ол салыстырулар мен дискілік операциялардың санын азайтады.

• Логарифмдік күрделілік: B-деревелері іздеудің логарифмдік уақыттық күрделілігіне ие, O(log N), мұнда N — элементтердің саны. Бұл әр түйінде бірнеше кілт бар теңгерімді ағаш түрінде деректерді көрсету арқылы қол жеткізіледі.
• Бұтақтау: Әр түйін бірнеше кілттер мен ұрпақ көрсеткіштерін қамтуы мүмкін. Іздеу кезінде біз ізделетін кілтті ағымдағы түйіндегі кілттермен салыстырамыз, дұрыс ұрпақ түйінін анықтаймыз. Бұл қажет түйіндердің санын айтарлықтай азайтады.
• Дискілік қол жетімділікке оңтайландыру: B-деревіндегі түйіндердің өлшемі әдетте дискілік блоктың өлшеміне сәйкес таңдалады. Бұл түйін жүктелген кезде жадыға үлкен деректер көлемін бірден оқуға мүмкіндік береді, баяу дискілік операциялардың санын азайтады. Тізбектелген іздеу әр элементті бір-бірлеп оқуды талап етеді.

Оның орнына, тізбектелген іздеу O(N) сызықтық күрделілікке ие, ең нашар жағдайда N салыстыруды талап етеді.