Я новичок в базах данных, так что простите меня, если это глупый вопрос.
В современных базах данных, если я использую индекс для доступа к строке, я считаю, что это будет сложность O (1). Но если я сделаю запрос, чтобы выбрать другой столбец, будет ли он O (1) или O (n)? Должна ли база данных проходить через все строки или создавать отсортированный список для каждого столбца?
На самом деле, я думаю, что доступ, основанный на индексе, будет O (log (n)), потому что вы все равно будете искать через организацию B-Tree-esque, чтобы перейти к вашей записи.
Чтобы ответить на ваш личный вопрос, да, если в столбце нет индекса, движок базы данных должен будет смотреть на все строки.
В более интересном случае выбора по нескольким столбцам, как с индексом, так и без него, ситуация становится более сложной: если Оптимизатор запросов выбирает использовать индекс, тогда он сначала будет выбирать строки на основе индекса, а затем применять фильтр с оставшимися ограничениями. Таким образом, сокращение второй операции фильтрации от O (количество строк) до O (количество выбранных строк по индексу). Отношение между этими двумя номерами называется селективностью и важной статистикой при выборе того, какой индекс использовать.
Индексы относятся к столбцу, поэтому, если вы используете предложение where в столбце без индексации, он будет делать так называемые таблицы, которые являются O (n).
Я не знаю ответа, но имейте в виду, что запись в формате "большой O" дает вам представление о производительности для размеров данных, которые являются сколь угодно большими.
Например, узкое место для производительности базы данных обычно ищет диски. Поэтому производительность значительно возрастает, если рабочий набор данных может храниться в памяти. Нотация Big-O не расскажет вам ничего о таких оптимизациях, потому что они применимы только для конечных наборов данных.
B-деревья не дают O (logN), то есть сложность двоичного дерева.
B-Tree организован таким образом, что он имеет целый блок на node, поэтому после обнаружения node одна операция ввода-вывода может считывать весь блок.
С количеством элементов на node= коэффициент блокировки (# records/block) {bfr}, оптимизированный поиск B-Tree даст O (log bfr ÷ 2 +1 N) Операции ввода-вывода вместо операций ввода-вывода O (N), которые ищут запись по ключу.
У вас есть индексы. Кластерные индексы физически сортируются на диске, вы можете иметь только одну таблицу. Некластеризованные индексы логически отсортированы, и у вас может быть много таких (осторожно, чтобы не злоупотреблять им, это может замедлить действия записи). Если в столбце нет индекса, то я считаю его хорошим старым методом строки за строкой.
Существуют разные типы индексов, разные планы выполнения и различные реализации для разных баз данных. Большая часть базы данных кодов отношений находится в алгоритмах оптимизации поиска. На ваш вопрос нет ни одного ответа. Вы можете использовать инструмент для визуализации плана выполнения, когда хотите узнать, как будет выполняться запрос.