#sql #database #mongodb #performance #nosql
#sql #База данных #mongodb #Производительность #nosql
Вопрос:
У меня есть предварительно определенный массив A, содержащий произвольное количество идентификаторов строк для конкретной таблицы.
Запрос должен найти все записи / строки этой таблицы, которые имеют идентификаторы строк, не содержащиеся в A.
Какова временная сложность этого запроса?
Идентификатор строки является первичным ключом этой таблицы. Таким образом, он индексируется?
Комментарии:
1. недавно я тестировал агрегацию с
$inее сложностью, состоящей из O (m) m элементов массива, поэтому я предполагаю, что mxn (n записей) (сканирование коллекции) или mxlogn (сканирование индекса), я не уверен в них. Вы можете протестировать его, также с большим или маленьким списком, я думаю, большой => больше времени, по крайней мере, судя по тестам, которые я проводил. Похоже, что MongoDB не использует внутренние наборы и выполняет последовательный поиск в массивах, чтобы определить, содержит или нет.
Ответ №1:
O (n)
Напрямую зависит от количества записей в коллекции.
Если индекс не может быть использован, O (n) . Если можно использовать индексы, индексы представляют собой b-дерево. Таким образом, это будет O (log n).
Также могут быть крайние случаи, но я думаю, что приведенное выше охватывает большинство случаев.
Если вы хотите получить некоторые интересные подробности о ваших запросах / индексах — ознакомьтесь с explain — это метод, который возвращает полезные сведения о запросе / индексах, используемых для возврата результатов.
Комментарии:
1. Запрос относится к самому идентификатору записи. Разве идентификатор записи не всегда по умолчанию будет индексом?
2. @free_lions_n_tigers_from_cages обновленный ответ.
3. Почему это
log(n)так, а неm*log(n)гдеmдлина массива, содержащего записи?4. @free_lions_n_tigers_from_cages — индексы в MongoDB являются b-tree. B-дерево растет и сжимается от корня. Как и в других сбалансированных бинарных деревьях поиска, временная сложность поиска, вставки и удаления равна O (log n)