Изменения

** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастаниеупорядочивание, после упорядочиваем по возрастанию и строим поверх этого дерево поиска

** Поиск Ищем данные в упорядоченной последовательностидереве поиска. Используемое дерево поиска должно поддерживать операции вставки, удаления и поиска

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

** Сильно Используем сильно ветвящиеся деревья, так . Так размер узла будет ~примерно равен странице и высота дерева будет минимальной

** От В каждом узле от $\frac{n}{2}$ до n детей

* $B+$ на одну страницу глубже, а это значит что больше образений к листу.

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

* Плотный индекс** Храним ключи всех элементов* Разряженные индекс** Храним ключи части элементов** Обычно – один на страницу, мы можем найти данные в рамках этой страницы без загрузки новых** Разряженный индекс бычно используется для кластеризованных индексов** Уменьшает число уровней Так как упорядоченных упорядоченный индекс хранит сами данные в узлах, а не только хеш, то чем больше индексируеммые данные, тем меньше степень ветвления, тем больше высота дерева.Поэтому в упорядоченных индексах, в отличии от хеш-индексов, нужно обращать внимание на то, что является индексом:

*Строки- часто бывают большие, нужно очень аккуратно**Много данных в ключе – меньше степень ветвления**Можно Если есть последовательно упорядоченные строки, то можно использовать префиксы**Строки опасно использовать в качестве индекса, может сильно вырости высота дереваоптимизируя размер индекса*Суррогатные ключи**Малый . Обычно имеют малый размер**Выше эффективность**Широкие , поэтому получается низкое и широкое дерево поиска, что нам и низкие деревья - хорошонужно*Изменяющиеся данные. При изменении данных нужно перестраивать дерево, это не эффективно**Частое обновление индекса**Уменьшение индекса**Не эффективноИндексы часто не умеют уменьшаться~--- удаление данных не приводит к уменьшению дерева. Подразумевается, для уменьшения данных нужна что запускается отдельная таскапрограмма, которая перестраивает индексы

* Минимум и максимум среди значений, на которых построен ключ, в хеш-таблицах этого нет* Диапазон Можно реализовать поиск в диапазоне** ЗагрузкаВ хеш-индексах единственный способ - перебрать всю таблицу, поэтому обчно так не делают. А в упорядоченных нет с этим проблем, если все необходимые столбцы входят в ключ** ''count''. count * работает быстроеебыстрее, так как не нужно идти по всем данным* Если построен на строках, ''like '', но только по префиксу