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
– такой страницы нет