Индекс базы данных ИРБИС
Инвертированный файл (также используется название инверсный файл) используется в качестве индекса базы данных ИРБИС.
Пользователи системы ИРБИС для обозначения индекса базы данных используют термин словарь базы данных.
Инвертированный файл строится с использованием ТВП для инвертированного файла.
Содержание
Структура инвертированного файла
Инвертированный файл состоит из 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_, ссылки распределяются равномерно между старой и новой записью.
Ссылки
См. также:
Источники информации:
