MongoDB използва B-дърво за индексиране, както може да се види в изходния код за index.cpp
. Това означава, че справките могат да бъдат изразени като O(log N) където N е броят на документите, но също така е O(D) ако D е дълбочината на дървото (приемайки, че дървото е донякъде балансирано). D обикновено е много малък, защото всеки възел ще има много деца.
Броят на децата във възел в MongoDB е около 8192 (btree.h ), така че индекс с няколко милиарда документите могат да се поберат в дърво само с 3 нива! Лесно разбирате, че логаритъма не е log_2 (както в двоичните дървета), а вместо това log_8192, който расте изключително бавно.
Поради това b-дърветата обикновено се разглеждат като търсене в постоянно време, O(1) , на практика.
Друга добра причина за поддържане на много деца във всеки възел е, че индексът се съхранява на диск. Искате да опитате да използвате цялото пространство в дисковия блок за един възел, за да подобрите производителността на кеша и да намалите търсенето на диск. B-дърветата имат много добра дискова производителност, защото трябва да посетите много малко възли, за да намерите това, което търсите.
