Построение индексных структур для ключевых характеристик объектов
Цель работы Изучение логической организации индексов, как основных функциональных структур, оптимизирующих процессы поиска информации
Идентификация объектов и записей Информация Запись Значение Объект ПрО Свойство Данные Элементы данных
Поиск записей Прикладная программа задать машинный адрес данных и в соответствии с физическим форматом записи прочитать значение сообщить системе имя записи или элемента данных и, возможно, организацию набора данных Информация о структуре данных и организации набора
112 а/м ВАЗ 2110… 113 а/м ВАЗ 2121… 441 а/м ГАЗ 3110… 456 а/м ВАЗ 2110… 457 а/м ВАЗ 2121… 678 а/м ВАЗ 2101… 789 а/м ГАЗ 3110… 889 а/м ВАЗ 2110… 998 а/м ГАЗ 3102… Первичный (главный) - ключ, который идентифицирует запись единственным образом Вторичный (альтернативный) – ключ, идентифицирующий некоторую группу записей, имеющих определенное общее свойство
Индекс – физическая реализация ключа – обеспечивает доступ к записям, ассоциированным с отдельным значением ключа 678 а/м ВАЗ а/м ВАЗ а/м ВАЗ а/м ВАЗ а/м ВАЗ а/м ВАЗ а/м ГАЗ а/м ГАЗ а/м ГАЗ 3110 а/м ВАЗ а/м ВАЗ , 456, 889 а/м ВАЗ , 457 а/м ГАЗ а/м ГАЗ , 789 Прямая форма индекса Инвертированная форма индекса
Типология простых (атомарных) запросов А(Е) = ?Каково значение атрибута А для объекта Е? А(?) = VКакие объекты имеют значение атрибута равное V? ?(Е) = VКакие атрибуты объекта Е имеют значение равное V? ?(Е) = ?Какие значения атрибутов имеет объект Е? А(?) = ?Какие значения имеет атрибут А в наборе? ?(?) = VКакие атрибуты объектов набора имеют значение равное V?
Типы архитектур доступа к записям Системы с вторичными индексами: последовательность расположения записей соответствует последовательности значений первичного ключа. Как правило, используется один первичный индекс и несколько вторичных. Системы частично инвертированных файлов: записи могут располагаться в произвольной последовательности; первичный индекс отсутствует; вторичные индексы применяются и для прямой адресации записей. Системы полностью инвертированных файлов: предусмотрено наличие файлов, содержащих значения отдельных элементов данных, входящих в состав записей. Для ускорения процесса поиска в системе используют два набора индексов: индекс экземпляров (значений ключей) и индекс данных (инвертированный список). С помощью индекса экземпляров можно найти в файле элементы данных, имеющих заданное значение. С помощью индекса данных можно найти записи, связанные с заданными значениями элементов.