Структура данных
Структу́ра да́нных, организация данных, представляющая собой множество их элементов и множество отношений между ними.
Элементы данных структуры могут быть разной гранулярности. Они могут быть простыми (атомарными) либо агрегированными (составными), включающими другие элементы данных. Примерами атомарных элементов данных являются байты, литеры алфавита, числа разного вида (целые, с фиксированной или плавающей точкой), агрегированных – строки, одномерные и многомерные массивы, таблицы, списки, записи, множества. Элементы данных, входящие в состав агрегированных, сами могут быть агрегированными. Например, запись может включать как атомарные, так и агрегированные элементы данных. Таким образом, структура данных может быть рекурсивной.
Элементы данных структуры данных обладают значением и могут снабжаться в её описании или в тегах языков разметки именами, которые используются для их идентификации при выполнении операций над ними. Для идентификации элементов данных могут использоваться их порядковые номера (индексы) в упорядоченных структурах, например, одномерных или многомерных массивах. Наконец, для цели идентификации может использоваться указание их местоположения, абсолютного или относительного по отношению к другим элементам данных.
Агрегированные элементы данных, например, строки таблиц, могут идентифицироваться совокупностью значений некоторого подмножества составляющих их элементов данных. Эта совокупность называется ключом. Значением ключа является конкатенация значений указанных элементов данных.
Отношения между элементами данных структуры могут быть разнообразными. Например, отношение иерархии, отношение порядка, отношение соседства и другие с различной конкретной семантикой. Они могут быть бинарными различного вида (1:1, 1:N или M:N) или n-арными. В соответствии с этим существуют различные виды структур данных: графовые – деревья или сети, уже упоминавшиеся таблицы, одномерные и многомерные массивы, списки и многие другие.
Со структурой данных в ряде случаев ассоциируются некоторые свойства данных, зависимые от вида отношений между её элементами данных. Так, например, в иерархической древовидной структуре данных объектных моделей данных, используемых в языках программирования и других средствах информационных технологий, в которой вершинам дерева соответствуют типы объектов, поддерживаются отношения наследования свойств типа объектов его подтипами. При этом все свойства, определённые для типа объектов, присущи как экземплярам объектов этого типа, так и объектов его подтипов. Некоторые объектные модели данных используют иерархические структуры более общего вида, в которых подтипы могут иметь несколько родительских типов. В ряде таких моделей допускается отношение множественного наследования экземплярами объектов подтипа свойств экземпляров объектов родительских типов.
Используются различные способы представления отношений между элементами данных в структуре данных. Так, для представления отношения порядка между соседними элементами списка может использоваться указание из предыдущего элемента на последующий. Строки двух таблиц в реляционной базе данных, содержащие данные об одной и той же сущности реального мира, связываются по критерию совпадения значений их ключей. Отношение между элементами данных столбцов таблицы представляется их принадлежностью одним и тем же строкам таблицы.
В системах программирования, системах баз данных, в веб-браузерах, обеспечивающих просмотр HTML-страниц или XML-документов, а также в других средствах информационных технологий используется многоуровневое представление данных, которыми они оперируют. Отображение представлений данных между смежными уровнями многоуровневого представления обеспечивается механизмами отображения данных.
Системы программирования имеют дело с описанием структуры данных и других их свойств на языке программирования, а также с внутренним представлением этих данных (с их внутренней структурой) на стадии исполнения. Компилятор исходного кода программы, по сути, генерирует описание внутренней структуры данных на основе их описания на языке программирования и «встраивает» его в исполняемый код программы. Интерпретатор формирует и использует внутреннюю структуру данных на стадии исполнения. Средства отображения данных фактически используются при этом, соответственно, на стадии компиляции исходного кода программы или на стадии его интерпретации.
Система управления базами данных (СУБД) генерирует также в своём внутреннем представлении описание структуры хранимых данных, используя схему базы данных, когда она загружается в систему. Механизмы отображения данных являются функциональными компонентами СУБД и работают на стадии функционирования системы. Точно так же механизмы отображения данных встроены в веб-браузеры и функционируют при просмотре страниц веб-сайтов. Эти механизмы генерируют из представления страницы сайта на языке разметки её представление для пользователя, используя информацию тегов разметки.
Благодаря возможности поддержки многоуровневого представления данных обеспечивается иерархия абстракций данных, позволяющая пользователям СУБД и веб-браузеров, а также программистам при написании программного кода обращаться с данными в понятной им форме, избавляя от необходимости знания, как устроены хранимые данные, – представления их на нижнем уровне иерархии или внутренней структуры данных в исполняемой программе.
Таким образом, указанные программные средства имеют дело с несколькими структурами данных, каждая из которых относится к соответствующему уровню иерархии абстракции данных. Структуры хранимых данных в системах баз данных обладают при этом отличительной особенностью. Наряду с данными, представляющими интерес для пользователей, они могут включать организованные специальным образом вспомогательные структуры данных, обеспечивающие быстрый доступ к пользовательским данным. Примерами могут служить организованные различными способами индексы и хеш-таблицы.
В зависимости от вида структуры данных и уровня абстракции данных, к которому она относится, над составляющими её данными возможны различные специфические операции. Так, для данных графовой структуры характерны навигационные операции. Для данных табличной структуры в реляционных системах баз данных свойственны операции селекции (выборки подмножества строк таблицы), проекции (построение новой таблицы, состоящей из заданного подмножества столбцов исходной таблицы), а также соединения таблиц (построение новой таблицы из столбцов двух таблиц-аргументов таким образом, что строки новой таблицы образуются из пар строк, каждая из которых принадлежит одной из таблиц-аргументов; при этом пары образуются из строк, у которых совпадают значения в указанных столбцах). Для структуры хранимых данных специфичны, например, операции актуализации индексов.
Используемые в различных программных системах структуры данных могут иметь или не иметь описание, отчуждённое или не отчуждённое от самих данных. Программный код на языке программирования всегда содержит описание средствами этого языка структуры данных, в нём используемых. СУБД располагает описанием структуры и других свойств данных, содержащихся в базе данных, называемым схемой базы данных. В обоих этих случаях описание структуры данных отчуждено от самих данных. Иная ситуация имеет место для структур данных гипертекстовых HTML-страниц веб-сайтов или для не снабжённых спецификацией соответствующей им XML-схемой XML-документов, содержащихся в веб-сайтах или в системах баз данных. Здесь описание структуры данных не отчуждено от данных и встроено в представление страниц на языке разметки средствами тегов языка. В этом случае структура данных является самоописываемой.
Существует ещё одна особенность структуры хранимых данных в системах баз данных. В современных СУБД отсутствуют средства её описания. Это описание автоматически генерируется из описания структуры данных более высокого уровня многоуровневого представления данных – схемы базы данных. Одним из исключений являются ранние СУБД, основанные на подходе CODASYL. В таких СУБД проектировщику баз данных предоставляется специальный язык описания хранимых данных (англ. Data Storage Description Language – DSDL), на котором описывается их структура и другие необходимые свойства.
Данные, структура которых описана и это описание отчуждено от данных, называются структурированными. В отличие от них, как уже отмечалось, существуют данные со структурой, описание которой встроено в данные (например, страницы веб-сайтов) либо которая описывается схемой, не являющейся строго регламентирующей состояние данных, и некоторые элементы данных структуры могут не соответствовать схеме. Данные с такой структурой называются слабоструктурированными. Такими данными оперируют, например, веб-браузеры и некоторые системы баз данных XML-документов. Наконец, в случае, когда какое-либо описание структуры данных вообще отсутствует, данные называются неструктурированными. Примерами могут служить текстовые документы на естественных языках, аудио- и видеоданные.
Рассмотренные характеристики степеней структурированности обычно не ассоциируют с хранимыми данными и внутренним представлением данных в системах программирования.