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

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

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

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

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

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

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

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

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

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

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

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

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

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