Тема 3. Индексирование.
Главная цель – ускорение поиска кортежей отношения, удовлетворяющих некоторым условиям (заданное значение ключа).
Индексно-последовательные файлы.
Файл данных должен быть отсортирован по атрибуту индекса.
Плотный индекс – одна запись индексного файла соответствует одному кортежу файла данных.
Разреженный индекс – одна запись индексного файла соответствует одному блоку файла данных.
Многоуровневые индексы – индексы, построенные для файлов индексов.
Дублирующие значения ключа.
Простейший подход – плотный индекс (дублирующие значения ключа в индексном файле).
1 способ – индекс содержит по одной записи для каждого ключевого значения, которая указывает на первый кортеж файла данных с таким значением ключевого атрибута (остальные находятся путем просмотра файла данных, начиная с записи, полученной с помощью индекса).
2 способ – разреженный индекс, каждая запись индекса соответствует первому ключевому значению каждого блока данных.
3 способ – разреженный индекс, запись индекса хранит первое новое ключевое значение каждого блока (если такого нет, то хранится единственное ключевое значение, встречающееся в этом блоке)
Изменения в индексах при модификации файла данных.
Стратегии:
Создание блоков переполнения файла данных. Вставка нового блока в файл данных (внутрь связанного списка блоков файла). Перемещение кортежей в смежные блоки.Возможны 7 основных действий с файлами данных:
Действие | Плотный индекс | Разреженный индекс |
Создание пустого блока переполнения | Ничего не делать | Ничего не делать |
Удаление пустого блока переполнения | Ничего не делать | Ничего не делать |
Создание пустого блока файла данных | Ничего не делать | Вставка записи о блоке |
Удаление пустого блока файла данных | Ничего не делать | Удалить запись о блоке |
Вставка записи | Вставка | Возможно изменение |
Удаление записи | Удаление | Возможно изменение |
Перемещение записи | Изменение | Возможно изменение |
Удаление записи из файла.
1. Удаление записи из файла с плотным индексом.
Дано:
| Удаление записи с ключом 30 (есть указатели на записи файла извне)
|
2. Удаление записи из файла с разреженным индексом.
Дано:
Удаление записи с ключом 30 (указателей на записи вовне нет)
Удаление записи с ключом 40.
Вставка записи в файл с разреженным индексом.
Дано:
Вставка записи с ключом 15 (если есть возможность перемещение записей).
Вставка в исходный файл записи с ключом 25 (использование блоков переполнения).
Вторичные индексы – индекс, построенный не по ключевому атрибуту отношения (сортировка в файле осуществляется по другому атрибуту)
Повторение ключей во вторичных индексах (появляется промежуточный уровень адресации - сегменты).
Использование вторичных индексов, если указаны два условия отбора – пересечение указателей, из сегментов двух вторичных индексов (читаются только записи файла данных, удовлетворяющие обоим условиям).
Например, найти все кинофильмы, снятые на киностудии “Disn” в 1995 году.
Инвентированные индексы – индексы, используемые в информационно-поисковых системах для поиска документов по ключевым словам.
Документ – отношение Doc(hasCat, hasDog….). Каждый атрибут отношения – булево значение, равное true, если соответствующее слово присутствует в документе.
Определен вторичный индекс по ключевым словам, сегменты которого содержат только ссылки на документы, в которых слово есть (или позицию в документе заданного слова).
