Фрэнк Солтис - Основы AS/400

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

Позднее в System/3 была добавлена интерактивная обработка. Применение дисков позволило обращаться к записям в произвольном порядке. Поиск нужной записи осуществлялся с помощью индекса — небольшого файла, в котором каждой записи основного файла соответствуют лишь два поля. Первое содержит значение ключа, а второе — дисковый адрес записи с совпадающим значением. Для сортировки записей индекса по значениям ключа использовалась особая программа. Затем индекс сохранялся на диске вместе с основным файлом.

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

System/34 была первой моделью семейства System/3, предназначенной для работы в интерактивном, а не в пакетном режиме. Размеры памяти в System/34 были также невелики, так что IBM решила ускорить поиск нужной записи в индексе, а для этого — устранить необходимость считывать индекс с диска.

Часть дорожек диска была зарезервирована для индекса, для контроллера диска была разработана специальная аппаратура. Желаемое значение ключа процессор передавал дисковому контроллеру. Затем контроллер начинал считывать информацию дорожки, отыскивая значение ключа. Обнаружив искомое, аппаратура контроллера считывала следующее поле адреса и возвращала его процессору. Процессор использовал полученный адрес для считывания целой записи из некоторой другой части диска.

Эта операция была названа сканированием. Функция сканирования значительно повысила эффективность интерактивной обработки, благодаря полному устранению этапа обращения к диску для считывания индекса. Но при этом потребовалось встроить в памяти еще один небольшой индекс. Индекс в памяти указывал, на какой индексной дорожке диска следует выполнять поиск. Позднее аналогичная операция сканирования была реализована в System/36 для обработки файлов.

Для System/38 также была важна очень высокая эффективность интерактивной обработки. Недостатком описанной процедуры сканирования была ее слишком тесная привязка к аппаратуре. Были также и другие ограничения: максимально возможное число индексов, ограничение способов их обработки и др. Так как System/38 должна была иметь одноуровневую память, разработчики решили поместить все файлы и индексы в эту большую память.

Если вернуться назад к только что описанной файловой структуре, то мы увидим двумерную таблицу, где строки —это записи, а столбцы — поля записей. Разработчики посчитали, что наиболее эффективным будет организовать файл System/38 просто как двумерную таблицу в памяти. Они также полагали, что производительность обработки повысится, если таблицу обрабатывать «на месте» без сортировки записей. Чтобы добиться этого, они встроили индекс в таблицу так, что сортировка просто не требуется (подробнее об этом — далее, в разделе «Машинные индексы»). По сути, предполагалось, что в System/38 никогда не будет программы сортировки.

Однако, такая программа была и есть. Ее написал Дик Бэйнс, назвав «Conversion Reformat Utility», вероятно, чтобы скрыть ее сущность и предотвратить использование прикладными программистами в новых проектах [ 50 ] Бессмыслица, что-то вроде «утилита переформатирования преобразования». — Прим. консультанта. . Эта программа, тем не менее, была — а, может быть, есть и по сей день — самым быстрым способом сортировки и выборки записей из больших файлов. Джим Слоан (Jim Sloan), бывший разработчик и проектировщик, участвовавший в создании компилятора CL, разработал в составе своего набора QUSRTOOL утилиту для пользователей, интерфейс которой к этой программе сортировки позволял использовать внешние имена полей.

В процессе разработки базы данных Перри Тейлор (Perry Taylor) случайно наткнулся на технический отчет Е. Ф. Кодда (E. F. Codd). Кодд, который считается создателем реляционной базы данных, работал над проектом System/R (R — реляционная) в исследовательском центре IBM в Калифорнии. Базой в определении Кодда была двумерная таблица, над которой можно было выполнять четыре элементарных операции. Первая операция — упорядочение (order) — позволяла обрабатывать строки или столбцы в определенном порядке по ключевому полю; вторая — выборка (selection) — выбирать записи по значению ключевого поля; третья — проекция (projection) — осуществлять выборку из таблицы заданных полей; и наконец, четвертая — соединение (join) —рассматривать несколько таблиц как одну большую. Таким образом, реляционная база данных представляла собой просто двумерную таблицу с операциями упорядочения, выборки, проекции и соединения.