Страницы делятся на блоки одинакового размера. Размер блока определяется параметром oess_1::db::storage::hard_config_t::m_chain_link_size. Размер блока должен быть не меньше 8 байт и не больше размера страницы. На странице должно размещаться целое количество блоков, без остатка.
Для всех страниц используется сквозная нумерация блоков. Первый блок на первой странице имеет индекс 0, первый блок на второй странице имеет индекс (размер страницы/размер блока).
Информация в БД сохраняется в блоках. Т.е., если объем сохраняемых данных меньше, чем размер блока, то для их хранения все равно будет выделен один блок. Если размер блока меньше, чем размер сохраняемых данных, то будет выделено несколько блоков и эти блоки будут специальным образом прописаны в цепочку.
Часть страниц хранилища выполняют специальные функции -- являются заголовками логических частей. Блоки, номера которых соответствуют этим страницам, для сохранения данных не используются.
Первая страница файла является заголовком файла. Далее файл делится на логические области, которые состоят из логических сегментов. Логические области и логические сегменты имеют собственные заголовки. Все логические сегменты состоят из одинакового количества страниц. Логические области состоят из одинакового количества сегментов за исключением, возможно, последней области. В последнюю область входит столько целых логических сегментов, сколько помещается в файл.
struct file_header_t { // Количество областей, в которых есть свободные блоки. oess_1::ushort_t m_free_area_count; // Номера областей, в которых есть свободные блоки. oess_1::db::storage::area_ordinal_t m_free_areas[ m_free_area_count ]; };
Первоначально, в пустом файле данных, в file_header_t::m_free_areas находятся номера всех областей файла. После того, как в какой-либо области свободные блоки заканчиваются, номер этой области из m_free_areas изымается. Если в какую-то область возвращается свободный блок, а до этого в области свободных блоков не было, то номер области возвращается в m_free_areas.
Номера областей хранятся в m_free_areas упорядоченными по возрастанию номеров.
Размер m_free_areas определяется размером страницы. Т.е. в файле данных не может быть больше, чем (размер страницы/sizeof(oess_1::ushort_t) - 1). Если в файле физически не может разместиться столько областей, сколько их можно описать в m_free_areas, то часть заголовка файла оказывается неиспользуемой.
Заголовок области можно описать следующей структурой:
struct area_header_t { // Количество сегментов, в которых есть свободные блоки. oess_1::ushort_t m_free_segment_count; // Номера сегментов, в которых есть свободные блоки. oess_1::db::storage::segment_ordinal_t m_free_segments[ m_free_segment_count ]; };
Первоначально, в пустой области, в area_header_t::m_free_segments находятся номера всех сегментов области. После того, как в каком-либо сегменте свободные блоки заканчиваются, номер этого сегмента из m_free_segments изымается. Если в какой-то сегмент возвращается свободный блок, а до этого в сегменте свободных блоков не было, то номер сегмента возвращается в m_free_segments.
В m_free_segments хранятся относительные номера сегментов. Т.е. номера сегментов уникальны только в рамках одной области. Для полной идентификации сегмента нужно знать порядковый номер области, которой он принадлежит и порядковый номер сегмента в области.
Номера сегментов хранятся в m_free_segments упорядоченными по возрастанию номеров.
Количество сегментов, которые могут входить в область определяется размером страницы: (размер страницы/sizeof(oess_1::ushort_t) - 1).
Заголовок сегмента можно описать следующими структурами:
struct block_info_t { // Собственный идентификатор блока. oess_1::uint_t m_self_id; // Идентификатор следующего блока в цепочке. oess_1::uint_t m_next; }; struct segment_header_t { // Количество свободных блоков в сегменте. oess_1::uint_t m_free_blocks_count; // Количество занятых блоков в сегменте. oess_1::uint_t m_used_blocks_count; // Описатели свободных блоков. block_info_t m_free_blocks[ m_free_blocks_count ]; // Описатели занятых блоков. block_info_t m_used_blocks[ m_used_blocks_count ]; };
Размер сегмента зависит от размера страницы: (размер страницы/sizeof(block_info_t)). В число страниц сегмента так же входит и заголовок сегмента. Т.е. реально, в сегменте находится одна страница заголовка + (размер сегмента - 1) страниц данных. Т.к. часть блоков, которая попадает на страницу заголовка сегмента, не может быть использована, то часть segment_header_t не используется.
Для пустого сегмента segment_header_t::m_free_blocks_count содержит общее количество блоков данных сегмента, а в m_free_blocks находятся описатели этих блоков. При выделении блока под данные, его описатель перемещается из m_free_blocks в m_used_blocks. Т.о. в полностью занятом сегменте описатели всех блоков находятся в m_used_blocks.
Для свободных блоков block_info_t::m_next всегда содержит значение oess_1::db::storage_t::invalid_chain_id. Для занятых блоков block_info_t::m_next содержит идентификатор следующего блока цепочки или oess_1::db::storage_t::invalid_chain_id, если блок является последним блоком цепочки.
Алгоритм выделения блоков следующий:
Этот алгоритм позволяет:
1.4.7
