В информатике запись (также называемая структурой , структурой или составными данными ) представляет собой базовую структуру данных . Записи в базе данных или электронной таблице обычно называются « строками ». [1] [2] [3] [4]
Запись — это набор полей , возможно, разных типов данных, обычно в фиксированном количестве и последовательности. [5] Поля записи также можно называть членами , особенно в объектно-ориентированном программировании ; поля также могут называться элементами , хотя это может привести к путанице с элементами коллекции .
Например, дата может храниться как запись, содержащая числовое поле года , поле месяца , представленное в виде строки, и числовое поле дня месяца . Кадровая запись может содержать имя , зарплату и звание . Запись Circle может содержать центр и радиус — в этом случае сам центр может быть представлен как запись точки , содержащая координаты x и y .
Записи отличаются от массивов тем, что количество их полей определяется в определении записи, а также тем, что записи представляют собой гетерогенный тип данных; не все поля должны содержать данные одного и того же типа. [6]
Тип записи — это тип данных , который описывает такие значения и переменные. Большинство современных компьютерных языков позволяют программисту определять новые типы записей. Определение включает указание типа данных каждого поля и идентификатора (имени или метки), по которому к нему можно получить доступ. В теории типов типы продуктов (без имен полей) обычно отдаются предпочтение из-за их простоты, но подходящие типы записей изучаются на таких языках, как System F-sub . Поскольку теоретико-типические записи помимо данных могут содержать первоклассные поля с функциональными типами, они могут выражать многие особенности объектно-ориентированного программирования .
Записи могут существовать на любом носителе информации, включая оперативную память и устройства хранения данных , такие как магнитные ленты или жесткие диски . Записи являются фундаментальным компонентом большинства структур данных, особенно связанных структур данных . Многие компьютерные файлы организованы как массивы логических записей , которые для повышения эффективности часто группируются в более крупные физические записи или блоки .
Параметры функции или процедуры часто можно рассматривать как поля переменной записи; и аргументы, передаваемые этой функции, можно рассматривать как значение записи, которое присваивается этой переменной во время вызова. Кроме того, в стеке вызовов , который часто используется для реализации вызовов процедур, каждая запись представляет собой запись активации или кадр вызова , содержащий параметры процедуры и локальные переменные, адрес возврата и другие внутренние поля.
Объект в объектно-ориентированном языке — это, по существу, запись, содержащая процедуры, предназначенные для обработки этой записи; а типы объектов являются развитием типов записей. Действительно, в большинстве объектно-ориентированных языков записи представляют собой всего лишь частные случаи объектов и известны как старые простые структуры данных (PODS), в отличие от объектов, использующих объектно-ориентированные функции.
Запись можно рассматривать как компьютерный аналог математического кортежа , хотя кортеж может считаться записью, а может и не считаться, и наоборот, в зависимости от соглашений и конкретного языка программирования. В том же духе тип записи можно рассматривать как аналог декартова произведения двух или более математических наборов в компьютерном языке или реализацию абстрактного типа продукта на определенном языке.
Запись может иметь ноль или более ключей . Ключ сопоставляет выражение со значением или набором значений в записи. Первичный ключ уникален для всех хранимых записей; существует только один из этих ключей. [7] Другими словами, ни для одного первичного ключа не может существовать дубликат. Например, файл сотрудника может содержать номер сотрудника, имя, отдел и зарплату. Номер сотрудника будет уникальным в организации и будет первичным ключом. В зависимости от носителя и организации файлов номер сотрудника может быть проиндексирован — он также сохраняется в отдельном файле для ускорения поиска. Код отдела не обязательно уникален; он также может быть проиндексирован, и в этом случае он будет считаться вторичным ключом или альтернативным ключом . [8] Если он не проиндексирован, придется сканировать весь файл сотрудника, чтобы получить список всех сотрудников определенного отдела. Ключи обычно выбираются таким образом, чтобы свести к минимуму вероятность реального сопоставления нескольких значений с помощью одного ключа. Например, поле «Зарплата» обычно не считается пригодным для использования в качестве ключа, поскольку многие сотрудники, скорее всего, будут иметь одинаковую зарплату. Индексирование — это один из факторов, который учитывается при разработке файла.
Понятие записи можно проследить до различных типов таблиц и регистров , используемых в бухгалтерском учете с давних времен. Современное понятие записей в информатике с полями четко определенного типа и размера уже было неявно заложено в механических калькуляторах XIX века, таких как аналитическая машина Бэббиджа . [9] [10]
Первоначальным машиночитаемым носителем данных (в отличие от контрольных) была перфокарта, использовавшаяся для записей переписи населения США 1890 года : каждая перфокарта представляла собой отдельную запись. Сравните запись в журнале 1880 года и перфокарту 1895 года. Записи были широко распространены в первой половине 20-го века, когда большая часть обработки данных выполнялась с использованием перфокарт. Обычно каждая запись файла данных записывается на одну перфокарту, причем определенным полям присваиваются определенные столбцы. Как правило, запись представляла собой наименьшую единицу, которую можно было прочитать из внешнего хранилища (например, устройства чтения карт, ленты или диска). Содержимое записей в виде перфокарт изначально называлось «единичными записями», поскольку перфокарты имели заранее определенную длину документа. [11] Когда системы хранения стали более продвинутыми с использованием жестких дисков и магнитной ленты , записи переменной длины стали стандартом. Запись переменной длины — это запись, у которой размер записи в байтах примерно равен сумме размеров ее полей. Это было невозможно сделать до того, как было изобретено более совершенное оборудование для хранения данных, поскольку все перфокарты должны были соответствовать заранее определенной длине документов, которые мог прочитать компьютер, поскольку в то время карты нужно было физически вводить в машину.
Большинство реализаций машинного языка и ранние языки ассемблера не имели специального синтаксиса для записей, но эта концепция была доступна (и широко использовалась) благодаря использованию индексных регистров , косвенной адресации и самомодифицирующегося кода . Некоторые ранние компьютеры, такие как IBM 1620 , имели аппаратную поддержку для разграничения записей и полей, а также специальные инструкции для копирования таких записей.
Концепция записей и полей была центральной в некоторых ранних утилитах сортировки файлов и табулирования , таких как IBM Report Program Generator (RPG) .
COBOL был первым широко распространенным языком программирования, поддерживающим типы записей[12], и его возможности определения записей были довольно сложными в то время. Язык позволяет определять вложенные записи с буквенно-цифровыми, целочисленными и дробными полями произвольного размера и точности, а также поля, которые автоматически форматируют любое присвоенное им значение (например, вставку знаков валюты, десятичных точек и разделителей групп цифр). ). Каждый файл связан с переменной записи, в которую данные считываются или записываются. COBOL также предоставляетMOVE CORRESPONDINGоператор, который назначает соответствующие поля двух записей в соответствии с их именами.
Ранние языки, разработанные для числовых вычислений, такие как FORTRAN (вплоть до FORTRAN IV ) и Algol 60 , не имели поддержки типов записей; но более поздние версии этих языков, такие как FORTRAN 77 и Algol 68, добавили их. В исходном языке программирования Лисп тоже отсутствовали записи (за исключением встроенной cons-ячейки ), но его S-выражения представляли собой адекватный суррогат. Язык программирования Паскаль был одним из первых языков, в котором типы записей полностью интегрировались с другими базовыми типами в логически согласованную систему типов. Язык программирования PL/I обеспечивает записи в стиле COBOL. Язык программирования C изначально представлял концепцию записи как своего рода шаблон ( struct), который можно было разместить поверх области памяти, а не как настоящий тип данных записи. Последние были предоставлены в конечном итоге (в typedefдекларации), но эти две концепции по-прежнему различны в языке. Большинство языков, разработанных после Паскаля (таких как Ada , Modula и Java ), также поддерживают записи.
Хотя записи больше не часто используются в их исходном контексте (т.е. используются исключительно для целей хранения данных), записи повлияли на новые объектно-ориентированные языки программирования и системы управления реляционными базами данных . Поскольку записи обеспечивают большую модульность в способах хранения и обработки данных, они лучше подходят для представления сложных, реальных концепций, чем примитивные типы данных , предусмотренные в языках по умолчанию. Это повлияло на более поздние языки, такие как C++ , Python , JavaScript и Objective-C , которые решают те же проблемы программистов с модульностью. [13] Объекты в этих языках по сути представляют собой записи с добавлением методов и наследования , которые позволяют программистам манипулировать поведением данных, а не только содержимым записи. Многие программисты сейчас считают записи устаревшими, поскольку объектно-ориентированные языки обладают возможностями, намного превосходящими возможности записей. С другой стороны, многие программисты утверждают, что низкие накладные расходы и возможность использования записей на языке ассемблера делают записи по-прежнему актуальными при программировании с низким уровнем абстракции . Сегодня самые популярные языки в индексе TIOBE , показателе популярности языков программирования, в той или иной степени подверглись влиянию рекордов из-за того, что они объектно-ориентированы. [14] Языки запросов, такие как SQL и язык объектных запросов, также находились под влиянием концепции записей. Эти языки позволяют программисту хранить наборы данных, которые по сути являются записями, в таблицах. [15] Эти данные затем можно получить с помощью первичного ключа . Сами таблицы также являются записями, которые могут иметь внешний ключ : ключ, ссылающийся на данные в другой таблице.
Выбор поля из значения записи дает значение.
Некоторые языки могут предоставлять средства, перечисляющие все поля записи или, по крайней мере, поля, которые являются ссылками. Это средство необходимо для реализации определенных служб, таких как отладчики , сборщики мусора и сериализация . Это требует некоторой степени полиморфизма типов .
В системах с подтипами записей операции над значениями типа записи могут также включать:
В таких настройках определенный тип записи подразумевает наличие определенного набора полей, но значения этого типа могут содержать дополнительные поля. Таким образом, запись с полями x , y и z будет принадлежать к типу записей с полями x и y , как и запись с полями x , y и r . Смысл в том, что передача записи ( x , y , z ) функции, которая ожидает запись ( x , y ) в качестве аргумента, должна работать, поскольку эта функция найдет все необходимые поля в записи. Многие способы практической реализации записей в языках программирования могут вызвать проблемы с допущением такой изменчивости, но это основная характеристика типов записей в более теоретическом контексте.
Большинство языков допускают присваивание между записями, которые имеют одинаковый тип записи (включая одинаковые типы полей и имена в одном и том же порядке). Однако в зависимости от языка два типа данных записи, определенные отдельно, могут рассматриваться как разные типы, даже если они имеют одинаковые поля.
Некоторые языки также могут разрешать присваивание между записями, поля которых имеют разные имена, сопоставляя каждое значение поля с соответствующей переменной поля по их позициям в записи; так, чтобы, например, комплексное число с полями вызывалось realи imagмогло быть присвоено переменной записи 2D-точки с полями Xи Y. В этом альтернативном варианте два операнда по-прежнему должны иметь одинаковую последовательность типов полей. Некоторые языки также могут требовать, чтобы соответствующие типы имели одинаковый размер и кодировку, чтобы всю запись можно было назначить как неинтерпретируемую битовую строку . Другие языки могут быть более гибкими в этом отношении и требуют только того, чтобы каждое поле значения могло быть законно присвоено соответствующему полю переменной; так что, например, короткое целочисленное поле можно назначить длинному целочисленному полю или наоборот.
Другие языки (например, COBOL ) могут сопоставлять поля и значения по их именам, а не по позициям.
Эти же возможности применимы и к сравнению двух значений записи на равенство. Некоторые языки также могут позволять сравнивать порядок ('<' и '>'), используя лексикографический порядок , основанный на сравнении отдельных полей. [ нужна цитата ]
PL/I допускает оба предыдущих типа присвоения, а также допускает структурные выражения , например, a = a+1;где «a» — это запись, или структура в терминологии PL/I.
В Алголе 68, если Ptsбы был массив записей, каждая с целочисленными полями Xи Y, можно было бы написать , чтобы получить массив целых чисел, состоящий из полей всех элементов . В результате заявления и имели бы тот же эффект.Y of PtsYPtsY of Pts[3] := 7(Y of Pts)[3] := 7
В языке программирования Паскаль команда with R do Sбудет выполнять последовательность команд S, как если бы все поля записи Rбыли объявлены как переменные. Подобно вводу другого пространства имен в объектно-ориентированном языке, таком как C# , больше нет необходимости использовать имя записи в качестве префикса для доступа к полям. Таким образом, вместо записи Pt.X := 5; Pt.Y := Pt.X + 3можно было бы написать .with Pt do begin X := 5; Y := X + 3 end
Представление записей в памяти варьируется в зависимости от языков программирования. Обычно поля хранятся в памяти в последовательных позициях в том же порядке, в котором они объявлены в типе записи. Это может привести к тому, что два или более полей будут сохранены в одном слове памяти; действительно, эта функция часто используется в системном программировании для доступа к определенным битам слова. С другой стороны, большинство компиляторов добавляют поля заполнения, в основном невидимые для программиста, чтобы соответствовать ограничениям выравнивания, налагаемым машиной — скажем, что поле с плавающей запятой должно занимать одно слово.
Некоторые языки могут реализовать запись как массив адресов, указывающих на поля (и, возможно, на их имена и/или типы). Объекты в объектно-ориентированных языках часто реализуются довольно сложными способами, особенно в языках, допускающих множественное наследование классов .
Самоопределяющаяся запись — это тип записи, который содержит информацию для идентификации типа записи и поиска информации внутри записи. Он может содержать смещения элементов; поэтому элементы могут храниться в любом порядке или могут быть опущены. [16] Информация, хранящаяся в самоопределяющейся записи, может интерпретироваться как метаданные для записи, что аналогично тому, что можно было бы ожидать найти в метаданных UNIX о файле, содержащих такую информацию, как время создания записи и размер. записи в байтах . Альтернативно, различные элементы записи, каждый из которых включает идентификатор элемента, могут просто следовать друг за другом в любом порядке.