Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Последние темы форума

Показать новые сообщения »

Почтовая рассылка

Подписчиков: 11653
Последний выпуск: 19.06.2015

Структура индексного файла (.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Особенности индекса (любое из нижеследующих значений либо их сумма):
  • 1 - уникальный индекс;
  • 8 - индекс имеет дополнительный оператор
  • FOR;
  • 32 - формат компактного индекса;
  • 64 - заголовок составного индекса.
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Ключи индексов и информация (**)

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


DBF | FPT | CDX

Оставить комментарий

Комментарий:
можно использовать BB-коды
Максимальная длина комментария - 4000 символов.
 
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог