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

Question

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

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

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

Answer 1

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

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

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

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

O (log _t n)

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

Этонасколько я понимаю.

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

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

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

Answer 2

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

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

Answer 3

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

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

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

Answer 4

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

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

Answer 5

Если ВЫ ВЫБИРАЕТЕ те же столбцы, которые ищете, то

• Первичным или Unqiue будет O (log n): это поиск по b-дереву
• неуникальный индекс также O (log n) + бит: это поиск по b-дереву
• без индекса = O (N)

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

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