1632
правки
Изменения
м
* Большое Изначально создаем большое количество корзин, сильно больше чем требуется* Несколько . Пока мало данных Храним несколько корзин на одной странице, чтобы не аллоцировать для каждой корзины страницупо отдельной странице.** Обычно - последовательныхвыбираем набор корзин, которые идут подряд** Разделение корзин при При переполнении страницы разделенем корзины на две страницы
Стоимость: $1$ чтение и запись стольких страниц, на сколько мы разделили (обычно $2$)
*Глубина хеша $n$** Создадим $2^n$ корзин* Для каждой страницы хранится ее локальная глубина $k$** Это значит что она хранит $2^{n−k}$ последовательных корзин на странице** Может быть разной для разных Есть точные гарантии по производительности~--- все наши затраты измеряются единицами страниц* При переполнении происходит разделение корзин** Страница глубины $k$ разделяется на две глубины $k+1$.
* Плотный индекс** Храним ключи всех элементов* Разряженные индекс** Храним ключи части элементов** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых** Разряженный индекс бычно используется для кластеризованных индексов** Уменьшает число уровней Так как упорядоченных упорядоченный индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления, тем больше высота дерева.Поэтому в упорядоченных индексах, в отличии от хеш-индексов, нужно обращать внимание на то, что является индексом:
rollbackEdits.php mass rollback
* Если цепочка длинная, значит этому набору столбцов соответствует много строк, значит база данных так и задумывалась.
При этом получаем* Линейное линейное время поиска* В Но в случае, если данных много, мы не можем просто увеличить число корзин и перенести данные, так как перехешировать таблицу очень долго
[[Файл: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*'' зачастую можно посчитать по индексу countколичество записей с определенным набором стобцов, не обращаясь к самим записям, что дает существенный выигрыш по премени
*Поиск по ключу
**Естественные соединения. Если есть идентификатор, по этому идентификатору есть хеш-индекс, это, в свою очередь, позволяет быстро найти запись.
== Упорядоченные индексы ==
* Предварительная обработка
** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастаниеупорядочивание, после упорядочиваем по возрастанию и строим поверх этого дерево поиска
* Поиск в индексе
** Поиск Ищем данные в упорядоченной последовательностидереве поиска. Используемое дерево поиска должно поддерживать операции вставки, удаления и поиска
Деревья поиска
* Количество операций** Обычно обычно пропорционально $O$(высоты)** . Так как время выполнение операций зависит от высотыдерева, для оптимизации времени нужно минимизировать высоту
* Размер узла
** Хотим эффективно использовать страницы
** Сильно Используем сильно ветвящиеся деревья, так . Так размер узла будет ~примерно равен странице и высота дерева будет минимальной
=== $B$ и $B+$ деревья ===
Обычно в качестве сильно ветвящихся деревьев поиска берут $B$ и $B+$ деревья и их разновидности.
* $B$ деревья степени $n$
** От В каждом узле от $\frac{n}{2}$ до n детей
** Указатели и ключи хранятся в узлах
* $B+$ деревья степени $n$
* $B+$ меньше данных в узлах - сильнее ветвятся
* $B+$ на одну страницу глубже, а это значит что больше образений к листу.
Мы храним корень и несколько первых уровней в памяти для быстрого обращения, из-за этого время работы может резко возрастать, когда заканчивается закешированные уровни.Поэтому даже один лишний уровень в дереве может значительно увеличить время исполнения
=== Плотные и разряженные индексы ===
Индексы также делятся на плотные и разряженные
* Плотный индекс. Храним ключи всех элементов подряд
* Разряженные индекс. Храним ключи части элементов
** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых. Разряженный индекс бычно используется для кластеризованных индексов
** Уменьшает число уровней так как храним меньше индексов. Вспоминая что даже один уровень может повысить количество загрузок в два раза, понимаем что разряженные индексы могут сильно оптимизировать базу данных
*Строки- часто бывают большие, нужно очень аккуратно**Много данных в ключе – меньше степень ветвления**Можно Если есть последовательно упорядоченные строки, то можно использовать префиксы**Строки опасно использовать в качестве индекса, может сильно вырости высота дереваоптимизируя размер индекса*Суррогатные ключи**Малый . Обычно имеют малый размер**Выше эффективность**Широкие , поэтому получается низкое и широкое дерево поиска, что нам и низкие деревья - хорошонужно*Изменяющиеся данные. При изменении данных нужно перестраивать дерево, это не эффективно**Частое обновление индекса**Уменьшение индекса**Не эффективноИндексы часто не умеют уменьшаться~--- удаление данных не приводит к уменьшению дерева. Подразумевается, для уменьшения данных нужна что запускается отдельная таскапрограмма, которая перестраивает индексы
* Проверка существования ключа
* Поиск по ключу
* Минимум и максимум среди значений, на которых построен ключ, в хеш-таблицах этого нет* Диапазон Можно реализовать поиск в диапазоне** ЗагрузкаВ хеш-индексах единственный способ - перебрать всю таблицу, поэтому обчно так не делают. А в упорядоченных нет с этим проблем, если все необходимые столбцы входят в ключ** ''count''. count * работает быстроеебыстрее, так как не нужно идти по всем данным* Если построен на строках, ''like '', но только по префиксу
==Литература==
