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

Индексы

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

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

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

На больших данных вся таблица не помещяется в память, из-за этого время работы очень сильно возрастает.

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

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

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

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

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

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

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

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

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

Хеш-индексы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Проверка существования ключа
  • Проверка повторений (ключи)
  • in - только если есть все необходимые атрибуты
  • exist - только если есть все необходимые атрибуты
  • count - зачастую можно посчитать по индексу count, не обращаясь к самим записям
• Поиск по ключу
  • Естественные соединения

Упорядоченные индексы

Традиционно реализуются на деревьях поиска

• Предварительная обработка
  • Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание
• Поиск в индексе
  • Поиск в упорядоченной последовательности

Деревья поиска

• Количество операций
  • Обычно пропорционально $O$(высоты)
  • Так как время выполнение операций зависит от высоты, для оптимизации времени нужно минимизировать высоту
• Размер узла
  • Хотим эффективно использовать страницы
  • Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной

$B$ и $B+$ деревья

• $B$ деревья степени $n$
  • От $\frac{n}{2}$ до n детей
  • Указатели и ключи хранятся в узлах
• $B+$ деревья степени $n$
  • От $\frac{n}{2}$ до $n$ детей
  • Указатели хранятся в листьях

• $B+$ меньше данных в узлах - сильнее ветвятся
• $B+$ на одну страницу глубже

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

Плотные и разряженные индексы

• Плотный индекс
  • Храним ключи всех элементов
• Разряженные индекс
  • Храним ключи части элементов
  • Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых
  • Разряженный индекс бычно используется для кластеризованных индексов
  • Уменьшает число уровней

Так как упорядоченных индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления

• Строки
  • Много данных в ключе – меньше степень ветвления
  • Можно использовать префиксы
  • Строки опасно использовать в качестве индекса, может сильно вырости высота дерева
• Суррогатные ключи
  • Малый размер
  • Выше эффективность
  • Широкие и низкие деревья - хорошо
• Изменяющиеся данные
  • Частое обновление индекса
  • Уменьшение индекса
  • Не эффективно, для уменьшения данных нужна отдельная таска

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

• Проверка существования ключа
• Поиск по ключу
• Минимум и максимум среди значений, на которых построен ключ
• Диапазон
  • Загрузка
  • count. count * работает быстроее, так как не нужно идти по всем данным
• Если построен на строках, like по префиксу

Литература

• Дейт К. Введение в системы баз данных (Приложение Г)
• Кнут Д. Искусство программирования. Том 3. Сортировка и поиск
• Silberschatz A., Korth H. F., Sudarshan S. Database System Concepts