Метод индексированной последовательной доступа к файлам (ISAM)

Введение

Метод создания, обслуживания и манипулирования компьютерными файлами

ISAM, аббревиатура от Indexed Sequential Access Method, – это метод создания, обслуживания и манипулирования компьютерными файлами данных, позволяющий извлекать записи последовательно или произвольным образом по одному или нескольким ключам. Для быстрого поиска необходимых записей в индексированных файлах поддерживаются индексы ключевых полей. Компания IBM первоначально разработала ISAM для мэйнфреймов, но реализации доступны для большинства компьютерных систем. Термин ISAM используется для обозначения нескольких связанных понятий: продукт IBM ISAM и алгоритм, который он использует; система управления базами данных (СУБД), в которой разработчик приложения напрямую использует интерфейс программирования приложений (API) для поиска индексов с целью нахождения записей в файлах данных. В отличие от этого, в реляционной СУБД используется оптимизатор запросов, который автоматически выбирает индексы. Это также алгоритм индексации, обеспечивающий как последовательный, так и ключевой доступ к данным. Большинство СУБД используют различные варианты B-дерева для этой цели, хотя оригинальные реализации IBM ISAM и VSAM не использовали его. В наиболее общем смысле, ISAM – это любой индекс для базы данных. Индексы используются практически всеми базами данных.

Организация

В системе ISAM данные организованы в записи, состоящие из полей фиксированной длины, которые изначально хранятся последовательно в порядке ключей. Вторичные наборы записей, известные как индексы, содержат указатели на местоположение каждой записи, позволяя извлекать отдельные записи без необходимости поиска по всему набору данных. Это отличается от современных навигационных баз данных, в которых указатели на другие записи хранились непосредственно внутри самих записей. Основное преимущество ISAM заключается в том, что индексы имеют небольшой размер и могут быть быстро просмотрены, возможно, целиком в памяти, что позволяет базе данных получать доступ только к необходимым записям. Дополнительные изменения данных не требуют внесения изменений в другие данные, только в соответствующую таблицу и индексы. При создании файла ISAM индексные узлы фиксированы, и их указатели не изменяются при последующих вставках и удалениях (изменяется только содержимое листовых узлов). В результате, если количество вставок в листовой узел превышает его емкость, новые записи хранятся в цепочках переполнения. Если в таблице количество вставок значительно превышает количество удалений, эти цепочки переполнения могут постепенно становиться очень большими, что влияет на время, необходимое для извлечения записи. Реляционные базы данных могут быть легко построены на основе ISAM с добавлением логики для поддержания целостности связей между таблицами. Обычно поле, используемое в качестве связи (внешний ключ), индексируется для быстрого поиска. Хотя это медленнее, чем просто хранить указатель на связанные данные непосредственно в записях, это также означает, что изменения в физической структуре данных не требуют обновления указателей – запись останется действительной. ISAM прост в понимании и реализации, поскольку в основном состоит из прямого доступа к файлу базы данных. Компромисс заключается в том, что каждая клиентская машина должна самостоятельно управлять своим соединением с каждым файлом, к которому она обращается. Это, в свою очередь, может привести к конфликтующим вставкам в эти файлы и, как следствие, к несогласованному состоянию базы данных. Для предотвращения этого некоторые реализации ISAM предоставляют функциональность блокировки всего файла или отдельных записей. Блокировка нескольких записей сопряжена с риском возникновения взаимоблокировки (deadlock), если строго не соблюдается схема предотвращения взаимоблокировок. Проблемы блокировки и взаимоблокировки обычно решаются путем добавления клиент-серверной архитектуры, которая управляет клиентскими запросами и поддерживает порядок их выполнения. Некоторые реализации ISAM-клиент-сервера предоставляют полноценные системы управления транзакциями ACID. Это увеличивало время загрузки канала, контроллера и диска. С увеличением объемов физической и виртуальной памяти в более поздних системах это было признано неэффективным, и VSAM был разработан для изменения баланса между использованием памяти и активностью диска. Использование ISAM самомодифицируемых программ канала впоследствии вызвало трудности при поддержке CP 67 для OS/360, поскольку CP 67 копировала всю программу канала в фиксированную память при запуске операции ввода-вывода и преобразовывала виртуальные адреса в физические.

In an ISAM system, data is organized into records which are composed of fixed length fields, originally stored sequentially in key sequence. Secondary set(s) of records, known as indexes, contain pointers to the location of each record, allowing individual records to be retrieved without having to search the entire data set. This differs from the contemporaneous navigational databases, in which the pointers to other records were stored inside the records themselves. The key improvement in ISAM is that the indexes are small and can be searched quickly, possibly entirely in memory, thereby allowing the database to access only the records it needs. Additional modifications to the data do not require changes to other data, only the table and indexes in question. When an ISAM file is created, index nodes are fixed, and their pointers do not change during inserts and deletes that occur later (only content of leaf nodes change afterwards). As a consequence of this, if inserts to some leaf node exceed the node's capacity, new records are stored in overflow chains. If there are many more inserts than deletions from a table, these overflow chains can gradually become very large, and this affects the time required for retrieval of a record. Relational databases can easily be built on an ISAM framework with the addition of logic to maintain the validity of the links between the tables. Typically the field being used as the link, the foreign key, will be indexed for quick lookup. While this is slower than simply storing the pointer to the related data directly in the records, it also means that changes to the physical layout of the data do not require any updating of the pointers—the entry will still be valid. ISAM is simple to understand and implement, as it primarily consists of direct access to a database file. The trade off is that each client machine must manage its own connection to each file it accesses. This, in turn, leads to the possibility of conflicting inserts into those files, leading to an inconsistent database state. To prevent this, some ISAM implementations provide whole file or individual record locking functionality. Locking multiple records runs the risk of deadlock unless a deadlock prevention scheme is strictly followed. The problems of locking, and deadlock are typically solved with the addition of a client server framework which marshals client requests and maintains ordering. Full ACID transaction management systems are provided by some ISAM client server implementations. This increased the busy time of the channel, control unit, and disk. With increased physical and virtual memory sizes in later systems this was seen as inefficient, and VSAM was developed to alter the tradeoff between memory usage and disk activity. ISAM's use of self modifying channel programs later caused difficulties for CP 67 support of OS/360, since CP 67 copied an entire channel program into fixed memory when the I/O operation was started and translated virtual addresses to real addresses.