MongoDB používá k indexování B-strom, jak je vidět ve zdrojovém kódu pro index.cpp
. To znamená, že vyhledávání lze vyjádřit jako O(log N) kde N je počet dokumentů, ale je to také O(D) jestliže D je hloubka stromu (za předpokladu, že strom je poněkud vyvážený). D je obvykle velmi malý, protože každý uzel bude mít mnoho dětí.
Počet dětí v uzlu v MongoDB je asi 8192 (btree.h ) tedy index s pár miliardami dokumenty se mohou vejít do stromu pouze se 3 úrovněmi! Snadno zjistíte, že logaritmus není log_2 (jako u binárních stromů), ale místo toho log_8192, který roste extrémně pomalu.
Z tohoto důvodu jsou b-stromy obvykle považovány za vyhledávání v konstantním čase, O(1) , v praxi.
Dalším dobrým důvodem pro ponechání mnoha potomků v každém uzlu je to, že index je uložen na disku. Chcete se pokusit využít veškerý prostor v bloku disku pro jeden uzel, abyste zlepšili výkon mezipaměti a snížili počet vyhledávání disku. B-stromy mají velmi dobrý výkon disku, protože stačí navštívit velmi málo uzlů, abyste našli to, co hledáte.