Introduction

Очень краткое описание.

Статья не закончена!

Details

Несколько вводных слов

Следует различать индекс таблицы и индекс записи. Индекс таблицы - это совокупность всех индексов каждой записи таблицы.

Индекс записи таблицы данных - это некая последовательность байт. Байты эти вычисляются специальным образом из записи таблицы данных. И эти байты обладают специальным свойством - если одна запись должна идти раньше другой записи, то байты индекса первой записи будут меньше, чем байты индекса второй записи. Меньше - имеется ввиду обычное двоичное сравнение.

Самое большую проблему в таком преобразовании занимают строки. Чтобы долго не распинаться, сразу дам ссылку Collation.

1С для вычисления индексов строк использует библиотеку ICU. В 1С 8.1 использовалась библиотека ICU версии 3.4, в 1C 8.2 до версии 8.2.13 - библиотека версии 4.0, в 8.2.14 и далее - версии 4.6. Разные версии библиотеки для одних и тех же строк выдают разные последовательности байт, поэтому значения индексов в файлах 1CD разных версий будут разными. По сути, конвертация базы при изменении версии файла 1CD заключается в простой переиндексации таблиц с использованием соответствующей версии библиотеки ICU.

В 1С 8.0 использовалась какая-то своя реализация индексации строк, определить, какой точно алгоритм там использовался, мне не удалось.

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

В файле индексов таблицы хранятся сразу все индексы. Поэтому суммарный объем всех индексов таблицы не может превышать 4 гигабайта.

Файл индексов состоит из страниц длиной 0x1000 байт, т.е. размер страницы индексов совпадает с размером блока файла 1CD. Нулевая страница хранит ссылки на страницы описания каждого индекса. Страница описания каждого индекса хранит ссылки на корневые страницы двоичного дерева. Если уровней в дереве больше одного, то корневая страница хранит ссылки на страницы дерева следующего уровня. Те, в свою очередь, также могут хранить ссылки на страницы следующего уровня и т.д.

Страница 0

Структура страницы 0: struct page0{ unsigned int first_free_page; unsigned int index_offset[num_indexes]; }; * first_free_page – это индекс первой свободной страницы в файле индексов (0 – свободных страниц нет) * index_offset – массив смещений страниц описания индексов.

Общее количество индексов num_indexes определяется в описании таблицы. Порядок следования индексов тот же самый, что и в разделе Indexes описания таблицы. Предположительно, максимальное количество индексов равняется 1023, иначе массив index_offset не уместится на одной странице.

Примечание: first_free_page содержит именно индекс страницы, т.е. чтобы получить смещение страницы в файле индексов нужно этот индекс умножить на 0x1000, в то время как массив index_offset содержит уже готовые смещения страниц, т.е. числа, кратные 0x1000.

Структура пустой страницы

struct free_page{ unsigned int next_free_page; }; * next_free_page – индекс следующей свободной страницы в файле индексов (0 – это последняя свободная страница)

Структура страницы описания индекса

struct descr_page{ unsigned int root_offset; unsigned short int index_length; char unknown; // 0x80 }; * root_offset – смещение в файле индексов корневой страницы индекса * index_length – длина одной записи индекса

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

Значения битовых флагов flags

const int page_is_root = 1; // бит 0 const int page_is_leaf = 2; // бит 1 Следующие две описанные структуры (страницы-ветки и страницы-листа) начинаются с полей flags. Нулевое значение бита 1 означает, что это страница-ветка, иначе это страница-лист. Ненулевое значение бита 0 указывает на то, что это корневая страница дерева индексов (не забываем, что корневая страница может быть как веткой, так и листом).

На самом деле, у страниц-веток и страниц-листов совпадает структура первых 12 байт.

Структура страницы-ветки индекса

struct branch_page{ unsigned short int flags; // offset 0 unsigned short int number_indexes; // offset 2 unsigned int prev_page; // offset 4 unsigned int next_page; // offset 8 branch_record records[number_indexes]; // offset 12 }; * flags – набор битовых флагов, определяющий тип страницы * number_indexes – количество индексов, записанных на данной странице * prev_page – смещение в файле индексов предыдущей страницы-ветки того же уровня. 0xffffffff – такой страницы нет * next_page – смещение в файле индексов следующей страницы-ветки того же уровня. 0xffffffff – такой страницы нет * records – массив структур branch_record struct branch_record{ unsigned char end_index[index_length]; unsigned int end_table_record_index; // reverse byte order! unsigned int start_child_page; // reverse byte order! }; * end_index - значение индекса последней записи на странице следующего уровня * end_table_record_index - индекс (номер) записи в файле записей таблицы, значение индекса которой содержится в end_index. Значение записано с обратным порядком байт (первый байт старший). * start_child_page - адрес (смещение в файле индексов) подчиненной страницы (страницы следующего уровня). Значение записано с обратным порядком байт (первый байт старший).

Структура страницы-листа индекса

struct leaf_page{ unsigned short int flags; // offset 0 unsigned short int number_indexes; // offset 2 unsigned int prev_page; // offset 4 unsigned int next_page; // offset 8 unsigned short int freebytes; // offset 12 unsigned int numrecmask; // offset 14 unsigned short int leftmask; // offset 18 unsigned short int rightmask; // offset 20 unsigned short int numrecbits; // offset 22 unsigned short int leftbits; // offset 24 unsigned short int rightbits; // offset 26 unsigned short int recbytes; // offset 28 char packed_index_data[4066]; // offset 30 (4066 = 0x1000 - 30) }; * flags – набор битовых флагов, определяющий тип страницы * number_indexes – количество индексов, записанных на данной странице * prev_page – смещение в файле индексов предыдущей страницы-ветки того же уровня. 0xffffffff – такой страницы нет * next_page – смещение в файле индексов следующей страницы-ветки того же уровня. 0xffffffff – такой страницы нет