Индексация данных. Упорядоченные и хеш-индексы

Индексы

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

Всего есть два способа найти нужные данные:

• Полный просмотр таблицы
  • Последовательный перебор записей
  • Быстро работает на маленьких таблицах, но медленно на средних и больших
  • Если выбираем большую часть данных, то работает быстро. Иначе - медленно
• Индекс
  • Произвольный набор столбцов
  • Требуется предварительная обработка таблицы как при построении, так и при обновлении
  • Быстрый поиск в индексе, сразу получаем указатель на запись

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

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

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

Структура Индекса

Структура индекса

В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем

Есть два подхода к реализации индексов:

• Хеш-таблицы
• Деревья поиска

Хеш-индексы

• Предварительная обработка
  • Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.
  • Разбиение на корзины
• Поиск в индексе
  • Просмотр корзины
  • Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
• Заголовок помещяется в памяти