Механизмы поиска в БД Структуры индексов
Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов B-деревья (B+-деревья) Хэш-таблицы
Индексы для последовательных файлов Плотный индекс - Размер файла индекса значительно меньше - Возможность бинарного поиска - Есть вероятность загрузки индекса в память Разреженный индекс
Более сложные варианты Многоуровневый индекс Индексы для файлов с дубликатами ключей –Плотный с дублированием –Плотный –Разреженный с наименьшими значениями –Разреженный с наименьшими новыми значениями
Операции с индексами Удаление –Может быть модифицировано путем добавления мертвых записей, остающихся на месте удаленных Вставка –Может быть модифицирована путем использования блоков переполнения
Вторичные индексы Плотный вторичный индекс Двухуровневый плотный индекс Многоуровневые
В-деревья Классическое B-дерево порядка 2
Поиск в B-дереве 1.Если в считанной странице обнаруживается пара ключей ki и k(i+1) такая, что ki < K < k(i+1), то поиск продолжается на странице pi. 2.Если обнаруживается, что K > km, то поиск продолжается на странице pm. 3.Если обнаруживается, что K < k1, то поиск продолжается на странице p0.
Вставка в B-дерево Пытаемся вставить: Вставка путем расщепления страницы A
Исключение из B-дерева До удаления После удаления 25
Исключение с переливанием ключей До удаления После удаления 38
Исключение со слиянием страниц До удаления После удаления 29
B+ деревья 1). Не листовые вершины содержат только ключи и ссылки на дочерние страницы. 2). Листовые вершины содержат все множество ключей отношения, сами указатели на записи, плюс указатель на следующий по порядку лист. 3). Ключи в листовых вершинах отсортированы по возрастанию.
Эффективность B+ деревьев Возьмем значение блока равным 4096 байт (что часто встречается на практике). Пусть указатель занимает 8 байт, а ключ 4. Тогда блок вмещает максимум 340 индексов. Кол-во индексов в блоке в среднем = 255. Тогда дерево глубиной в 3 уровня может адресовать записей ( ).
Хэш-таблицы Хэш-функция вычисляет по ключу номер сегмента, где должна быть размещена запись. Особенности хэш-функций для внешней памяти: 1)В роли сегментов выступают блоки 2)Каждый сегмент содержит возможность для создания блока переполнения
Динамические хэш-таблицы Расширяемые хэш-таблицы Линейные хэш-таблицы