Индексация данных. Упорядоченные и хеш-индексы — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 76: Строка 76:
 
* При переполнении происходит разделение корзин
 
* При переполнении происходит разделение корзин
 
** Страница глубины $k$ разделяется на две глубины $k+1$
 
** Страница глубины $k$ разделяется на две глубины $k+1$
 +
 +
=== Ускоряемые запросы ===
 +
 +
*Проверка существования ключа
 +
**Проверка повторений (ключи)
 +
**''in''
 +
**''exist''
 +
**''count''
 +
*Поиск по ключу
 +
**Естественные соединения

Версия 04:46, 20 декабря 2021

Индексы

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

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

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

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

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

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

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

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

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

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

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

Хеш-индексы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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