The UNESCO micro CDS/ISIS Software
Приложение 7
Структура инвертированного файла и форматы записей
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 для обоих В-деревьев.
_______________________________________________________________________
_____________
Адрес корня файл .CNT
------------- --------------
I файл .C0x
I
-----------------------------------
Ключ 1 Ключ 2 ... Ключ N Корень
-----------------------------------
I I
__I I_____________
I I
------------------------ ------------------------ Индекс
Ключ 1 Ключ 2...Ключ N ... Ключ 1 Ключ 2...Ключ N 1 уровня
------------------------ ------------------------
I I
... ...
I I
I I
------------------------ ------------------------ Индекс
Ключ 1 Ключ 2...Ключ N ... Ключ 1 Ключ 2...Ключ N последнего
------------------------ ------------------------ уровня
I I --------------
I I файл .L0x
I I
I I
------------------------ -------------------------
Ключ 1 Ключ 2...Ключ N ... Ключ 1 Ключ 2...Ключ N
------------------------ -------------------------
I -------------
I файл .IFP
I
---------------------
Y1 Y2 Y3 ... YN
---------------------
Рис.67: Структура инвертированного файла
------------------------------------------------------------------------
Другие значения устанавливаются по запросу при генерации
В-дерева.
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 следующим обазом:
----------------------
00555 I Р1 Р2 Р3 Р4 Р5
----------------------
после раскола (и добавления, что следующая свободная позиция в
.IFP - это 3/4), список отправленных будет содержать следующие
сегменты:
----------------------
34535 I P1 P2 Px -- --
----------------------
I
I
----------------------
00535 I P3 P4 P5 -- --
----------------------
В этой ситуации не будет создаваться новый сегмент, пока
оба сегмента не будут закончены. Как указано выше, список отп-
равленных обычно записывается один за другим. Тем не менее, в
порядке обеспечения доступа к файлу .IFP, сегменты записываются
таким путем, что:
1) заголовок и первое отправленное в каждом списке (28
байт) никогда не раскалываются на два блока;
2) отправленное никогда не раскалывается между двумя бло-
ками; если не хватает памяти в текущем блоке, отправленное це-
ликом записывается в следующем блоке.
[К оглавлению]