Файлы поисковых структур

Из множества поисковых структур чаще всего используют линейные и цепные списки, инвертированные и индексные файлы.

Линейный список: прост в реализации, не требует создания дополнительных файлов (то есть минимум памяти), но низкое быстродействие. При этом файл БД рассматривается как последовательность невзаимосвязанных записей. Поиск осуществляется путем вычисления адреса нужной записи.

Цепной список: требует дополнительных затрат памяти, но обладает более высоким быстродействием. В каждой записи, кроме информативных полей, выделяется дополнительное поле, называемое адресом связи. В эти поля заносятся ссылки (указатели) на другие записи. Таким образом можно установить произвольный порядок выборки записей.

Инвертированный список: обеспечивает самый быстрый поиск данных, однако приводит к большим затратам памяти, так как требует создания копий основного файла базы данных, в котором записи упорядочены по не ключевому параметру.

Индексный файл: обладает тем же быстродействием, что и инвертированный список, но требует значительно меньше памяти, так как вместо данных хранятся их адреса.

Применение индексных файлов приводит к следующей структуре базы данных, где ОФБД – это основной файл базы данных, ИФ – индексный файл:

БД = {ОФБД, ИФ1, ИФ2, …, ИФn}, n <= число атрибутов.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВИДЫ ОБЕСПЕЧЕНИЯ САПР

 

 

Hosted by uCoz