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

Индексы

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

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

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

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

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

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

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

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

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

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

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

Хеш-индексы

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

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

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

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

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

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

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

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

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

При переполнении страницы мы:

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

Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)

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

Побитное расширяемое хеширование

• Глубина хеша $n$
  • Создадим $2^n$ корзин
• Для каждой страницы хранится ее локальная глубина $k$
  • Это значит что она хранит $2^{n−k} последовательных корзин на странице
  • Может быть разной для разных страниц
• При переполнении происходит разделение корзин
  • Страница глубины $k$ разделяется на две глубины $k+1$

Ускоряемые запросы

• Проверка существования ключа
  • Проверка повторений (ключи)
  • in
  • exist
  • count
• Поиск по ключу
  • Естественные соединения