Индексно-последовательные файлы

Наборы данных с индексно-последовательной организацией располагаются в основном на магнитных дисках. Доступ к записям этих наборов осуществляется двояко: прямой доступ по значению ключа и последовательный доступ в порядке возрастания значений их ключей. Можно выполнить последовательную обработку либо всего набора данных, либо его части в пределах заданного диапазона значений ключей.

Наборы данных индексно-последовательного доступа можно представить в виде древовидной структуры определенной высоты. В примере, показанном на рис. 2.8 высота дерева равна 3, листьевые вершины дерева соответствуют дорожкам магнитного диска.

Рис.2.8 Организация индексно-последовательного файла

Каждая дорожка диска может содержать несколько записей, в каждой из которых в определенном месте (в данном случае в начале) указывается ключ записи. Узлы, непосредственно предшествующие листьям, соответствуют индексу дорожки. Каждой занятой дорожке цилиндра в индексе дорожек соответствует один элемент, содержащий адрес дорожки и значение ключа последней записи на этой дорожке. При заполнении записями очередной дорожки диска происходит формирование нового элемента индекса дорожек и осуществляется переход на следующую дорожку.

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

1. Если максимальная длина записи превысит длину одной дорожки диска, то возникают трудности, связанные с общей организацией этих данных;

2. Трудно сформировать набор данных, располагающийся на дисках разного типа;

3. При большом количестве добавлений в набор данных новых записей значительно усложняется его структура и снижается эффективность поиска и использования пространства памяти.