Более точный ответ: MongoDB использует индексы B-Tree. Поиск определенного значения в B-дереве имеет сложность O (log n) в среднем и наихудшем случаях, что можно считать достаточно быстрым (то есть двоичный поиск). Это не постоянная сложность = O (1), поэтому вы все равно можете иметь некоторые эффекты замедления, если размер индекса будет больше, чем доступная оперативная память. (MongoDB пытается сохранить индексы в оперативной памяти, и каждый ввод-вывод, необходимый для поиска индекса на диске, значительно замедлит ваш запрос).