Структура индексного файла (.IDX)
В индексных файлах располагается одна запись заголовка и одна или больше записей вершин. В записи заголовка находится информация о корневой вершине, текущем размере файла, длине ключа, особенностях индекса и сигнатура, а также представление ключа* в коде ASCII, которое можно вывести на печать, и выражения FOR. Запись заголовка начинается с нулевой позиции файла.
Во всех других записях вершин содержится атрибут, количество существующих ключей и указатели на вершины, располагающиеся слева и справа (на том же уровне) от данной вершины. Помимо этого, в них находится группа символов, представляющая значение ключа, и либо указатель на вершину нижнего уровня, либо подлинный номер записи в базе данных. Размер каждой записи, которая выведена в файл, равен 512 байтам.
В приведенных ниже таблицах показан пример упорядоченной структуры дерева.
Примечания по структуре индексного файла.
(*) Тип ключа не запоминается в индексе. Он должен определяться индексным выражением.
(**) В вершине-листе все, что отлично от символьных строк, числа, используемые в качестве значений ключей и четырехбайтовые номера представляются в байтах, порядок которых изменен на противоположный (в формате Intel 8086).
(***) Если числа используются в качестве ключей, то они подвергаются специальной обработке. Они преобразовываются согласно нижеследующему способу таким образом, чтобы их можно было отсортировать с помощью такой же схемы упорядочения в коде ASCII, что и символы:
- Преобразовать число в формат с плавающей точкой IEEE.
- Изменить на противоположный порядок байтов с порядка Intel на порядок слева направо.
- Если число отрицательное, взять логическое дополнение числа (изменить на противоположные все 64 бита, 1 на 0 и 0 на 1), иначе инвертировать только самый левый бит.
Пример упорядоченной структуры дерева
Поиск ключа в приведенной ниже структуре потребует просмотра единственного пути между корневой вершиной и листом. Вершины на самом нижнем уровне являются вершинами-листьями. Так как ключи отсортированы, то все ключи в поддереве меньше либо равны родительской вершине.
На приведенном выше рисунке в качестве значений ключей используются буквы. Обычно каждый ключ имеет четырехбайтовый шестнадцатиричный номер. Номера, соответствующие ключам в листьях, - это подлинные номера базы данных, все ключи в других вершинах - это внутрииндексные указатели, им соответствующие.
Байты 12-511 в записях индексных вершин могли бы выглядеть следующим образом:
Комбинация из значения ключа и шестнадцатиричного номера будет заноситься в байты 12-511 n раз, где n - число существующих ключей.
Структура компактного индексного файла (типа .IDX)
| Запись заголовка компактного индексного файла | |
|---|---|
| Байты | Описание |
| 00-03 | Указатель на корневую вершину |
| 04-07 | Указатель на свободную в списке вершину (-1, если таковая отсутствует) |
| 08-11 | Резервируются для внутреннего использования |
| 12-13 | Длина ключа |
| 14 | Особенности индекса (любое из нижеследующих значений либо их сумма):
|
| 15 | Сигнатура индекса |
| 16-19 | Зарезервированы для внутреннего использования |
| 20-23 | Зарезервированы для внутреннего использования |
| 24-27 | Зарезервированы для внутреннего использования |
| 28-31 | Зарезервированы для внутреннего использования |
| 32-35 | Зарезервированы для внутреннего использования |
| 36-501 | Зарезервированы для внутреннего использования |
| 502-503 | По возрастанию или убыванию: (0=возрастание,1=убывание) |
| 504-505 | Зарезервированы для внутреннего использования |
| 506-507 | Длина пула выражения FOR (*) |
| 508-509 | Зарезервированы для внутреннего использования |
| 510-511 | Длина пула выражения FOR (*) |
| 510-1023 | Пул выражения ключа (не компилируется) |
(*) В этой информации отслеживается область, используемая в пуле выражения ключа.
| Запись внутренней вершины для компактного индекса | |
|---|---|
| Байты | Описание |
| 00-01 | Атрибуты вершины (любое из нижеследующих числовых значений либо их сумма): (0 - индексная вершина; 1 - корневая вершина; 2 - вершина-лист.) |
| 02-03 | Число существующих ключей (0, 1 или больше) |
| 04-07 | Указатель на вершину, расположенную непосредственно слева от данной вершины (на том же уровне; -1 - если отсутствует) |
| 08-11 | Указатель на вершину, расположенную непосредственно справа от данной вершины (на том же уровне; -1 - если отсутствует) |
| 12-511 | До 500 символов, включающих в себя значение ключа для длины ключа с четырехбайтовым шестнадцатиричным числом (хранящемся в обычном формате слева направо). Эта вершина всегда содержит ключ индекса, номер записи и внутрииндексный указатель.(**). Комбинация из значения ключа и четырехбайтового шестнадцатиричного числа будет повторена столько раз, количество которых задается в байтах 02-03. |
| Запись внешней вершины для компактного индекса | |
|---|---|
| Байты | Описание |
| 00-01 | Атрибуты вершины (любое из нижеследующих числовых значений либо их сумма) (0 - индексная вершина; 1 - корневая вершина; 2 - вершина-лист.) |
| 02-03 | Число существующих ключей (0, 1 или больше) |
| 04-07 | Указатель на вершину, расположенную непосредственно слева от данной вершины (на том же уровне; -1 - если отсутствует) |
| 08-11 | Указатель на вершину, расположенную непосредственно справа от данной вершины (на том же уровне; -1 - если отсутствует) |
| 12-13 | Свободное для распределения пространство в вершине |
| 14-17 | Маска номера записи |
| 18 | Маска запасного байтового счетчика |
| 19 | Маска хвостового байтового счетчика |
| 20 | Количество битов, используемых для номера записи |
| 21 | Количество битов, используемых для запасного счетчика |
| 22 | Количество битов, используемых для хвостового счетчика |
| 23 | Количество байтов, содержащих номер записи, запасной счетчик и хвостовой счетчик |
| 24-511 | Ключи индексов и информация (**) |
(**) Каждый элемент состоит из номера записи, запасного байтового счетчика и хвостового байтового счетчика, все в сжатом виде. Текст ключа помещается в логический конец вершины, обрабатывается он в обратном направлении, что позволяет находить элементы предшествующих ключей.