MongoDB använder B-tree för indexering, vilket kan ses i källkoden för index.cpp
. Detta betyder att uppslagningar kan uttryckas som O(log N) där N är antalet dokument, men det är också O(D) om D är trädets djup (förutsatt att trädet är något balanserat). D är vanligtvis mycket liten eftersom varje nod kommer att ha många barn.
Antalet barn i en nod i MongoDB är cirka 8192 (btree.h ) alltså ett index med några miljarder dokument får plats i ett träd med endast 3 nivåer! Du inser lätt att logaritmen inte är log_2 (som i binära träd) utan istället log_8192, som växer extremt långsamt.
På grund av detta betraktas b-träd vanligtvis som konstanttidsuppslag, O(1) , i praktiken.
En annan bra anledning till att ha många barn i varje nod är att indexet lagras på disk. Du vill försöka utnyttja allt utrymme i ett diskblock för en nod för att förbättra cacheprestanda och minska disksökningar. B-träd har mycket bra diskprestanda eftersom du bara behöver besöka väldigt få noder för att hitta det du letar efter.