Структура файла индекса (.IDX)

В состав файла индекса входит одна запись заголовка и одна или несколько записей узлов. Запись заголовка содержит информацию о корневом узле, о текущем разме е файла, длине ключа, опциях и сигнатуре индекса, а также печатаемые ASCII-пре ставления ключа (1) и выражений FOR. Запись заголовка начинается с позиции 0 в файле.

Остальные записи узлов содержат атрибуты данного узла, число имеющихся ключей и указатели на узел слева от текущего и узел справа (на том же уровне). Здесь также содержится группа символов, представляющих значение ключа и либо указатель на узел низшего уровня, либо номер самой записи таблицы. Размер каждой записи, помещаемой в файл, равен 512 байтам.

Запись заголовка индекса

Смещение в байтах	Описание
00-03	Указатель на корневой узел
04-07	Указатель на список свободных узлов ( 1, если список отсутствует)
08-11	Указатель на конец файла (размер файла)
12-13	Длина ключа
14	Опции индекса (любое из нижеприведенных числовых значений или их сумма): a) 1 уникальный индекс б) 8 индекс с предложением FOR
15	Сигнатура индекса (для использования в будущем)
16-235	Выражение ключа (неоткомпилированное; до 220 символов) (1,3)
236-455	Выражение FOR (неоткомпилированное; до 220 символов, заканчивающихся байтом с нуль-символом)
456-511	Не используются

Запись узла индекса

Смещение в байтах	Описание
00-01	Атрибуты узла (любое из нижеприведенных числовых значений или их сумм): a) 0 узел индекса б) 1 корневой узел в) 2 узел-лист
02-03	Количество имеющихся ключей (0, 1 или несколько)
04-07	Указатель на узел, расположенный непосредственно слева от текущего (на том же уровне; -1, если слева узлов нет)
08-11	Указатель на узел, расположенный непосредственно справа от текущего (на том же уровне; -1, если справа узлов нет)
12-511	До 500 символов, содержащих значение каждого ключа и четырехбайтный шестна цатеричный номер (хранящийся в обычном формате с порядком байтов слева направо): Если узел является листом (атрибут = 02 или 03), то эти четыре байта содержат омер самой записи таблицы в шестнадцатеричном формате; в противном случае 4 айта содержат внутрииндексный указатель. (2) Количество комбинаций "ключ/четырехбайтный шестнадцатеричный номер", входящих в запись, определяется содержимым байтов 02-03.

Примечания

(1) Тип ключа не хранится в индексе. Он должен определяться выражением ключа.

(2) Все данные, за исключением символьных строк, чисел, используемых в качестве з ачений ключа, и четырехбайтных номеров в записи листа, представляются в фо мате с обратным порядком байтов (формат Intel 8086).

(3) Числа, используемые в качестве ключей, представляют собой особый случай. Они преобразуются с помощью описанного ниже алгоритма, чтобы их можно было сорти овать с помощью той же последовательности сортировки ASCII, что и символы:

a) Преобразуйте число в формат IEEE с плавающей запятой.

б) Измените порядок байтов: вместо формата Intel 8086 установите порядок сле ования слева направо.

в) Если число было отрицательным, возьмите его логическое дополнение (инверти уйте все 64 бита: замените 1 на 0, 0 на 1); в противном случае инвертируйте то ько самый левый бит.

Пример упорядоченной древовидной структуры

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

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

Байты 12-511 записи узла индекса можно рассматривать следующим образом:

Комбинация "значение ключа/шестнадцатеричный номер" входит в байты 12-511 ров о n раз, где n количество присутствующих ключей.