21
правка
Изменения
Нет описания правки
*Поиск по ключу
**Естественные соединения
== Упорядоченные индексы ==
Традиционно реализуются на деревьях поиска
* Предварительная обработка
** Ключи упорядочиваются по возрастанию - так как ключ составной, то используем лексикографисечкое возрастание
* Поиск в индексе
** Поиск в упорядоченной последовательности
Деревья поиска
* Количество операций
** Обычно пропорционально O(высоты)
** Минимизировать высоту
* Размер узла
** Хотим эффективно использовать страницы
** Сильно ветвящиеся деревья, так размер узла будет ~странице и высота будет минимальной
=== B и B+ деревья ===
* $B$ деревья степени $n$
** От $\frac{n}{2}$ до n детей
** Указатели и ключи хранятся в узлах
* $B+$ деревья степени $n$
** От $\frac{n}{2}$ до n детей
** Указатели хранятся в листьях
* B+ меньше данных в узлах - сильнее ветвятся
* B+ на одну страницу глубже
Мы храним корень и несколько первых уровней в памяти для быстрого обращения
