Механизмы поиска в БД Структуры индексов. Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов. - презентация

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

2 Основные виды индексов Простые индексы для упорядоченных файлов Вторичные индексы для неупорядоченных файлов B-деревья (B+-деревья) Хэш-таблицы

3 Индексы для последовательных файлов Плотный индекс - Размер файла индекса значительно меньше - Возможность бинарного поиска - Есть вероятность загрузки индекса в память Разреженный индекс

4 Более сложные варианты Многоуровневый индекс Индексы для файлов с дубликатами ключей –Плотный с дублированием –Плотный –Разреженный с наименьшими значениями –Разреженный с наименьшими новыми значениями

5 Операции с индексами Удаление –Может быть модифицировано путем добавления мертвых записей, остающихся на месте удаленных Вставка –Может быть модифицирована путем использования блоков переполнения

6 Вторичные индексы Плотный вторичный индекс Двухуровневый плотный индекс Многоуровневые

7 В-деревья Классическое B-дерево порядка 2

8 Поиск в B-дереве 1.Если в считанной странице обнаруживается пара ключей ki и k(i+1) такая, что ki < K < k(i+1), то поиск продолжается на странице pi. 2.Если обнаруживается, что K > km, то поиск продолжается на странице pm. 3.Если обнаруживается, что K < k1, то поиск продолжается на странице p0.

9 Вставка в B-дерево Пытаемся вставить: Вставка путем расщепления страницы A

10 Исключение из B-дерева До удаления После удаления 25

11 Исключение с переливанием ключей До удаления После удаления 38

12 Исключение со слиянием страниц До удаления После удаления 29

13 B+ деревья 1). Не листовые вершины содержат только ключи и ссылки на дочерние страницы. 2). Листовые вершины содержат все множество ключей отношения, сами указатели на записи, плюс указатель на следующий по порядку лист. 3). Ключи в листовых вершинах отсортированы по возрастанию.

14 Эффективность B+ деревьев Возьмем значение блока равным 4096 байт (что часто встречается на практике). Пусть указатель занимает 8 байт, а ключ 4. Тогда блок вмещает максимум 340 индексов. Кол-во индексов в блоке в среднем = 255. Тогда дерево глубиной в 3 уровня может адресовать записей ( ).

15 Хэш-таблицы Хэш-функция вычисляет по ключу номер сегмента, где должна быть размещена запись. Особенности хэш-функций для внешней памяти: 1)В роли сегментов выступают блоки 2)Каждый сегмент содержит возможность для создания блока переполнения

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