Понятие об обработке данных

Списки записей могут быть объектами различных обработок, которые включают в себя как анализ и синтез символьной информации, так и арифметические операции. Проблемы и способы, которые связаны с обработкой списков записей, имеют общее название «обработка данных». Под совокупностью программ, реализующих алгоритмы обработки данных, и являющихся прикладными программами в практической деятельности (технической, хозяйственной, социальной, научной и т. п.), понимают систему обработки данных. Иногда этим термином называют не только совокупность программ, но и технические средства, а также всю технологию их применения: подготовку исходных данных, порядок выполнения программ, методы использования результатов и т. д. Структуры записей и способы их объединения в списки определяются в процессе проектирования системы обработки данных в компьютере, мобильном телефоне, прочих вычислительных устройствах; они должны быть согласованы с алгоритмами обработки, предусмотренными в системе. В последнее время наметилась новая тенденция: создаются системы управления базами данных. Эти системы позволяют в значительной мере ослабить связь между структурами данных и обрабатывающими программами.
В практически действующих системах обработки данных списки записей обычно объединяются в наборы данных. Наборы данных хранятся на внешних носителях, и записи вызываются в основную память сравнительно небольшими порциями.
Предполагается, что весь обрабатываемый список записей расположен в основной памяти.
Записи могут быть организованы в списки по-разному. Например, порядок записей в списке может определяться моментами их включения в список: новая запись помещается в область памяти, непосредственно следующую за областью, занятой последней, уже имеющейся в списке записью. Такая организация называется физически последовательной. Записи можно располагать в порядке возрастания значения некоторого подполя записи. Подполе, используемое для упорядочения записей, называется ключом; в общем случае значение ключа — это целое неотрицательное значение, представленное битами, составляющими ключ и рассматриваемыми как двоичные цифры. Список с такой организацией называется упорядоченным по ключу. При помещении в список, упорядоченный по ключу, новой записи со значением ключа к в списке отыскивается пара соседних записей, значения ключей которых удовлетворяют определенному неравенству
и новая запись включается между записями с ключами. Для осуществления такого включения требуется все записи, у которых значения ключей больше или равны единице, сдвинуть в памяти «вправо» так, чтобы освободить место для новой записи.
При исключении записи из списка с физически последовательной организацией или из списка, упорядоченного по ключу, записи следует сдвинуть «влево», чтобы заполнить место памяти, освободившееся от удаленной записи. Время, затрачиваемое на удаление записи, можно сократить: вместо того чтобы сдвигать записи на освободившееся место, можно в каждой записи предусмотреть подполе, которое принимает два значения: первое означает, что запись в списке присутствует, второе — запись из списка исключена. За такой способ сокращения времени, затрачиваемого на удаление записи, приходится «платить» областями памяти, содержащими исключенные записи.
Существуют и другие способы организации списков записей.