Petrova

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

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

Критерии	Методы организации данных			Лучший метод
оценки	последователь-	цепной	Дерево
	ный
Время	~М log М	~ М log М	~ M log M	цепной,
формирования				бинарное дерево
Время поиска	~ log M	~ М	~ log M	последовательный,
				бинарное дерево
Время	~ М	~ М	~ log М	бинарное дерево
корректировки
Объем	0	~ М	~ М	последовательный
дополнительной
памяти

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

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

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

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

3.2. Методы ускорения доступа к данным

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

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

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

Адресная функция

Расстановка записей происходит в соответствии с так называемой адресной функцией (другие общеупотребительные ее названия - "рандомизирующая функция" и "хэш-функция"). Применяемые при этом методы организации данных часто называются методами рандомизации.

Адресной функцией называется зависимость

I = f(p),

где i - номер (адрес) записи;

р - значение ключевого атрибута в записи.

Адресная функция может вырабатывать одинаковое значение i для значений р, принадлежащих разным записям, которые в этом случае называются синонимами. К функции f предъявляются следующие требования:

•она должна быть задана аналитически и вычисляться достаточно быстро;

•ключевые атрибуты, подчиняющиеся произвольному распределению, функция должна переработать в равномерно распределенные номера записей; это условие обычно соблюдается приближенно;

•число записей-синонимов должно составлять 10-20% от общего числа записей.

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

i = р - а,

где а - константа.

Пусть известны минимальное значение ключевого атрибута в массиве р' и максимальное значение р" . Тогда а = р' - 1. Необходимый участок памяти для данных оценивается в р" - р' + 1 запись. Записи-синонимы связываются в цепочки с помощью адресов связи, они занимают дополнительную (резервную) память.

Пример размещения записей с ключами 13, 11, 14, 11, 15, 18, 14, 16 согласно адресной функции i = р - а показан на рис. 3.9.

Рис. 3.9. Организация записей в соответствии с адресной функцией i = р - а

При доступе к записи с ключом q вычисляется i = f(q) и производится обращение к i-й записи. При необходимости с помощью адресов связи извлекаются все синонимы.

Недостаток адресной функции вида i = р - а - большой объем неиспользуемой памяти, если р" - р' много больше, чем количество записей М.

Указанного недостатка лишена функция вида

I = OCT(p/m).

Здесь m - целое число; ОСТ - остаток от деления р на m.

Вычисление i на языке Паскаль производится с помощью оператора i: = p mod m.

Значение m принимается равным простому числу, которое непосредственно больше либо непосредственно меньше числа записей М.

Выделяются 2 зоны памяти - основная и резервная. Основная зона содержит m записей. Резервная зона предназначена для размещения записейсинонимов.

Рис. 3.10. Организация записей в соответствии с адресной функцией i = ОСТ (р/m)

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

Например, для массива ключей со значениями 17, 9, 4, 14, 25, 21, 20, 11 необходимо выбрать m = 7, поскольку М = 8 (возможно также m = 19). Содержимое основной и резервной зон иллюстрирует рис.3.10. Резервная зона заполняется последовательно. При поиске значения, например q = 11, вычисляется i = ОСТ(11/7) = 4, и далее последовательно сравниваются 4 и 11, 25 и 11 и т. д. В рассматриваемом примере число записей-синонимов составляет 3/8.

Индексы

Для ускорения поиска записей в массиве используется дополнительная информация, организованная в виде массива индексов.

Индексом называется набор ключей и адресов записей, которые выбираются из основного массива по определенному закону. Отдельный элемент набора индексов также называется индексом, хотя это не соответствует значению слова index -список.

Имеются три важные разновидности индексов:

•информация о каждой записи основного массива попадает в индекс (сплошная индексация);

•номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d > 1. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным;

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

Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Этот случай уже рассмотрен в п. 2.4.

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

В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. На рис. 3.11 показаны ключевые атрибуты основного массива и состояние массива индексов для d = 3.

Рис. 3.11. Индексно-последовательная организация данных

Поиск значения q в индексно-последовательном массиве происходит в две стадии:

•в массиве индексов (который отсортирован в силу упорядоченности основного массива);

•среди записей основного массива, расположенных между двумя

соседними индексами, найденными на первой стадии. Применение индексов приводит к ускорению доступа, если основной

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

Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию, мы получаем ситуацию с адресной функцией для индекса (рандомизация индекса).

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

p(l) + z(n-1),

где z - константа (шаг арифметической прогрессии); р(1) - значение; ключа первой записи основного массива.

На рис. 3.12 показаны ключевые атрибуты основного массива (идентичные с предыдущим примером) и состояние массива рандомизированных индексов для z = 10. Примечательно, что значения ключей в таком индексе хранить не нужно.

Рис. 3.12. Рандомизация индекса

Рассмотрим поиск с использованием рандомизированных индексов. На первой стадии номер требуемого далее индекса определяется по формуле

Результат деления округляется в меньшую сторону. Интервал записей основного массива на второй стадии поиска определяется адресами, указанными в n-м и (n+1)-м индексах.

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

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

Пример

Рассмотрим записи с четырьмя атрибутами в порядке старшинства слева направо А1, А2, A3, А4. Значения А1 упорядочены (для примера) по возрастанию. На каждом множестве записей, которые соответствуют одинаковому значению А1, реализована упорядоченность по возрастанию значений А2 для записей, у которых значение А1 одинаково. Далее, на каждом множестве записей с одинаковыми парами значений атрибутов А1 и А2 соблюдается упорядоченность значений по атрибуту A3. И, наконец, на каждом множестве записей с одинаковыми значениями атрибутов А1, А2, A3 должна соблюдаться упорядоченность по возрастанию для атрибута А4.

Последовательный массив с такой упорядоченностью может обеспечивать быстрый доступ к данным по следующим сочетаниям ключевых атрибутов а1+а2+а3+а4, а1+а2+а3, а1+а2 и а1.

Количество сочетаний атрибутов, необходимых для реализации максимально широкого круга запросов, в нашем примере составляет 15. Хранение нескольких по-разному рассортированных дублей массива или систематическая сортировка единственного массива в соответствии с поступающими запросами не является хорошим решением проблемы.

Рассмотрим возможности создания нескольких массивов индексов в этой ситуации. Индекс удобно формировать не для одного ключевого атрибута, а для набора атрибутов. Естественно, что индекс ключевых атрибутов а1+а2+а3+а4 может также использоваться для быстрого доступа по атрибутам а1+а2+а3, а1+а2 и а1. Поэтому в нашем примере максимально необходимо создание 4 индексов с упорядоченностью атрибутов а1+а2+а3+а4, а1+а2+а4,

а1+а3+а4, а2+а3+а4.

Для доступа к данным по нескольким ключевым атрибутам используется также мультисписковая организация данных. Мультисписком называется

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

Рассмотрим особенности организации мультисписков, которые предназначены для обработки записей по нескольким ключевым атрибутам.

Пример

Втабл. 3.2 показаны 14 записей с ключевыми атрибутами Фамилия и Профессия (остальные атрибуты в данном случае несущественны). На пересечении строки с некоторой фамилией и столбца с некоторой профессией указан номер записи, которая содержит именно эти значения в качестве ключей.

Впростейшем случае мультисписок будет содержать два списка - с указателем Фамилия - (А(1), А(2), А(3), ... , А(13), А(14)) и с указателем Профессия - (А(3), А(6), А(12), А(1), А(7), А(10), А(13), А(2), А(4), А(8), А(14), А(5), А(9), А(11)).

Та б л и ц а 3 . 2 . Мультисписок для двух ключевых атрибутов

Фамилия			Профессия
	слесарь	токарь		штамповщик	электрик
Бардин		А(1)		А(2)
Басов	А(3)			А(4)	А(5)
Батов	А(6)	А(7)
Белов				А(8)	А(9)
Иванов		А(10)			А(11)
Исаев	А(12)	А(13)		А(14)

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

Эффективная организация мультисписка предполагает выполнение следующих условий:

•число записей в каждом списке должно быть небольшим,

•адреса хранения записей должны монотонно возрастать.

Для сокращения длины списков в мультисписке необходимо детализировать содержимое указателей. Например, указатель Фамилия = "Ба" определяет список (А(1), А(2), А(3), А(4), А(5), А(6), А(7)), указатель Фамилия = "Бе" - список (А(8), А(9)), указатель Фамилия = "И" - список (А(10), А(11), А(12), А(13), А(14)). Поскольку атрибут Профессия содержит четыре значения, возможно существование следующих четырех списков: (А(3),А(6),А(12)); (А(1),А(7),А(10),А(13)); (А(2),А(4),А(8),А(14)); (А(5),А(9),А(11)).

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

Рассмотрим запрос с условием

Фамилия ="Иванов" и Профессия = "электрик"

Потребуются три обращения к памяти для выбора списка (А(10), А,(11), А(12)),А(13), А(14)) и четыре обращения для выбора списка (А(5),А(9), А(11)).

Вуказателях хранится длина каждого списка. Вторая строка короче, поэтому она просматривается полностью до извлечения нужной записи А(11).

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

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

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

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

Рис. 3.13. График зависимости времени доступа к данным от адресного расстояния

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

Определим адресное расстояние dA как разность адресов предыдущего и текущего обращения к запоминающему устройству, взятую со знаком "плюс".

DA = |A(i - l) - A(i)|.

Чтобы применять адресное расстояние ко всем типам запоминающих устройств, отметим, что с магнитного диска читается (записывается) не отдельный символ (байт), а сектор или блок данных размером, например, 512 байт.

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

Когда производится только последовательная обработка файла, оптимальный (с точки зрения минимального времени доступа) размер блока должен быть наиболее крупным из возможных; когда происходит только выборка одиночных записей, оптимальными являются блоки размером в одну запись.

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

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

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

В зависимости от размера первичной области могут создаваться один, два или три уровня индексов:

•индекс первого уровня отмечает последнюю запись каждой дорожки магнитного диска;

•индекс второго уровня отмечает последнюю запись каждого цилиндра магнитного диска.

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

на том цилиндре, при котором ключи новых записей соответствуют интервалу значений ключей в первичной области этого цилиндра.

Перечислим итоговые характеристики индексно-последовательного доступа:

•значения ключей записей должны быть отсортированы;

•в индекс заносится наибольший ключ для всех записей блока (дорожки);

•наличие повторяющихся значений ключа недопустимо;

•эффективность доступа зависит от числа уровней индексации, распределения памяти для размещения индекса, числа записей в файле и размера области переполнения. Если в индекс попадает информация о ключе каждой записи, то получаем индекснопроизвольный доступ. Записи файла могут быть при этом не упорядочены по значению ключа. Индекс для индекснопроизвольного метода доступа практически всегда формируется как многоуровневый. Типичная организация многоуровневого индекса соответствует понятию В-дерева. Нижний уровень В-дерева образуют индексы со ссылкой на каждую запись основного массива. Благодаря использованию адресных ссылок упорядоченность основного массива не обязательна. Индексы нижнего уровня разделены на страницы, и в конце каждой

страницы оставляется резервная память. Последний индекс каждой страницы поступает на страницу предпоследнего уровня В-дерева. Когда эта страница будет почти заполнена индексами, последний из них поступит на страницу более высокого уровня и т. д.

Пользуясь аналогией между многоступенчатым поиском и многоуровневым индексом, можно утверждать, что минимальное время доступа обеспечивает В-дерево с числом уровней, примерно равным 1nМ (М - число записей в основном массиве). Корень В-дерева обычно имеет два разветвления, так как при большем числе разветвлений происходит незначительное ускорение доступа. Пример В-дерева для 14 записей основного массива приводится на рис. 3.14.

Поиск данных (например, значения q) начинается с корня В-дерева. Предположим, что k8 < q < kl4. В этом случае выполняются переход по правой ветви на второй уровень и поиск на соответствующей странице. Будем считать, что kl0 < q < kl3. Следовательно, надо спуститься на третий уровень по адресу, записанному в kl3, и завершить поиск. Достоинство В-дерева состоит в его простом расширении. При переполнении какой-либо страницы половина ее содержимого переходит в новую страницу, а на вышестоящем уровне появляется новый индекс.