Слишком сложно? Тогда запросите консультацию специалиста!
Наша компания занимается тем, что помогает студентам выполнять различные учебные работы на заказ. Вы можете ознакомиться с перечнем выполняемых работ, а так же с их стоимостью на странице с ценами.
Последовательные структуры данных (ПСД)
Способы физической организации и хранения данных
ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ БАЗ ДАННЫХ
Существует два понятия: логическая и физическаяорганизация данных.
Логическая – отображает логическую структуру баз данных. Например, это может быть строка из таблицы для реляционной модели или экземпляры вершин в иерархической модели.
Физическая – отражает физическую структуру хранения данных. Представляет собой совокупность файлов. При этом связи между файлами также реализуются с помощью файлов. При хранении данных в физической памяти используют шесть основных способов доступа к памяти.
1. Последовательный способ
2. Индексно-последовательный
3. Индексно-произвольный
4. Инвертированный
5. Прямой
6. Хеширования
Введем два критерия для оценки качества физических способов доступа.
1) Эффективность доступа – это количественная величина, обратная среднему числу обращений к внешней памяти. Имеется в виду количество обращений, которые необходимы для доступа к конкретной записи.
2) Эффективность хранения – это величина, обратная среднему числу байт вторичной памяти, которые используются для хранения одного байта исходных данных.
(последовательный способ)
ПСД характеризуется тем, что логический порядок элементов совпадает с физическим порядком расположения элементов. Элементами ПСД являются записи.
Отметим, что ПСД могут быть упорядоченными и неупорядоченными по значению ключевого признака. Имя ключевого признака одинаково во всех записях. Записи могут быть постоянной, переменной и неопределенной длины.
Преимущества.
Экономное использование памяти, т.к. записи ПСД располагаются одна за другой. Однако это преимущество теряется, если заранее неизвестно общее число записей. В этих случаях выделяют дополнительную память под максимально возможное число записей.
Недостатки.
1. Неудобство корректировки
2. Длительность выборного поиска.
Отметим, что в этом способе вставка нового элемента должна выполняться с соблюдением логического порядка следования элементов. Это вызывает необходимость физического перемещения данных.
Примечание. В связи с широким распространением реляционных баз данных применение последовательного способа значительно возросло. Это объясняется тем, что многие реляционные СУБД предусматривают организацию хранения каждого отношения в виде последовательного файла.
В связи с тем, что физические данные могут быть фиксированной и переменной длины, на практике используются различные способы хранения данных.
Рассмотрим пример. Пусть в памяти машины имеется последовательно организованный файл.
| Ф.И.О. | Возраст | Должность |
| Бендер Паниковский Балаганов Функ | Зав. отделением Курьер Конюх Зам. председателя |
Если записи будут иметь фиксированную длину, то в памяти ЭВМ необходимо отвести место, равное максимальной длине.
Паниковский 60 Курьер*********
 |
Функ ******* 70 Зам. председателя
 |
Память используется неэффективно. На практике используют переменную длину записи.
Бендер & 30 & зав. отделением, где & - разделитель
При таком способе нет нерационального расхода памяти, однако здесь требуется специальный счетчик, который подсчитывает разделители. На практике иногда используют разновидность способа хранения данных, позволяющего размещать элементы в произвольном порядке.
При этом каждая запись должна иметь свой разделитель.
Бендер & 30? зав. отделением!
Отметим, что при этом объем вторичной памяти не изменяется. Вместе с тем, расходуется дополнительное время на распознавание знаков.
В основе индексно-последовательного и индексно-произвольного методов доступа лежит принцип организации дополнительного вспомогательного файла. Этот файл называется индексным. Индексный файл содержит в себе значения ключей действующего файла, т.е. исходного файла.
Рассмотрим пример.
| Табельный № | № цеха | Профессия | Разряд | Записи основного файла условно разделим на три блока и организуем индексный файл.
В индексном файле каждая запись имеет два элемента: индекс и адрес.
| ||||
| Слесарь Токарь Наладчик | ||||||||
| Слесарь Наладчик | ||||||||
| Слесарь Токарь |
Индексы выбираются из множества значений исходных ключей. Причем один индекс соответствует нескольким записям исходного файла. Индексный файл содержит индексы, которые соответствуют упорядоченным записям.
бл.1
| Значение ключа |  Адрес блока
| Отметим, что индексы из нескольких исходных ключей выбираются с наибольшим значением. Каждый блок соответствует некоторому множеству записей в исходном файле. Причем распределение записей по блокам должно быть равномерным. | |||
| *0423 | |||||
| бл.2 | |||||
| |||||
| *0934 | |||||
 3
| бл.3 | ||||
| *1016 | |||||
Предположим, что необходимо отыскать запись с ключом 0981. При этом выполняется следующая процедура. Сначала считывается индекс 0423, требуемый адрес найти не можем, т.к. значение ключа 0423 меньше, чем 0981, затем считываем следующее значение 0934, переходим к индексу 1016. По индексу 1016 в блоке 3 отыскиваем требуемую запись.
Вывод. Эффективность доступа в этом методе выше по сравнению с последовательным методом. В то же время эффективность хранения ниже, причем она падает с возрастанием индексного файла. Это объясняется тем, что индексный файл требует дополнительной памяти.
Примечание. Для очень больших исходных файлов иногда используется несколько уровней индексации. Это означает, что в индексном файле делается ссылка не на блок с исходными данными, а на блок с другими индексами.
Рассмотрим пример.
|  4
| ||||||
 5
| *0318 | ||||||
 6
| |||||||
| |||||||
 3
| *0914 | ||||||
| . | |||||||
| . | |||||||
| . |
. . . .
Для дополнения записи в индексно-последовательном методе используются различные приемы. Например,
1) отводится дополнительная область переполнения каждому блоку
2) организуется общая резервная область переполнения для всех блоков.
