MongoDB gebruikt B-tree voor indexering, zoals te zien is in de broncode voor index.cpp
. Dit betekent dat zoekopdrachten kunnen worden uitgedrukt als O(log N) waarbij N het aantal documenten is, maar het is ook O(D) als D de diepte van de boom is (ervan uitgaande dat de boom enigszins in evenwicht is). D is meestal erg klein omdat elke knoop veel kinderen zal hebben.
Het aantal kinderen in een node in MongoDB is ongeveer 8192 (btree.h ) dus een index met een paar miljarden documenten passen misschien in een boom met slechts 3 niveaus! Je realiseert je gemakkelijk dat de logaritme niet log_2 is (zoals in binaire bomen) maar in plaats daarvan log_8192, dat extreem langzaam groeit.
Om deze reden worden b-trees gewoonlijk beschouwd als constant-time lookup, O(1) , in de praktijk.
Een andere goede reden om veel kinderen in elk knooppunt te houden, is dat de index op schijf wordt opgeslagen. U wilt proberen alle ruimte in een schijfblok voor één knooppunt te gebruiken om de cacheprestaties te verbeteren en het zoeken naar schijven te verminderen. B-trees hebben zeer goede schijfprestaties omdat je maar heel weinig nodes hoeft te bezoeken om te vinden wat je zoekt.