Формат файла .n01 (Словарь ИРБИС64 - Узлы дерева поиска)

НАЧАЛО >> Нативный провайдер данных DP_Irbis64Native >> Формат файла .n01 (Словарь ИРБИС64 - Узлы дерева поиска)📄 Скачать в DOCX

Файл .n01 является частью инвертированного файла (словаря) системы ИРБИС64. Он отвечает за хранение верхних (индексных) уровней B-дерева и обеспечивает быструю навигацию (поиск терминов), перенаправляя к файлам листовых узлов .l01 и файлу ссылок .ifp.

1. Физическая структура

Файл логически разбит на блоки фиксированного размера. Размер одного блока (SIZE_OF_TERMS_BLOCK) составляет 2048 байт.

Максимальный размер такого файла словаря может достигать примерно 4000 Гб (ограничивается максимальным значением, которое может хранить 32-битное целое число для номера блока, умноженным на размер блока).

1.1. Порядок байт (Endianness)

Все бинарные числовые значения в файле (int, unsigned short, а также половины структуры TInt64) записываются на диск в формате Big-Endian (старший байт по меньшему адресу). Это связано с необходимостью сохранения кроссплатформенной совместимости со стандартом CDS/ISIS.

2. Структура отдельного блока (Node)

Каждый блок размером 2048 байт имеет следующую внутреннюю организацию:

[Заголовок блока] [Массив указателей на ключи] ... [Свободное пространство] ... [Сами ключи (термины)]

Ключи добавляются с конца блока (навстречу заголовкам), а массив заголовков ключей растет от начала.

2.1. 1. Заголовок блока (Header_block)

Заголовок блока (THeader_Block) всегда располагается в начале блока и занимает 16 байт.

Поле Тип Размер Описание
number int 4 байта Номер текущего блока. Для самого первого блока файла (заголовочного) это поле хранит указатель на номер первого свободного блока. Само значение номера блока всегда положительное.
prev int 4 байта Номер предыдущего блока (связанный список). Отрицательное значение (обычно -1) или 0 означает отсутствие связи (например, начало списка).
next int 4 байта Номер следующего блока. Отрицательное значение (обычно -1) или 0 означает отсутствие связи (например, конец списка).
terms unsigned short 2 байта Количество терминов (ключей), содержащихся в текущем блоке.
offset_free unsigned short 2 байта Смещение на свободное пространство от начала блока. Указывает на границу, до которой записаны ключи со стороны конца блока. Для полностью пустого блока равно 2048, при добавлении термина значение уменьшается на его длину.

2.2. 2. Заголовок ключа (Header_key)

Следом за Header_block идет массив элементов Header_key (THeader_Key), по одному на каждый термин в блоке. Описание одного элемента занимает 12 байт.

Поле Тип Размер Описание
len unsigned short 2 байта Длина ключа (термина). Максимальная длина термина ограничена 255 символами.
offset_key unsigned short 2 байта Смещение на начало ключа (строки символов) относительно начала блока.
nxt TInt64 (struct) 8 байт 64-битное число, записанное в виде двух 32-битных частей. На диске сначала располагается LowWord (4 байта), а затем HiWord (4 байта). В индексном файле .n01 младшие 4 байта (LowWord) интерпретируются как знаковое целое число (int), где знак определяет тип целевого файла:
• = 0 — пустая ссылка;
• > 0 — ссылка на номер блока в текущем индексном файле .n01 (переход на подуровень);
• < 0 — ссылка на номер блока в файле листьев .l01. Отрицательный знак выступает специальным флагом, указывающим на файл .l01, а сам номер блока берется по модулю.

Примечание: исторически nxt состоял из полей block и flag по 4 байта (до введения поддержки больших файлов > 2Gb в 2002 году), теперь это структура TInt64.

2.3. 3. Термины (Ключи)

Сами строковые значения ключей записываются, начиная с конца блока. Значение смещения для каждого термина определяется в поле offset_key.

3. Расчет свободного места

Свободное (незанятое) пространство в блоке можно вычислить по формуле:

Свободно = offset_free - (terms * 12) - 16

Где:

4. Дополнительные характеристики