В индексных файлах располагается одна запись заголовка
и одна или больше записей вершин. В записи заголовка
находится информация о корневой вершине, текущем размере
файла, длине ключа, особенностях индекса и сигнатура, а
также представление ключа в коде ASCII, которое можно
вывести на печать, и выражения FOR. Запись заголовка
начинается с нулевой позиции файла.
Во всех других записях вершин содержится атрибут,
количество существующих ключей и указатели на вершины,
располагающиеся слева и справа (на том же уровне) от данной
вершины. Помимо этого, в них находится группа символов,
представляющая значение ключа, и либо указатель на вершину
нижнего уровня, либо подлинный номер записи в базе данных.
Размер каждой записи, которая выведена в файл, равен 512
байтам.
В приведенных ниже таблицах показан пример
упорядоченной структуры дерева.
Запись заголовка индексного файла
| Байты |
Описание |
| 00 - 03 |
Указатель на корневую вершину |
| 04 - 07 |
Указатель на свободную в списке вершину (-1, если
таковая отсутствует) |
| 08 - 11 |
Указатель на конец файла (размер файла) |
| 12 - 13 |
Длина ключа |
| 14 |
Особенности индекса (любое из нижеследующих
числовых значений либо их сумма)
| а. |
1 |
уникальный индекс |
| б. |
8 |
индекс имеет дополнительный оператор
FOR |
|
| 15 |
Сигнатура индекса (для использования в будущем) |
| 16 - 235 |
Ключевое выражение (не компилируется; до 220
символов) |
| 236 - 455 |
Выражение FOR (не компилируется; до 220 символов,
оканчивающееся пустым символом) |
| 456 - 511 |
Не используются |
Запись вершины индекса
| Байты |
Описание |
| 00 - 01 |
Атрибуты вершины (любое из нижеследующих
числовых значений либо их сумма)
| а. |
0 |
вершина индекса |
| б. |
1 |
корневая вершина |
| в. |
2 |
лист |
|
| 02 - 03 |
Количество существующих ключей (0, 1 или больше) |
| 04 - 07 |
Указатель на вершину, расположенную непосредственно слева от данной вершины (на том
же уровне; -1, если отсутствует) |
| 08 - 11 |
Указатель на вершину, расположенную непосредственно справа от данной вершины (на том
же уровне; -1, если отсутствует) |
| 12 - 511 |
До 500 символов, включающих в себя значение ключа
для длины ключа с четырехбайтовым шестнадцатеричным
числом (хранящемся в обычном
формате слева направо):
Если вершина является листом (атрибут = 02 или 03), тогда четыре байта содержат подлинный номер номер в базе данных в
шестнадцатеричном формате - иначе 4 байта содержат внутрииндексный указатель. |
Примечания по структуре индексного файла.
- Тип ключа не запоминается в индексе. Он должен
определяться индексным выражением.
- В вершине-листе все, что отлично от символьных
строк, числа, используемые в качестве значений ключей и
четырехбайтовые номера представляются в байтах, порядок
которых изменен на противоположный (в формате Intel
8086).
- Если числа используются в качестве ключей, то они
подвергаются специальной обработке. Они
преобразовываются согласно нижеследующему способу таким
образом, чтобы их можно было отсортировать с помощью
такой же схемы упорядочения в коде ASCII, что и
символы:
- Преобразовать число в формат с плавающей точкой
IEEE.
- Изменить на противоположный порядок байтов с
порядка Intel на порядок слева направо.
- Если число отрицательное, взять логическое
дополнение числа (изменить на противоположные все 64
бита, 1 на 0 и 0 на 1), иначе инвертировать только
самый левый бит.
Пример упорядоченной структуры дерева
Поиск ключа в приведенной ниже структуре потребует
просмотра единственного пути между корневой вершиной и
листом. Вершины на самом нижнем уровне являются
вершинами-листьями. Так как ключи отсортированы, то все
ключи в поддереве меньше либо равны родительской вершине.
На приведенном выше рисунке в качестве значений ключей
используются буквы. Обычно каждый ключ имеет четырехбайтовый
шестнадцатеричный номер. Номера, соответствующие ключам в
листьях, - это подлинные номера базы данных, все ключи в
других вершинах - это внутрииндексные указатели, им
соответствующие.
Байты 12-511 в записях индексных вершин могли бы
выглядеть следующим образом:
Комбинация из значения ключа и шестнадцатеричного
номера будет заноситься в байты 12-511 n раз, где n - число
существующих ключей.