Базы данных -> FoxPro -> DBF - Структура базы данных

В индексных файлах располагается одна запись заголовка и одна или больше записей вершин. В записи заголовка находится информация о корневой вершине, текущем размере файла, длине ключа, особенностях индекса и сигнатура, а также представление ключа* в коде ASCII, которое можно вывести на печать, и выражения FOR. Запись заголовка начинается с нулевой позиции файла.

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

В приведенных ниже таблицах показан пример упорядоченной структуры дерева.

Примечания по структуре индексного файла.

(*) Тип ключа не запоминается в индексе. Он должен определяться индексным выражением.

(**) В вершине-листе все, что отлично от символьных строк, числа, используемые в качестве значений ключей и четырехбайтовые номера представляются в байтах, порядок которых изменен на противоположный (в формате Intel 8086).

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

• Преобразовать число в формат с плавающей точкой IEEE.
• Изменить на противоположный порядок байтов с порядка Intel на порядок слева направо.
• Если число отрицательное, взять логическое дополнение числа (изменить на противоположные все 64 бита, 1 на 0 и 0 на 1), иначе инвертировать только самый левый бит.

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

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

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

Байты 12-511 в записях индексных вершин могли бы выглядеть следующим образом:

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

Структура компактного индексного файла (типа .IDX)

(*) В этой информации отслеживается область, используемая в пуле выражения ключа.

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