Организация данных во внешней памяти ЭВМ

Сравнение методов организации данных

В табл. 3 собраны все оценки методов организации дан­ных, что позволяет сделать ряд выводов.

Таблица 3. Сравнение методов организации данных

Критерии оценки	Методы организации данных	Лучший метод
Последова­тельный	Цепной	бинарное дерево
Время формирования	-MlogM	-MiogM	-MiogM	Цепной, бинарное дерево
Время поиска	-logM	-М	-logM	Последовательный, бинарное дерево
Время корректировки	-М	--М	-logM	Бинарное дерево
Объем дополнительной памяти		-М	-М	Последовательный

Это объясняется необходимостью пересылки записей в про­цессе сортировки последовательного массива, а в цепном ка­талоге и бинарном дереве при формировании пересылаются адреса связи, а не целые записи.

По времени поиска последовательный массив и бинарное дерево предпочтительнее цепного каталога. Минимальное время корректировки характерно для бинарного дерева, а минимальный объем дополнительной памяти - для последо­вательного массива.

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

Следует отметить, что для последовательной и цепной орга­низации данных разработаны методы ускорения поиска, которые не применимы к деревьям. Это в ряде случаев создает преимущества для пос­ледовательных массивов перед деревьями.

Ускорение доступа к данным осуществляться в результате вычисления местоположения требуемой записи. Сами записи могут быть упорядочены алгоритмом сортиров­ки либо используется специальная расстановка записей.

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

Данные на внешнем запоминающем устройстве хранятся в виде файлов. Файл представляет собой множество логически связанных записей. Запись обычно соответствует одному зна­чению некоторой составной единицы информации. Каждый файл имеет уникальное имя файла. В простейшем случае файл представляет последовательный массив записей на внешнем запоминающем устройстве. Вся внешняя память разделена на блоки или секторы и обмен с оперативной памятью происходит только целыми секторами.

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

Вопросы для самоконтроля к главе 3

1. По каким критериям производится анализ эффективности методов обработки данных?

2.Каково количество вариантов возможных состояний неупорядоченного массива из М записей?

3.Что означает процедура формирования данных?

4.Что означает процедура поиска?

5.Какими методами ускоряется поиск в упорядоченном последовательном массиве?

6.Что означает процедура корректировки данных?

7.Как осуществляется последовательность обработки данных при цепной организации данных?

8.Какими методами можно ускорить поиск при цепной организации данных?

9.Что такое цепной каталог?

10.Почему бинарный метод поиска не эффективен для цепной организации данных?

11.Как осуществляется связь между записями при древовидной организации данных?

12.Как осуществляется упорядоченность записей в бинарном дереве?

13.Как осуществляется поиск данных в бинарном дереве?

14.Какой метод требует минимальный объем памяти?

15.Какой метод считается предпочтительным?

Глава 4. Моделирование предметных областей в экономике.

Базы знаний

Дата добавления: 2014-01-05