Индексы базы данных и их нотация Big-O

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

Запрос на первичный ключ или уникальный индекс даст вам время поиска O (1).
Запрос на не уникальный идентификатор также даст время O (1), хотя, возможно, "1" медленнее, чем для уникального индекса (?)
Запрос в столбце без индекса даст время поиска O (N) (полное сканирование таблицы).

Это вообще правильно? Будет ли запрос на первичный ключ когда-либо давать худшую производительность, чем O (1)? Моя особая проблема связана с SQLite, но мне было бы интересно узнать, в какой степени это зависит от разных баз данных.

Ответ 1

Большинство индексов структуры реляционных баз данных как B-деревья.

Если таблица имеет индекс кластеризации, страницы данных хранятся в виде листовых узлов B-дерева. По существу, индекс кластеризации становится таблицей.

Для таблиц без индекса кластеризации страницы данных таблицы хранятся в куче. Любые некластеризованные индексы являются B-деревьями, где лист node B-дерева идентифицирует конкретную страницу в куче.

Наихудшая высота B-дерева - O (log n), а поскольку поиск зависит от высоты, то поиск B-дерева выполняется в чем-то вроде (в среднем)

O (log _t n)

где t - коэффициент минимизации (каждый node должен иметь не менее t-1 ключей и не более 2 * t * -1 ключей (например, 2 * t * детей).

То, как я это понимаю.

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

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

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

Ответ 2

Индексированные запросы (уникальные или нет) более типичны O (log n). Очень упрощенно, вы можете думать, что это похоже на двоичный поиск в отсортированном массиве. Точнее, это зависит от типа индекса. Но поиск b-дерева, например, по-прежнему равен O (log n).

Если индекс отсутствует, то да, это O (N).

Ответ 3

Если вы выбираете те же столбцы, которые вы ищете, то

Первичный или Unqiue будет O (log n): он ищет b-tree
Неисторический индекс также O (log n) + бит: это поиск по дереву
no index = O (N)

Если вам нужна информация из другого "источника" (пересечение индексов, поиск по закладке/ключу и т.д.), потому что индекс не покрывает, тогда у вас может быть O (n + log n) или O (log n + log n + log n) из-за множества обращений к индексу + промежуточная сортировка.

Если статистика показывает, что вам нужен высокий% строк (например, не очень выборочный индекс), тогда индекс может быть проигнорирован и станет scan = O (n)

Ответ 4

Другие ответы дают хорошую отправную точку; но я бы просто добавил, что для получения O (1), первичный индекс сам по себе должен быть основан на хэше (который обычно не является выбором по умолчанию); так что чаще он логарифмический (B-дерево).

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

Ответ 5

Это зависит от вашего запроса.

Условие формы Column = Value позволяет использовать индекс, основанный на хеше, который имеет O (1) время поиска. Однако многие базы данных, включая SQLite, не поддерживают их.
Условие, использующее реляционные операторы (<, >, <=, >=), может использовать упорядоченный индекс, обычно реализуемый с помощью двоичного дерева, которое имеет время поиска O (log n).
Более сложные выражения, которые не могут использовать индекс, требуют O (n) времени.

Поскольку вы в первую очередь заинтересованы в SQLite, вы можете прочитать его Обзор оптимизатора запросов, в котором более подробно объясняется, как выбираются индексы.