Индексация данных. Упорядоченные и хеш-индексы
Версия от 04:02, 20 декабря 2021; Arimionim (обсуждение | вклад)
Индексы
Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.
Всего есть два способа найти нужные данные:
- Полный просмотр таблицы
- Последовательный перебор записей
- Быстро работает на маленьких таблицах, но медленно на средних и больших
- Если выбираем большую часть данных, то работает быстро. Иначе - медленно
- Индекс
- Произвольный набор столбцов
- Требуется предварительная обработка таблицы как при построении, так и при обновлении
- Быстрый поиск в индексе, сразу получаем указатель на запись
Кластеризованный индекс
Если данные в таблице хранятся в порядке индекса, то такой индекс называется кластеризованным. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.
Структура Индекса
В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем
Есть два подхода к реализации индексов:
- Хеш-таблицы
- Деревья поиска
Хеш-индексы
- Предварительная обработка
- Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.
- Разбиение на корзины
- Поиск в индексе
- Просмотр корзины
- Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
- Заголовок помещяется в памяти
