Викиконспекты - Вклад участника [ru]

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

2021-12-27T10:12:55Z

91.143.51.202: /* Упорядоченные индексы */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

При переполнении страницы мы:
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
* Каждой такой группе выделим по странице

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты, то есть даны все столбцы, которые есть в хеш-индексе. Иначе индек не поможет, так как нет способа перебрать все варианты
**''exist'' - только если есть все необходимые атрибуты, анологично с ''in''
**''count'' - при запросе ''count*'' зачастую можно посчитать по индексу количество записей с определенным набором стобцов, не обращаясь к самим записям, что дает существенный выигрыш по премени
*Поиск по ключу
**Естественные соединения. Если есть идентификатор, по этому идентификатору есть хеш-индекс, это, в свою очередь, позволяет быстро найти запись.

== Упорядоченные индексы ==

Традиционно реализуются на деревьях поиска

* Предварительная обработка
** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое упорядочивание, после упорядочиваем по возрастанию и строим поверх этого дерево поиска
* Поиск в индексе
** Ищем данные в дереве поиска. Используемое дерево поиска должно поддерживать операции вставки, удаления и поиска

Деревья поиска
* Количество операций обычно пропорционально $O$(высоты). Так как время выполнение операций зависит от высоты дерева, для оптимизации времени нужно минимизировать высоту
* Размер узла
** Хотим эффективно использовать страницы
** Используем сильно ветвящиеся деревья. Так размер узла будет примерно равен странице и высота дерева будет минимальной

=== $B$ и $B+$ деревья ===

Обычно в качестве сильно ветвящихся деревьев поиска берут $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''

[[Категория: Базы данных]]

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

2021-12-27T09:52:27Z

91.143.51.202: /* Ускоряемые запросы */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

При переполнении страницы мы:
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
* Каждой такой группе выделим по странице

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

=== Побитное расширяемое хеширование ===
Заранее сделаем заголовок большого размера.
* Глубина хеша $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''

[[Категория: Базы данных]]

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

2021-12-27T09:46:59Z

91.143.51.202: /* Побитное расширяемое хеширование */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

При переполнении страницы мы:
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
* Каждой такой группе выделим по странице

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:43:05Z

91.143.51.202: /* Расширяемое хеширование */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

При переполнении страницы мы:
* разделяем ее на несколько страниц
* разделим страницы, которые на нее ссылались, на несколько групп
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
* Каждой такой группе выделим по странице

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:38:19Z

91.143.51.202: /* Хеш-индексы */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

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

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

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:28:34Z

91.143.51.202: /* Хеш-индексы */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

== Хеш-индексы ==

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

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

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

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

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:21:00Z

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

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

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

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

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:14:56Z

91.143.51.202: /* Индексы */

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

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

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

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]

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

2021-12-27T09:08:30Z

91.143.51.202:

== Индексы ==

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

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

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

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

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

[[Файл:Index_Clustered.png|мини|Кластеризованный индекс]]

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

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

[[Файл:Index_Structure.png|мини|Структура индекса]]

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

Есть два подхода к реализации индексов:
* Хеш-таблицы
* Деревья поиска

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

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

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

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

[[Файл:Index_Hash_Sequence.png|мини|Цепочки страниц]]

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

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

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

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

[[Файл:Index_Hash_Extendable.png|мини|Расширяемое хеширование]]

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

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

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

*Проверка существования ключа
**Проверка повторений (ключи)
**''in'' - только если есть все необходимые атрибуты
**''exist'' - только если есть все необходимые атрибуты
**''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''

[[Категория: Базы данных]]