Сложность времени запроса базы данных

Question

Я довольно плохо знаком с базами данных, так что простите, если это глупый вопрос.

В современных базах данных, если я использую индекс для доступа к строке, я считаю, что это будет сложность O (1). Но если я сделаю запрос, чтобы выбрать другой столбец, это будет O (1) или O (n)? Должна ли база данных выполнять итерацию по всем строкам или она создает отсортированный список для каждого столбца?

Answer 1

На самом деле, я думаю, что доступ на основе индекса будет O (log (n)), потому что вы все равно будете искать в организации B-Tree-esque, чтобы получить доступ к вашей записи.

Answer 2

Чтобы ответить на ваш буквальный вопрос, да, если в столбце нет индекса, ядру базы данных придется просмотреть все строки.

В более интересном случае выбора по нескольким столбцам, как с индексом, так и без него, ситуация становится более сложной: если оптимизатор запросов выбирает использование индекса, он сначала выбирает строки на основе индекса, а затем применяет фильтр с остальными ограничениями. Таким образом, сокращается вторая операция фильтрации с O (количество строк) до O (количество выбранных строк по индексу). Соотношение между этими двумя числами называется селективностью и важной статистикой при выборе используемого индекса.

Answer 3

Индексы для каждого столбца, поэтому, если вы используете предложение where для неиндексированного столбца, оно выполнит так называемое табличное сканирование, которое равно O (n).

Answer 4

Я не знаю ответа, но имейте в виду, что нотация big-O дает вам только представление о производительности для произвольно больших размеров наборов данных.

Например, узким местом для производительности базы данных обычно является диск ищет . Следовательно, производительность значительно возрастает, если рабочий набор данных можно сохранить в памяти. Нотация Big-O ничего не скажет о таких оптимизациях, потому что они актуальны только для конечных наборов данных.

Answer 5

B-деревья не дают O (logN), то есть сложность двоичного дерева.

B-дерево организовано так, что в нем имеется целый блок на узел, поэтому, как только узел найден, одна операция ввода / вывода может прочитать весь блок.

При количестве элементов на узел = коэффициент блокировки (# записей / блок) {bfr}, оптимизированный поиск B-Tree даст O (log _{bfr ÷ 2 +1} N) I / O операции вместо O (N) операций ввода / вывода, ищущих запись по ключу.

Answer 6

Существуют разные типы индексов, разные планы выполнения и разные реализации для разных баз данных. Большая часть базы данных кода отношений находится в поисково-оптимизирующих алгоритмах. Там нет ни одного ответа на ваш вопрос. Вы можете использовать инструмент для визуализации плана выполнения, когда хотите узнать, как будет выполняться запрос.

Answer 7

У вас есть индексы. Кластерные индексы физически сортируются на диске, вы можете иметь только один на таблицу. Некластеризованные индексы логически отсортированы, и их может быть много (осторожно, не злоупотребляйте ими, это может замедлить действия записи). Если в вашем столбце нет индекса, то я считаю, что это старый добрый метод строка за строкой.