Me pregunto cómo funciona la ordenación con un índice en MongoDB. Hay unPareja artículos en la documentación de MongoDB, pero en realidad no describen cómo procede la clasificación ni la complejidad del tiempo. Las búsquedas de SO y el interweb en general hasta ahora no han resultado relevantes.

Asumamos que haya documentos en una colección, la cláusula find () coincideb documentos, hay un límite dec documentos devueltos,a >>b >>cyc es un número adecuadamente grande de tal manera que el conjunto devuelto no puede caber en la memoria, digamos, por ejemplo, documentos 1M.

Al inicio de la operación, existeb documentos que necesitan ser ordenados y un índice de tamaño de árbol ordenadoa para la función se ordenarán los documentos.

Puedo imaginar:

A) recorra el índice en orden, y para cada ObjectID recorra la lista deb documentos. Volver partidos hastac es alcanzado. Esto sería O (ab)

B) como A), pero cree un hashset de los ObjectID en elb documentos primero. Este es O (a), pero toma O (b) memoria.

He tratado de considerar tipos basados en atravesar el conjunto deb documentos, pero parece que no puede encontrar nada más rápido que O (b Iniciar sesiónb), que no es mejor que ordenar sin un índice.

Supongo (pero tal vez me equivoque) que cada tipo no requiere un escaneo de índice, entonces, ¿cómo funciona realmente el tipo?

Actualizar:

La respuesta de Kevin y el enlace proporcionado reducen mucho la pregunta, pero me gustaría confirmar / aclarar algunos puntos:

Según tengo entendido, no puede usar diferentes índices para la consulta y la ordenación si desea evitar una ordenación en memoria. Cuando leoesta página parecía como si pudieras (o al menos, no especificaba de una forma u otra), pero eso parece ser incorrecto. Esencialmente, los documentos se ordenan porque se buscan en el orden del índice durante la consulta y, por lo tanto, se devuelven en el orden del índice. ¿Derecho?Al consultar en un índice compuesto, el índice de clasificacióndebe ser el primer índice en el índice compuesto, excepto los índices donde la consulta es una igualdad. Si no, la clasificación se realiza en la memoria. ¿Derecho?

¿Cómo funciona la clasificación con$in o$or consultas? Por ejemplo, suponga que la consulta es

{a: {$in: [4, 6, 2, 1, 3, 10]}, b: {$gt: 1, $lt: 6}}

... y hay un índice compuesto ena yb en ese orden. ¿Cómo funcionaría la ordenación en los casos en que está ordenada?a ob? $or es aún más complicado ya que, según tengo entendido,$or Las consultas se dividen esencialmente en múltiples consultas separadas. Son$or consultas siempre en la memoria, al menos para fusionar los resultados de las consultas separadas?