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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 37: Строка 37:
 
** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
 
** Несколько ключей в корзине. Коллизии могут быть, так как индекс не всегда ключ.
 
* Заголовок помещяется в памяти
 
* Заголовок помещяется в памяти
[[Файл:Index_Hash_Simple.jpg|мини|Простой хеш-индекс]]
+
[[Файл: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$