Методы адресации данных по первичному ключу

Вопрос №13

Представление древовидных и сетевых структур в памяти ЭВМ.

В древовидных структурах реализуется след. методы:

а)физическое последовательное размещение(метод левосписковых структур)

б)связанное размещение(указатели, цепи и кольца в справочнике)

в)битовое отображение.

1) Метод левосписковых структур:

2) Метод указателей:

а) метод указателей на порожденные узлы

б) метод указателей на исходные записи

в) метод указателей на порожденные и исходные узлы

г) указатели на порожденные и подобные записи

д) метод указателей на порожденные, подобные и исходные

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

Таким образом, скорость поиска данных и их обработки значительно повышаются.

3) Битовое отображение связей: он фиксирует связи, заполняет единицами при наличии связи и нулями при отсутствии связи в клетки таблицы.

Вопрос №14

Методы адресации данных по первичному ключу.

1)Последовательное сканирование файла(поиск) он заключается в последовательной проверке всех записей на соответствие некоторому условию поиска Q.

Записи, удовлетворяющие этому условию, выдаются в качестве результата.

Существуют различные виды поиска:

а)поиск по равенству К=а

б)поиск по интервалу значений а К b

в)поиск по множеству значений К=a_i, i=1…n

2)Блочный поиск.

предполагает просмотр каждой, например, сотой записи последовательности возрастания ключей. При нахождении записи с ключом больше, чем ключ, используемый при поиске, просматриваются последние 99 записей, которые были пропущены. Таким образом, записи группируются в блоки и каждый блок проверяется 1 раз, пока не будет найден нужный блок.

3)Бинарный поиск

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

4)Поиск по бинарному дереву.

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

5)Индексно-последовательный файл(неплотный индекс)

Основной файл F упорядочен по ключу. На его основе строится новый файл FB, в котором все записи упорядочены по ключу и формат записи этого файла имеет вид (к,р’), где К- поле, принимающее значение ключа 1-ой записи блока основного файла F, р- указатель на этот блок. Полученный файл называют неплотным индексом.

Например:

6)Индексно-произвольный файл(плотный индекс)

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