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

Индексы

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

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

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

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

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

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

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

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

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

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

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

Хеш-индексы

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

Файл:Index Hash Simple.jpg

Простой хеш-индекс

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

• Так как хеш-функция хорошая, то в цепочке только полезные данные
• Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.

При этом получаем

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

Цепочки страниц

=== Расширяемое хеширование

• Большое количество корзин
• Несколько корзин на одной странице
  • Обычно - последовательных
  • Разделение корзин при переполнении страницы
• Не работает при плохой хеш-функции, но у нас хорошая

Расширяемое хеширование