ГЛАВА 3. ФИЗИЧЕСКАЯ ОРГАНИЗАЦИЯ ДАННЫХ В СУБД

3.1.Списковые структуры

Всистемах обработки данных в качестве данных выступают описания (представления) фактов и понятий рассматриваемой предметной области на точном и формализованном входном языке системы – языке описания данных [17]. С помощью входного языка при описании фактов и понятий ПО между элементами данных конструируются логические структурные отношения. В качестве логических структур (см. гл.2) используют либо таблицы, представляющие собой двумерный или n-мерный массив данных, либо древовидные иерархические структуры, либо сетевые структуры, представляющие собой сложную многосвязную структуру с большим количеством взаимных соединений и т.п. Чтобы правильно использовать вычислительную машину, необходимо хорошо представлять себе структурные отношения между данными, знать способы представления таких структур в памяти машины и методы работы с ними. Структура данных и представление этой структуры в памяти ЭВМ – два важных, но различных между собой понятия [17]. Так, например, некоторая логическая структура данных типа «дерево» может быть представлена в памяти ЭВМ несколькими различными способами.

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

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

Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список. Линейный список – это множество n≥0 объектов (узлов) Х[1], Х[2], ..., Х[п], структурные свойства

которого связаны только с линейным (одномерным) относительным расположением узлов. Если n>0, то Х[1] является первым узлом; для 1<i<n узел X[i-1] предшествует узлу X[i], а узел Х[i+1] следует за ним, Х[п] является последним узлом, т.е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных [17].

Линейный список X рассматривают как последовательность Х[1], Х[2], ..., X[i], ..., Х[n], компоненты которой идентифицированы порядковым номером, указывающим их относительное расположение в X.

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

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

При реализации адресной функции используют два основных метода [17]:

последовательное распределение памяти;

связанное распределение памяти.

3.1.1.Последовательное распределение памяти

Последовательное распределение – простой и естественный способ хранения линейного списка. В этом случае узлы списка размещаются в последовательных элементах памяти (рис.3.1) [17].

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

а) N – размер вектора данных, т.е. количество элементов списка записей; б) т – размер элемента списка, т.е. размер записи, например, в байтах;

70

в) β – адрес базы, указывающий на начало вектора данных в памяти.

Рис. 3.1. Пример последовательного распределения памяти для представления линейного списка

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

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

Вкачестве примера (из [17]) рассмотрим реализацию с помощью линейного списка при последовательном распределении памяти для логической структуры типа регулярного двоичного дерева (рис. 3.2). Идея способа заключается в том, что начиная с элемента памяти α(1), делают его корнем

дерева, размещают там данные, соответствующие узлу У1. В элементах памяти α(2) и α(3) размещают непосредственных потомков узла У1 – узлы У2 и У3, и т.д. В общем случае, непосредственные потомки узла Уk размещаются по адресам: α(2k) и α(2k+1). Адресная функция имеет вид

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

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

где ë û – знак округления до ближайшего меньшего целого.

71