|
|
Структура
индексного файла (.IDX)
В индексных файлах располагается одна запись заголовка и одна или больше
записей вершин. В записи заголовка находится информация о корневой вершине,
текущем размере файла, длине ключа, особенностях индекса и сигнатура,
а также представление ключа* в коде 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), иначе инвертировать только самый левый
бит.
[Оглавление]
|
|
