Методы индексирования и доступа

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

Definition

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

Scope

Эта тема охватывает структуры и концепции, лежащие в основе путей доступа к данным: различие между кластеризованными и некластеризованными, первичными и вторичными индексами; B+-дерево как основной упорядоченный индекс, поддерживающий поиск по равенству и диапазону; хеш-индексы для поиска по равенству; и роль индексов в выборе, объединении и избегании сортировки. В ней рассматривается, как выбор индекса влияет на стоимость запроса и накладные расходы на обновление. Она исключает общий выбор плана оптимизатором на основе стоимости, что является отдельной темой.

Core questions

• Как B+-дерево эффективно поддерживает как запросы на равенство, так и запросы на диапазон?
• В чем разница между кластеризованными и некластеризованными, первичными и вторичными индексами?
• Когда хеш-индекс предпочтительнее древовидного индекса?
• Как индексы ускоряют выборки, объединения и упорядоченное извлечение?
• Какова стоимость поддержки индексов при вставках, обновлениях и удалениях?

Key concepts

• B+-дерево
• хеш-индекс
• кластеризованный и некластеризованный индекс
• первичные и вторичные индексы
• плотные и разреженные индексы
• поиск по диапазону и по равенству
• расширяемое и линейное хеширование
• стоимость поддержки индекса

Key theories

B+-деревья

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

Кластеризованные и некластеризованные индексы

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

Хеш-индексы

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

Clinical relevance

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

History

Байер и МакКрейт представили B-дерево в 1972 году для поддержания больших упорядоченных индексов на диске; вариант B+-дерева, который хранит все данные в листьях, стал стандартным индексом базы данных, как было рассмотрено в работе Комера 1979 года «Повсеместное B-дерево». Хеш-методы доступа и схемы динамического хеширования развивались параллельно, и оба семейства остаются основными для каждого реляционного движка.

Key figures

• Rudolf Bayer
• Edward McCreight
• Douglas Comer

Seminal works

• bayer1972
• comer1979
• ramakrishnan2003

Frequently asked questions

Почему в базах данных используются B+-деревья вместо бинарных деревьев поиска?

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

Когда следует использовать хеш-индекс вместо B+-дерева?

Используйте хеш-индекс, когда вам нужны только поиски по равенству (например, найти строку с заданным идентификатором) и вы хотите получить ожидаемый доступ за постоянное время. Используйте B+-дерево, когда вам также нужны запросы по диапазону, упорядоченное сканирование или сопоставление префиксов, поскольку хеш-индексы не сохраняют порядок ключей и не могут эффективно отвечать на условия диапазона.