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

Индексы

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеш-индексы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заранее сделаем заголовок большого размера.

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

Есть точные гарантии по производительности~--- все наши затраты измеряются единицами страниц.

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

• Проверка существования ключа
  • Проверка повторений (ключи)
  • in - только если есть все необходимые атрибуты, то есть даны все столбцы, которые есть в хеш-индексе. Иначе индек не поможет, так как нет способа перебрать все варианты
  • exist - только если есть все необходимые атрибуты, анологично с in
  • 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