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

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

Заголовочная запись индекса
Byte offset Описание

00 – 03

Указатель к корневому узлу

04 – 07

Указатель к списку свободных узлов ( -1, если список отсутствует)

08 – 11

Указатель на конец файла (собственно представляет собой размер файла)

12 – 13

Длина ключа

14

Опции индекса (любые приведенные численные значения или их суммы): 1 – уникальный индекс 8 – индекс имеет опцию FOR

15

Сигнатура индекса (предусмотрено для использования в будущем)

16 – 235

Выражение ключа (несомпилируемое; до 220 символов) - смотрите ссылки 1,3

236 – 455

Выражение FOR (несомпилируемое; до 220 символов завершаемое нуль терминатором - chr(0))

456 – 511

Неиспользуемые

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

00 – 01

Аттрибуты узла (любые из следующих численных значений или их суммы): 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 (collating sequence), что и символы:

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

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

FoxPro Nodes

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

Байты 12-511 в индексном узле могут выглядеть так, как показано ниже:

FoxPro Key Values

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

Expand imageСмотрите также