The UNESCO micro CDS/ISIS Software

7.1. Введение

Инвертированный файл CDS/ISIS состоит из шести физических файлов, пять из которых содержат словарь терминов поиска (организованный как В-дерево), а шестой содержит список указателей, связанных с каждым термином. В порядке оптимизации дисковой памяти, два разделенных В-дерева взаимосвязаны, одно для терминов длиной до 10 символов (запоминаемых в файлах .N01/.L01) и другое для терминов длиннее, чем 10 символов, до максимума в З0 символов (запоминаемых в файлах .N02/.L02). Файл CNT содержит управляющие поля для обоих В-деревьев. В каждом файле В-дерева .NOx содержатся ветви дерева, а в файле .L0x содержатся листья. Записи листьев указывают на соответствующие регистрации файла .IFP.

Взаимосвязь между различными файлами схематически представлена на рис. 67. Физическая связь между этими шестью терминами - это указатель, который представляет относительный адрес записи, на который он указывает. Относительный адрес - это обычный номер записи в данном файле (т. е. первая запись имеет номер 1, вторая - 2 и т. д.). Файл .CNT указывает на файл .N0x, N0x указывает на файл .L0x, а .L0x указывает на .IFP. Так как .IFP - упакованный файл, указатель из .L0x на .IFP имеет две компоненты: номер блока и смещение в блоке, представленные каждый раз как целые.

7.2. Формат файла .CNT

Этот файл содержит две 26-байтовые записи (для каждого В-дерева), содержащие следующие 10 целых (поля, отмеченные *, являются З1-битовыми целыми со знаком):

IDTYPE - Тип В-дерева (1 для .N01/.L01, 2 для .N02/.L02);

ORDN - Порядок ветвей (каждая запись .N0x содержит не более 2*ORDN ключей);
ORDF - Порядок листьев (каждая запись .LOx содержит не более 2*ORDF ключей);
N - Число буферов в памяти, предназначенных для ветвей;

К - Число буферов, предназначенных для 1-го уровня индекса ( K ( N );
LIV -   Текущий номер индексных уровней;
POSRX *   Указатель на корневую запись в .N0x;
NMAXPOS *   Следующая доступная позиция в файле .N0x;
FMAXPOS *   Следующая доступная позиция в файле .L0x;
ABNORMAL - Формальный индикатор нормализации В-дерева (0, если В-дерево ненормализовано, 1, если В-дерево нормализовано). В-дерево является ненормализованным, если файл веток .N0x содержит только корень.

ORDN, ORDF, N и К фиксированы для данной сгенерированной системы. Обычно эти значения следующие:

ORDN=5; ORDF=5; N=15; K=5 для обоих В-деревьев.

Другие значения устанавливаются по запросу при генерации В-дерева.

7.3. Формат файлов .N0x

Эти файлы содержат индекс(ы) словаря терминов поиска (.N01 для терминов, короче 10 символов и .N02 для терминов, длиннее 10 символов). Файл .N0x имеет записи следующего формата (поля, отмеченные * являются З1-битовыми целыми со знаком):

POS * целое, указывающее относительный номер записи (1 для первой, 2 для второй и т. д.);
ОСК   целое, указывающее число активных ключей в записи ( 1 <= OCK <= 2*ORDN );
IT - целое, указывающее тип В-дерева (1 для .N01 и 2 для.N02);
IDX - массив входов ORDN (ОСК из которых активны), каждого следующего формата:

   KEY строка символов фиксированной длины LEx (LE1=10, LE2=30);
   PUNT указатель на запись .N0x (если PUNT) 0) или .L0x (если PUNT( 0), чей IDX(1).KEY=KEY.PUNT=0 указывает на активный вход. Положительный PUNT указывает ветвь индекса иерархически более высокого уровня. Самый высокий уровень индекса (PUNT) 0) указывает на лист в файле .L0x.

7.4. Форматы файлов .L0x

Эти файлы содержат словарь терминов поиска (.L01 для терминов, короче 10 символов, и .L02 для терминов, длиннее 10 символов). Записи файла .L0x имеют следующий формат (поля со * - 31-битовые целые со знаком):

POS  * целое, указывающее отностельный номер записи (1 для первой, 2 для второй и т. д.);
ОСК    целое, указывающее число активных ключей в записи ( 1 <= OCK <= 2*ORDF );
IT    целое, указывающее тип В-дерева (1 для .N01, 2 для .N02);
PS * указатель на применение записи .L0x (т. е. запись, чей IDX[1].KEY является непосредственным приемником для IDX[OCK].KEY в этой записи (это используется для ускорения последовательного доступа к файлу));
IDX  массив ORDN входов (ОСК из которых активны), каждого следующего формата:

  KEY строка символов фиксированной длины LEx (LE1=10, LE2=30);
  INFO указатель на запись .IFP, где список отправленных записей связан с начальным KEY. Этот указатель состоит из двух 31-битовых целых со знаком следующего вида:
         INFO[1] * относительный номер блока в .IFP
         INFO[2] * смещение (число слов относительно
                           0) к списку отправленных.

7.5. Формат файла .IFP

Этот файл содержит список указателей для каждого термина словаря. Каждый список указателей имеет впереди указатель формата. Файл разбит на блоки по 25 символов, где (для первоначальной загрузки и сжатия файла) размещен список указателей для каждого термина, исключая отмеченное выше. Общий формат любого блока следующий:

IFPBLK 31-битовое целое со знаком, указывающее номер блока для него (блоки нумеруются с 1);
IFPREC массив 127 З1-битовых целых со знаком;
IFPREC[1] и IFPREC[2] первого блока являются указателями на следующую свободную позицию в файле .IFP.

Указатели из .L0x на .IFP и указатели в .IFP cостоят из двух З1-битовых целых со знаком: первое целое - это номер блока, а второе целое - это смещение слова в IFPREC (например, смещение первого слова в IFPREC - это 0). Список указателей по отношению к первому термину поиска будет начинаться с 1/0.

Каждый список указателей состоит из заголовка (5 двойных слов), следующего за текущим списком указателей (8 байт для каждого указателя). Заголовок имеет следующий формат (каждое поле - это З1-битовое целое со знаком):

IFPNXTB  * Указатель следующего сегмента (номер блока);
IFPNXTP  * Указатель следующего сегмента (смещение);
IFPTOTP  * Общее число указателей (только в первом сегменте);
IFPSEGP * Число указателей в этом сегменте ( IFPSEGP <=IFPTOTP );
IFPSTGC * Возможность сегмента (т. е. число указателей, которые могут быть записаны в этот сегмент).

Каждый указатель - это 64-битовая строка, разбитая следующим образом:

PMFN  (24 бита) MFN;
PTAG  (16 бит)  Идентификатор поля (присвоенный в ТВП);
POCC  (8 бит)   Число вхождений;
PCNT  (16 бит)  Последовательный номер термина в поле.

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

Список указателей записывается в возрастающей последовательности: PMFN/PTAG/POCC/PCNT. Когда инвертированный файл загружается последовательно (например, после пустого инвертированного файла, сгенерированного ISISINV), каждый список содержит один или более соответствующих сегментов. Если IFPTOT<=32768, тогда IFPNXTB/IFPNXTP=0/0 и IFPTOT=IFPSEGP=IFPSEGC.

При выполнении обновления, могут создаваться дополнительные сегменты, если отправления должны добавиться. В этом случае новый сегмент с помощью возможностей IFPTOTP создается и связывается с другими сегментами (через указатель IFPNXTB/IFPNXTP) таким путем, что последовательность PMFN/PTAG/POCC/PCNT сохраняется. Это расщепляет вхождение отправленных в сегменте, где новое отправленное должно быть вставлено, что эквивалентно разделению между этим сегментом и вновь созданным сегментом. Новые сегменты записываются в конец файла (который сохраняет в IFPREC[1]/IFPREC[2] первого блока .IFP).

Для примера, добавим, что новое отправленное Рх должно быть вставлено между Р2 и Р3 следующим обазом:

после раскола (и добавления, что следующая свободная позиция в .IFP  - это 3/4), список отправленных будет содержать следующие сегменты:

В этой ситуации не будет создаваться новый сегмент, пока оба сегмента не будут закончены. Как указано выше, список отправленных обычно записывается один за другим. Тем не менее, в порядке обеспечения доступа к файлу .IFP, сегменты записываются таким путем, что:

1) заголовок и первое отправленное в каждом списке (28 байт) никогда не раскалываются на два блока;
2) отправленное никогда не раскалывается между двумя блоками; если не хватает памяти в текущем блоке, отправленное целиком записывается в следующем блоке.