MongoDB bruger B-tree til indeksering, som det kan ses i kildekoden til index.cpp
. Det betyder, at opslag kan udtrykkes som O(log N) hvor N er antallet af dokumenter, men det er også O(D) hvis D er træets dybde (forudsat at træet er noget afbalanceret). D er normalt meget lille, fordi hver knude vil have mange børn.
Antallet af børn i en node i MongoDB er omkring 8192 (btree.h ) altså et indeks med et par milliarder dokumenter kan passe ind i et træ med kun 3 niveauer! Du indser nemt, at logaritmen ikke er log_2 (som i binære træer), men i stedet log_8192, som vokser ekstremt langsomt.
På grund af dette betragtes b-træer normalt som konstanttidsopslag, O(1) , i praksis.
En anden god grund til at holde mange børn i hver node er, at indekset er gemt på disken. Du vil prøve at udnytte al pladsen i en diskblok til én node for at forbedre cache-ydeevnen og reducere disksøgninger. B-træer har meget god diskydeevne, fordi du kun behøver at besøge meget få noder for at finde det, du leder efter.