Индексация данных. Упорядоченные и хеш-индексы — различия между версиями
Arimionim (обсуждение | вклад) |
Arimionim (обсуждение | вклад) |
||
| Строка 37: | Строка 37: | ||
** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ. | ** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ. | ||
* Заголовок помещяется в памяти | * Заголовок помещяется в памяти | ||
| − | [[Файл:Index_Hash_Simple. | + | [[Файл:Index_Hash_Simple.png|мини|Простой хеш-индекс]] |
Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. | Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками. | ||
| Строка 50: | Строка 50: | ||
[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]] | [[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]] | ||
| − | === Расширяемое хеширование | + | === Расширяемое хеширование === |
| − | * Большое количество корзин | + | * Большое количество корзин, сильно больше чем требуется |
| − | * Несколько корзин на одной странице | + | * Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу |
** Обычно - последовательных | ** Обычно - последовательных | ||
** Разделение корзин при переполнении страницы | ** Разделение корзин при переполнении страницы | ||
* Не работает при плохой хеш-функции, но у нас хорошая | * Не работает при плохой хеш-функции, но у нас хорошая | ||
| + | |||
| + | При переполнении страницы мы: | ||
| + | * разделяем ее на несколько страниц | ||
| + | * разделим страницы, которые на нее ссылались, на несколько групп | ||
| + | * Каждой такой группе выделим по странице | ||
| + | |||
| + | Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2) | ||
[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]] | [[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]] | ||
| + | |||
| + | === Побитное расширяемое хеширование | ||
| + | |||
| + | *Глубина хеша $n$ | ||
| + | ** Создадим $2^n$ корзин | ||
| + | * Для каждой страницы хранится ее локальная глубина $k$ | ||
| + | ** Это значит что она хранит $2^{n−k} последовательных корзин на странице | ||
| + | ** Может быть разной для разных страниц | ||
| + | * При переполнении происходит разделение корзин | ||
| + | ** Страница глубины $k$ разделяется на две глубины $k+1$ | ||
Версия 04:42, 20 декабря 2021
Содержание
Индексы
Индексы нужны для того, чтобы оптимально искать нужные записи в таблице.
Всего есть два способа найти нужные данные:
- Полный просмотр таблицы
- Последовательный перебор записей
- Быстро работает на маленьких таблицах, но медленно на средних и больших
- Если выбираем большую часть данных, то работает быстро. Иначе - медленно
- Индекс
- Произвольный набор столбцов
- Требуется предварительная обработка таблицы как при построении, так и при обновлении
- Быстрый поиск в индексе, сразу получаем указатель на запись
Кластеризованный индекс
Если данные в таблице хранятся в порядке индекса, то такой индекс называется кластеризованным. Кластеризованный индекс позволяет увеличить скорость просмотра, однако так хранить данные возможно только если в таблице есть всего один индекс.
Структура Индекса
В общем случае индексы хранят отображение из ключей на идентификаторы записей, которые ведут на записи, которые мы загружаем
Есть два подхода к реализации индексов:
- Хеш-таблицы
- Деревья поиска
Хеш-индексы
- Предварительная обработка
- Подсчет хешей ключей. Хеш-функция задается разработчиком СУБД, что дает нам гарантии хорошего статистического распределения.
- Разбиение на корзины
- Поиск в индексе
- Просмотр корзины
- Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
- Заголовок помещяется в памяти
Однако может наступить момент, когда очередная корзина не помещается в страницу, в таком случае мы так же храним их цепочками.
- Так как хеш-функция хорошая, то в цепочке только полезные данные
- Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.
При этом получаем
- Линейное время поиска
- В случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго
Расширяемое хеширование
- Большое количество корзин, сильно больше чем требуется
- Несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницу
- Обычно - последовательных
- Разделение корзин при переполнении страницы
- Не работает при плохой хеш-функции, но у нас хорошая
При переполнении страницы мы:
- разделяем ее на несколько страниц
- разделим страницы, которые на нее ссылались, на несколько групп
- Каждой такой группе выделим по странице
Стоимость - 1 чтение и запись стольких страниц, на сколько мы разделили (обычно 2)
=== Побитное расширяемое хеширование
- Глубина хеша $n$
- Создадим $2^n$ корзин
- Для каждой страницы хранится ее локальная глубина $k$
- Это значит что она хранит $2^{n−k} последовательных корзин на странице
- Может быть разной для разных страниц
- При переполнении происходит разделение корзин
- Страница глубины $k$ разделяется на две глубины $k+1$
