Индекс базы данных ИРБИС — различия между версиями

Материал из Wikipedia
Перейти к: навигация, поиск
Строка 1: Строка 1:
−
== Введение ==
+
Инвертированный файл (также используется название ''инверсный файл'') используется в качестве ''индекса'' базы данных ИРБИС.
  
−
Инверсный файл состоит из 3 физических файлов, два из которых содержат словарь поисковых терминов (в структуре бинарного дерева) и третий содержит список ссылок, соответствующих каждому термину.
+
Пользователи системы ИРБИС для обозначения ''индекса'' базы данных используют термин [[Базы данных ИРБИС#Словарь базы данных ИРБИС (инвертированный файл)|''словарь'' базы данных]].
−
В бинарном дереве файл с расширением N01 содержит узлы дерева и файл с расширением L01 – листья. Записи с листьями указывают на файл ссылок IFP.
 
−
Физически взаимосвязи между файлами N01 и L01 обеспечиваются ссылками, которые представляют собой относительные адреса соответствующих записей. Относительный адрес это порядковый номер записи в данном файле. Структура записи одинакова для N01 и L01 файлов. Размер (длина) записи зависит от реализации (512;1024;2048;4096). (Таким образом, максимальный размер файлов L01 и N01 определяется как 2Гб*Размер записи) В данной реализации 2048
 
−
Адрес корневой записи файла N01 сохраняется как номер первой записи.
 
−
Смещение на запись в файле IFP сохраняется в файле L01 и имеет длину 64 байта (в данной реализации используется только младшее слово этого смещения).
 
  
−
== Формат файлов N01 и L01 ==
+
Инвертированный файл строится с использованием [[Таблица выбора полей#ТВП для инвертированного файла|''ТВП для инвертированного файла'']].
−
Эти файлы содержат  в себе индексы словаря поисковых терминов и состоят из записей (блоков) постоянной длины. Записи состоят из трех частей: лидера, справочника и ключей переменной длины.
 
  
−
{|
+
==Структура инвертированного файла==
−
|+Формат лидера записи
+
 
−
|-
+
Инвертированный файл состоит из 3 физических файлов, два из которых содержат словарь поисковых терминов (в структуре бинарного дерева), а третий содержит список [[Таблица выбора полей#ТВП для инвертированного файла|индексных ссылок]], соответствующих каждому термину.
−
!Число бит
+
 
−
!Параметр
+
В бинарном дереве файл с расширением <tt>.n01</tt> содержит узлы дерева и файл с расширением <tt>.l01</tt> – листья. Записи с листьями указывают на файл ссылок <tt>.ifp</tt>.
−
!Описание
+
 
−
|-
+
Взаимосвязи между файлами <tt>.n01</tt> и <tt>.l01</tt> обеспечиваются ссылками, которые представляют собой относительные адреса соответствующих записей. Относительный адрес это порядковый номер записи в данном файле.
−
|32
+
 
−
|NUMBER
+
Структура записи одинакова для <tt>.n01</tt> и <tt>.l01</tt> файлов. Размер (длина) записи зависит от реализации (512, 1024, 2048, 4096). Таким образом, максимальный размер файлов <tt>.l01</tt> и <tt>.n01</tt> определяется как 2 Гб * размер записи. В данной реализации размер записи 2048.
−
|номер записи(начиная с 1; в N01 файле номер первой записи равен номеру корневой записи дерева)
+
 
−
|-
+
Адрес корневой записи файла <tt>.n01</tt> сохраняется как номер первой записи.
−
|32
+
 
−
|PREV
+
Смещение на запись в файле <tt>.ifp</tt> сохраняется в файле <tt>.l01</tt> и имеет длину 64 байта (в данной реализации используется только младшее слово этого смещения).
−
|номер предыдущей записи(если нет = -1)
+
 
−
|-
+
==Формат файлов <tt>.n01</tt> и <tt>.l01</tt>==
−
|32
+
 
−
|NEXT
+
Файлы состоят из записей (блоков) постоянной длины. Записи состоят из трех частей: лидера, справочника и ключей переменной длины.
−
|номер следующей записи(если нет = -1)
+
 
−
|-
+
Формат лидера записи:
−
|16
+
{| class="standard"
−
|TERMS
+
!Число бит||Параметр||Описание
−
|число ключей в записи
+
|-
−
|-
+
|32||NUMBER||номер записи (начиная с 1; в <tt>.n01</tt> файле номер первой записи равен номеру корневой записи дерева)
−
|16
+
|-
−
|OFFSET_FREE
+
|32||PREV||номер предыдущей записи (если нет = -1)
−
|смещение на свободную позицию в записи (от начала записи)
+
|-
 +
|32||NEXT||номер следующей записи (если нет = -1)
 +
|-
 +
|16||TERMS||число ключей в записи
 +
|-
 +
|16||OFFSET_FREE||смещение на свободную позицию в записи (от начала записи)
 
|}
 
|}
  
−
Справочник это таблица, определяющая поисковый термин. Каждый ключ переменной длины, который есть в записи, представлен в справочнике одним входом следующего формата:
+
Справочник это таблица, определяющая поисковый термин. Каждый ключ переменной длины, который есть в записи, представлен в справочнике одним вхождением следующего формата:
 +
{| class="standard"
 +
!Число бит||Параметр||Описание
 +
|-
 +
|16||LEN||длина ключа
 +
|-
 +
|16||OFFSET_KEY||смещение на ключ (от начала записи)
 +
|-
 +
|32||LOW||В <tt>.n01</tt> файле: ссылка на запись файла <tt>.n01</tt> (если LOW > 0) или файла <tt>.l01</tt> (если LOW < 0), у которых 1-й ключ равен данному.
 +
 
 +
Положительное значение LOW определяет ветку индекса иерархически более низкого уровня. Самый низкий уровень индекса (LOW < 0) соответствует ссылкам на записи (листья) файла <tt>.l01</tt>.
  
−
{|
+
В <tt>.l01</tt> файле: младшее слово 8-байтового смещения на ссылочную запись в <tt>.ifp</tt>.
−
|+Формат справочника
+
|-
−
|-
+
|32||HIGH||В <tt>.n01</tt> файле: всегда 0.
−
!Число бит
 
−
!Параметр
 
−
!Описание
 
−
|-
 
−
|16
 
−
|LEN
 
−
|длина ключа
 
−
|-
 
−
|16
 
−
|OFFSET_KEY
 
−
|смещение на ключ (от начала записи)
 
−
|-
 
−
|32
 
−
|LOW
 
−
|
 
−
В N01 файле:
 
−
ссылка на запись файла N01 (если LOW > 0) или файла L01 (если LOW < 0), у которых 1-й ключ равен данному.
 
−
Положительное значение LOW определяет ветку индекса иерархически более низкого уровня. Самый низкий уровень индекса (LOW < 0)соответствует ссылкам на записи (листья) файла L01;
 
  
−
В L01 файле:
+
В <tt>.l01</tt> файле: старшее слово 8 байтового смещения на ссылочную запись в <tt>.ifp</tt>.
−
младшее слово 8 байтового смещения на ссылочную запись в IFP;
 
−
|-
 
−
|32
 
−
|HIGH
 
−
|В N01 файле: всегда 0;<br />
 
−
В L01 файле: старшее слово 8 байтового смещения на ссылочную запись в IFP
 
 
|}
 
|}
  
−
Ключи переменной длины записываются, начиная с конца записи, так что порядок входов, соответствующих им, определяется алфавитным порядком ключей. Сами ключи располагаются вплотную друг к другу без разделителей в порядке поступления на запись.
+
Ключи переменной длины записываются начиная с конца записи, так что порядок входов, соответствующих им, определяется алфавитным порядком ключей. Сами ключи располагаются вплотную друг к другу без разделителей в порядке поступления на запись.
  
 
* '''Длина справочника''' 12 * TERMS.
 
* '''Длина справочника''' 12 * TERMS.
 
* '''Длина ключей''' = [Размер записи] – OFSET_FREE.
 
* '''Длина ключей''' = [Размер записи] – OFSET_FREE.
 
* '''Размер свободного места в записи''' = 16 + 12 * TERMS - [длина ключей].
 
* '''Размер свободного места в записи''' = 16 + 12 * TERMS - [длина ключей].
−
* '''Размер записи''' зависит от реализации и может быть равен в байтах: 512 ; 1024 ; 2048 ; 4096.
+
* '''Размер записи''' зависит от реализации и может быть равен в байтах: 512, 1024, 2048, 4096.
 +
 
 +
==Формат файла <tt>.ifp</tt>==
 +
 
 +
Файл содержит список ссылок для каждого термина словаря.
 +
 
 +
Список ссылок может быть представлен в 2-х различных форматах. Выбор формата размещения ссылок осуществляется при загрузке словаря из файла <tt>.lk1</tt> (этот файл формируется после отбора и сортировки терминов) в зависимости от общего числа ссылок для данного термина. Обыкновенный формат – это заголовок блока и набор упорядоченных ссылок. По превышении определенного числа ссылок (MIN_POSTINGS_IN_BLOCK – в данной реализации 256) формат включает специальный блок и набор блоков обыкновенного формата размер которых определяется по следующей схеме: блоки 4, 8, 16, 32 Кб для общего числа ссылок соответственно 256-32000, 32000-64000, 64000-128000, 128000 и более.
  
−
== Формат файла IFP ==
 
−
Файл содержит список ссылок для каждого термина словаря. Список ссылок может быть представлен в 2-х различных форматах. Выбор формата размещения ссылок осуществляется при загрузке словаря из файла Lk1 (этот файл формируется после отбора и сортировки терминов) в зависимости от общего числа ссылок для данного термина. Обыкновенный формат – это заголовок блока и набор упорядоченных ссылок. По превышении определенного числа ссылок (MIN_POSTINGS_IN_BLOCK - в данной реализации 256) формат включает специальный блок и набор блоков обыкновенного формата размер которых определяется по следующей схеме:
 
−
блоки 4, 8, 16, 32Kb для общего числа ссылок соответственно 256-32000 ; 32000-64000 ; 64000-128000 ; 128000 и более
 
 
Такая схема оптимизирует работу с диском в процессе инвертирования записи в базах данных, характеризующихся большим количеством ссылок на термин.
 
Такая схема оптимизирует работу с диском в процессе инвертирования записи в базах данных, характеризующихся большим количеством ссылок на термин.
  
−
=== Обыкновенный формат записи IFP ===
+
===Обыкновенный формат записи <tt>.ifp</tt>===
 +
 
 
Запись состоит из заголовка и упорядоченного набора ссылок.
 
Запись состоит из заголовка и упорядоченного набора ссылок.
−
{|
+
 
−
|+Ссылка имеет следующий формат
+
Ссылка имеет следующий формат:
−
|-
+
{| class="standard"
−
!Число бит
+
!Число бит||Параметр||Описание
−
!Параметр
+
|-
−
!Описание
+
|32||PMFN||номер записи
−
|-
+
|-
−
|32
+
|32||PTAG||идентификатор поля, назначенный при отборе терминов в словарь
−
|PMFN
+
|-
−
|номер записи
+
|32||POCC||номер повторения
−
|-
+
|-
−
|32
+
|32||PCNT||номер термина в поле
−
|PTAG
 
−
|идентификатор поля, назначенный при отборе терминов в словарь
 
−
|-
 
−
|32
 
−
|POCC
 
−
|номер повторения
 
−
|-
 
−
|32
 
−
|PCNT
 
−
|номер термина в поле
 
 
|}
 
|}
  
−
{|
+
Заголовок имеет следующий формат:
−
|+Заголовок имеет следующий формат
+
{| class="standard"
−
|-
+
!Число бит||Параметр||Описание
−
!Число бит
+
|-
−
!Параметр
+
|32||LOW||младшее слово смещения на следующую запись (если нет  0)
−
!Описание
+
|-
−
|-
+
|32||HIGH||старшее слово смещения на следующую запись (если нет  0)
−
|32
+
|-
−
|LOW
+
|32||TOTP||общее число ссылок для данного термина (только в первой записи); число ссылок в данном блоке (в следующих записях)
−
|младшее слово смещения на следующую запись(если нет  0)
+
|-
−
|-
+
|32||SEGP||число ссылок в данном блоке
−
|32
+
|-
−
|HIGH
+
|32||SEGC||вместимость записи в ссылках
−
|старшее слово смещения на следующую запись(если нет  0)
 
−
|-
 
−
|32
 
−
|TOTP
 
−
|общее число ссылок для данного термина(только в первой записи); число ссылок в данном блоке(в следующих записях)
 
−
|-
 
−
|32
 
−
|SEGP
 
−
|число ссылок в данном блоке
 
−
|-
 
−
|32
 
−
|SEGC
 
−
|вместимость записи в ссылках
 
 
|}
 
|}
 +
 
Признак последнего блока – LOW = HIGH = -1
 
Признак последнего блока – LOW = HIGH = -1
  
−
=== Специальный формат записи IFP ===
+
===Специальный формат записи <tt>.ifp</tt>===
−
В этом случае первой записью является специальный блок, который представляет собой заголовок (обыкновенного формата), в котором смещения имеют специальные значения = -1001, и набор входов следующего формата:
+
 
−
{|
+
В этом случае первой записью является специальный блок, который представляет собой заголовок (обыкновенного формата), в котором смещения имеют специальные значения = -1001, и набор вхождений следующего формата:
−
|-
+
{| class="standard"
−
!Число бит
+
!Число бит||Параметр||Описание
−
!Параметр
+
|-
−
!Описание
+
|32||POSTING||1-я ссылка из записи обыкновенного формата
−
|-
+
|-
−
|32
+
|32||LOW||младшее слово смещения на следующую запись (если нет  0)
−
|POSTING
+
|-
−
|1-я ссылка из записи обыкновенного формата
+
|32||HIGH||старшее слово смещения на следующую запись (если нет  0)
−
|-
 
−
|32
 
−
|LOW
 
−
|младшее слово смещения на следующую запись (если нет  0)
 
−
|-
 
−
|32
 
−
|HIGH
 
−
|младшее слово смещения на следующую запись (если нет  0)
 
 
|}
 
|}
  
−
Число входов кратно 4. Записи, на которые ссылается специальный блок связаны между собой как описано выше. При чем общее количество ссылок для данного термина сохраняется только в специальном блоке.
+
Число вхождений кратно 4. Записи, на которые ссылается специальный блок связаны между собой как описано выше. Общее количество ссылок для данного термина сохраняется только в специальном блоке.
 +
 
 +
===Модификация записей файла <tt>.ifp</tt>===
  
−
=== Модификация записей файла IFP ===
+
При выполнении актуализации инвертированного файла могут создаваться новые дополнительные записи при добавлении новых ссылок. В этом случае создается новая запись размером, равным общему количеству ссылок, если нет специального блока, и размером, равным количеству ссылок в данной записи, если есть. Новая запись создается таким образом, чтобы не нарушалась возрастающая последовательность следования ссылок. Новая запись связывается с существующими через поле NXT_, ссылки распределяются равномерно между старой и новой записью.
−
При выполнении актуализации инверсного файла могут создаваться новые дополнительные записи при добавлении новых ссылок. В этом случае создается новая запись размером, равным общему количеству ссылок, если нет специального блока, и размером, равным количеству ссылок в данной записи, если есть. Новая запись создается таким образом, чтобы не нарушалась возрастающая последовательность следования ссылок. Новая запись связывается с существующими через поле NXT_, ссылки распределяются равномерно между старой и новой записью.
 
  
 
==Ссылки==
 
==Ссылки==
Строка 168: Строка 129:
 
См. также:
 
См. также:
 
* [[Базы данных ИРБИС]]
 
* [[Базы данных ИРБИС]]
 +
* [[Таблица выбора полей]]
  
 
Источники информации:
 
Источники информации:
Строка 175: Строка 137:
 
[[Категория:Базы данных ИРБИС]]
 
[[Категория:Базы данных ИРБИС]]
 
[[Категория:Файлы ИРБИС]]
 
[[Категория:Файлы ИРБИС]]
 +
[[Категория:Анонсированные статьи]]
 +
[[Категория:Последние анонсированные статьи]]

Версия 01:11, 21 декабря 2012

Инвертированный файл (также используется название инверсный файл) используется в качестве индекса базы данных ИРБИС.

Пользователи системы ИРБИС для обозначения индекса базы данных используют термин словарь базы данных.

Инвертированный файл строится с использованием ТВП для инвертированного файла.

Структура инвертированного файла

Инвертированный файл состоит из 3 физических файлов, два из которых содержат словарь поисковых терминов (в структуре бинарного дерева), а третий содержит список индексных ссылок, соответствующих каждому термину.

В бинарном дереве файл с расширением .n01 содержит узлы дерева и файл с расширением .l01 – листья. Записи с листьями указывают на файл ссылок .ifp.

Взаимосвязи между файлами .n01 и .l01 обеспечиваются ссылками, которые представляют собой относительные адреса соответствующих записей. Относительный адрес это порядковый номер записи в данном файле.

Структура записи одинакова для .n01 и .l01 файлов. Размер (длина) записи зависит от реализации (512, 1024, 2048, 4096). Таким образом, максимальный размер файлов .l01 и .n01 определяется как 2 Гб * размер записи. В данной реализации размер записи 2048.

Адрес корневой записи файла .n01 сохраняется как номер первой записи.

Смещение на запись в файле .ifp сохраняется в файле .l01 и имеет длину 64 байта (в данной реализации используется только младшее слово этого смещения).

Формат файлов .n01 и .l01

Файлы состоят из записей (блоков) постоянной длины. Записи состоят из трех частей: лидера, справочника и ключей переменной длины.

Формат лидера записи:

Число бит Параметр Описание
32 NUMBER номер записи (начиная с 1; в .n01 файле номер первой записи равен номеру корневой записи дерева)
32 PREV номер предыдущей записи (если нет = -1)
32 NEXT номер следующей записи (если нет = -1)
16 TERMS число ключей в записи
16 OFFSET_FREE смещение на свободную позицию в записи (от начала записи)

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

Число бит Параметр Описание
16 LEN длина ключа
16 OFFSET_KEY смещение на ключ (от начала записи)
32 LOW В .n01 файле: ссылка на запись файла .n01 (если LOW > 0) или файла .l01 (если LOW < 0), у которых 1-й ключ равен данному.

Положительное значение LOW определяет ветку индекса иерархически более низкого уровня. Самый низкий уровень индекса (LOW < 0) соответствует ссылкам на записи (листья) файла .l01.

В .l01 файле: младшее слово 8-байтового смещения на ссылочную запись в .ifp.

32 HIGH В .n01 файле: всегда 0.

В .l01 файле: старшее слово 8 байтового смещения на ссылочную запись в .ifp.

Ключи переменной длины записываются начиная с конца записи, так что порядок входов, соответствующих им, определяется алфавитным порядком ключей. Сами ключи располагаются вплотную друг к другу без разделителей в порядке поступления на запись.

  • Длина справочника 12 * TERMS.
  • Длина ключей = [Размер записи] – OFSET_FREE.
  • Размер свободного места в записи = 16 + 12 * TERMS - [длина ключей].
  • Размер записи зависит от реализации и может быть равен в байтах: 512, 1024, 2048, 4096.

Формат файла .ifp

Файл содержит список ссылок для каждого термина словаря.

Список ссылок может быть представлен в 2-х различных форматах. Выбор формата размещения ссылок осуществляется при загрузке словаря из файла .lk1 (этот файл формируется после отбора и сортировки терминов) в зависимости от общего числа ссылок для данного термина. Обыкновенный формат – это заголовок блока и набор упорядоченных ссылок. По превышении определенного числа ссылок (MIN_POSTINGS_IN_BLOCK – в данной реализации 256) формат включает специальный блок и набор блоков обыкновенного формата размер которых определяется по следующей схеме: блоки 4, 8, 16, 32 Кб для общего числа ссылок соответственно 256-32000, 32000-64000, 64000-128000, 128000 и более.

Такая схема оптимизирует работу с диском в процессе инвертирования записи в базах данных, характеризующихся большим количеством ссылок на термин.

Обыкновенный формат записи .ifp

Запись состоит из заголовка и упорядоченного набора ссылок.

Ссылка имеет следующий формат:

Число бит Параметр Описание
32 PMFN номер записи
32 PTAG идентификатор поля, назначенный при отборе терминов в словарь
32 POCC номер повторения
32 PCNT номер термина в поле

Заголовок имеет следующий формат:

Число бит Параметр Описание
32 LOW младшее слово смещения на следующую запись (если нет 0)
32 HIGH старшее слово смещения на следующую запись (если нет 0)
32 TOTP общее число ссылок для данного термина (только в первой записи); число ссылок в данном блоке (в следующих записях)
32 SEGP число ссылок в данном блоке
32 SEGC вместимость записи в ссылках

Признак последнего блока – LOW = HIGH = -1

Специальный формат записи .ifp

В этом случае первой записью является специальный блок, который представляет собой заголовок (обыкновенного формата), в котором смещения имеют специальные значения = -1001, и набор вхождений следующего формата:

Число бит Параметр Описание
32 POSTING 1-я ссылка из записи обыкновенного формата
32 LOW младшее слово смещения на следующую запись (если нет 0)
32 HIGH старшее слово смещения на следующую запись (если нет 0)

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

Модификация записей файла .ifp

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

Ссылки

См. также:

Источники информации:

Источник — «http://wiki.elnit.org/index.php?title=Индекс_базы_данных_ИРБИС&oldid=1476»