MongoDB usa B-tree para indexação, como pode ser visto no código-fonte para index.cpp . Isso significa que as pesquisas podem ser expressas como O(log N) onde N é o número de documentos, mas também é O(D) se D é a profundidade da árvore (assumindo que a árvore é um pouco equilibrada). D é geralmente muito pequeno porque cada nó terá muitos filhos.

O número de filhos em um nó no MongoDB é de cerca de 8192 (btree.h ) para um índice com alguns bilhões documentos podem caber em uma árvore com apenas 3 níveis! Você percebe facilmente que o logaritmo não é log_2 (como nas árvores binárias), mas sim log_8192, que cresce extremamente lentamente.

Por causa disso, as b-trees são geralmente consideradas como pesquisa de tempo constante, O(1) , na prática.

Outra boa razão para manter muitos filhos em cada nó é que o índice é armazenado em disco. Você deseja tentar utilizar todo o espaço em um bloco de disco para um nó para melhorar o desempenho do cache e reduzir as buscas de disco. As árvores B têm um desempenho de disco muito bom porque você só precisa visitar muito poucos nós para encontrar o que está procurando.