Механизмы поиска в БД Структуры индексов

Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов 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)Каждый сегмент содержит возможность для создания блока переполнения

Динамические хеш-таблицы Расширяемые хеш-таблицы Линейные хеш-таблицы

Количество сегментов линейной хеш-таблицы (n) всегда выбирается так, чтобы отношение среднего числа записей в блоке к максимально допустимому оставалось постоянным (например 80%) Допустимо применять блоки переполнения, но их число, отнесенное к общему числу сегментов должно быть существенно меньше единицы Количество битов, используемых для нумерации элементов массива сегментов (i) составляет log 2 n. Биты выбираются из младших разрядов двоичного представления числа, возвращаемого хеш-функцией (h(K)) Выбор сегмента для размещения ссылки на запись с ключом K осуществляется следующим образом: если число m образуемое младшими i битами h(K) < n, то запись кладется в сегмент с соответствующим номером. Иначе в двоичном представлении числа m заменяем старшие биты на 0 до тех пор, пока это условие не выполнится. Полученное в результате число и есть номер сегмента, куда надо распределить запись.

Примеры i = 1; n = 2; r = 3 i = 2; n = 3; r =

Примеры i = 2; n = 3; r = 5 i = 1; n = 2; r =

Примеры i = 2; n = 3; r = i = 2; n = 4; r = Блок переполнения