Организация данных и структуры данных

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

Совсем иначе обстоит дело при обработке коммерческих и деловых данных, которая в настоящее время является главной сферой применения вычислительных машин. Объем вычислений здесь, как правило, невелик, однако в данном случае необходимо преобразовать, просмотреть, скопировать и модифицировать огромные количества данных. Для хранения таких масс данных сконструированы специальные устройства, а для эффективной обработки данных разработаны различные аппаратные и программные средства.

Материал этой главы предполагает, что читатель знаком с основными аппаратными характеристиками наиболее часто используемых устройств хранения данных, например, таких, как магнитные ленты и диски. Текст главным образом ориентирован на вопросы программного обеспечения организации данных.

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

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


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Организация данных и структуры данных Исследователю или инженеру, научившемуся работать на вычислительной машине, не приходится слишком много беспокоиться о данных. Он использует машину как очень быстрый, эффективный и надежный вычислитель. При этом на объем его входных и выходных данных обычно накладываются ограничения, выражающиеся в некоторых фиксированных числах перфокарт и печатных строк. Несмотря на огромные различия в быстродействии между центральным процессором и устройствами ввода-вывода, время, затрачиваемое на проведение вычислений, как правило, значительно превышает время, необходимо - для ввода исходных данных и вывода результатов. Поэтому такой пользователь не проявляет особого интереса к вопросам эффективной организации хранения и поиска больших объемов данных. Совсем иначе обстоит дело при обработке коммерческих и деловых данных, которая в настоящее время является главной сферой применения вычислительных машин. Объем вычислений здесь, как правило, невелик, однако в данном случае необходимо преобразовать, просмотреть, скопировать и модифицировать огромные количества данных. Для хранения таких масс данных сконструированы специальные устройства, а для эффективной обработки данных разработаны различные аппаратные и программные средства. Материал этой главы предполагает, что читатель знаком с основными аппаратными характеристиками наиболее часто используемых устройств хранения данных, например, таких, как магнитные ленты и диски. Текст главным образом ориентирован на вопросы программного обеспечения организации данных. Используемая здесь терминология в основном совпадает с применяемой в материалах фирмы IBM. Возможно, что другие фирмы-производители машин называют те же самые или аналогичные подпрограммы и таблицы другими именами или же объединяют их иными способами, но основные функции этих подпрограмм и таблиц эквивалентны тем, что описаны здесь. Сначала в главе рассматриваются различные форматы записей, организация файлов и методы доступа. Затем объясняются методы адресации и сортировки данных. В конце главы с целью ознакомления читателя с проблемами, возникающими при обработке больших объемов данных, кратко обсуждаются простые структуры данных и основные элементы концепции базы данных и систем управления базами данных.