Индекс базы данных ИРБИС — различия между версиями
Sokv (обсуждение | вклад) (→Ссылки) |
Sokv (обсуждение | вклад) м (переименовал «Структура инверсного файла и форматы записей» в «Инвертированный файл») |
(нет различий)
| |
Версия 20:38, 20 декабря 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, 32Kb для общего числа ссылок соответственно 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_, ссылки распределяются равномерно между старой и новой записью.
Ссылки
См. также:
Источники информации:
