MongoDB usa el árbol B para la indexación, como se puede ver en el código fuente de índice.cpp
. Esto significa que las búsquedas se pueden expresar como O(log N) donde N es el número de documentos, pero también es O(D) si D es la profundidad del árbol (suponiendo que el árbol está algo equilibrado). D suele ser muy pequeño porque cada nodo tendrá muchos hijos.
El número de niños en un nodo en MongoDB es de aproximadamente 8192 (bárbol.h ) por lo que un índice con unos pocos billones ¡Los documentos pueden caber en un árbol con solo 3 niveles! Te das cuenta fácilmente de que el logaritmo no es log_2 (como en los árboles binarios) sino log_8192, que crece muy lentamente.
Debido a esto, los árboles b generalmente se consideran búsquedas en tiempo constante, O(1) , en la práctica.
Otra buena razón para mantener muchos hijos en cada nodo es que el índice se almacena en el disco. Desea intentar utilizar todo el espacio en un bloque de disco para un nodo para mejorar el rendimiento de la memoria caché y reducir las búsquedas de disco. Los árboles B tienen un rendimiento de disco muy bueno porque solo necesita visitar muy pocos nodos para encontrar lo que está buscando.
