<<< стр.3 >>>

Страницы описания свободного места

Последняя из вспомогательных страниц - страница описания свободного места (Space Inventory Page). Страницы этого типа показывают, является ли данная страница распределённой (в смысле "зарезервированной"), заполнена ли она и насколько. Именно страница этого типа следует в БД за страницей-заголовком. Как и все страницы, страница описания свободного места начинается заголовком, указывающим тип страницы. Остальная часть страницы представляет собой массив 1-битных кластеров, которые соответствуют страницам в БД. Каждая страница, исключая страницу-заголовок, независимо от типа представлена кластером на одной из страниц описания свободного места. В заголовок страниц этого типа не входит указатель на следующую страницу данного типа, не представлены они и в таблице RDB$PAGES. Страницы этого типа расположены в БД через равные промежутки, таким образом, InterBase вычисляет расположение следующей страницы этого типа исходя из размера страницы БД и длины заголовка.
Когда происходит добавление страницы к таблице или индексу, InterBase изменяет состояние соответствующего кластера на одной из страниц описания свободного места. Ошибка "висячая страница" (orphan page) происходит, когда сервер останавливается в середине процесса размещения новой страницы. На странице описания свободного места такая страница отмечена как размещённая, а на самом деле это не так.

Страница генераторов

Страница генераторов (Generator Page) состоит из заголовка и массива 32-разрядных чисел, которые представляют собой текущие значения генераторов БД. Индексом в этом массиве служит порядковый номер генератора. Страницы этого типа представлены в таблице RDB$PAGES.

Главная страница индексов

Каждая таблица БД, даже та, у которой нет ни одного индекса, имеет главную страницу индексов. На этой странице должен быть описан (перечислены поля индексации) каждый индекс таблицы БД. Также здесь указывается полезность (selectivity) индекса, которая может быть рассчитана как отношение числа различающихся индексных полей внутри индекса и среднего количества записей. Среднее количество записей - это число страниц БД, занятых данной таблицей, делённой на максимальное количество записей на странице. Полезность индекса - чрезвычайно важный показатель, на основании которого InterBase оптимизирует выполнение запросов.
В первых версиях InterBase все описания индексов для таблицы БД должны были располагаться на одной главной странице индексов, и для преодоления этого ограничения приходилось увеличивать размер страницы БД.

Страницы индексов (B-деревья)

Заголовок страницы индексов включает тип страницы и номер следующей страницы индексов для данной таблицы БД. Также эти страницы называют корзинами (buckets).
Индексы из-за своей структуры напоминают перевёрнутые деревья. Главная страница индексов указывает на верхнюю, "корневую", страницу индекса, содержащую указатели на страницы более низкого уровня, те, в свою очередь, указывают на страницы ещё более низкого уровня и т.д. В пределах одного уровня каждая страница указывает на соседнюю "справа"; соседняя же страница указателя на данную, "левую" по отношению к ней, не имеет.
Когда происходит заполнение индексной страницы А, она делится пополам так, что половина записей остаётся, а другая половина перемещается на новую индексную страницу В. Указатель на новую страницу добавляется к странице, располагающейся выше на нашем перевёрнутом дереве (это та страница, которая раньше указывала на страницу А до её разделения). Если происходит разделение страницы на вершине "корне" дерева, то создаётся новая "корневая" страница и изменяется соответствующий указатель на главной странице индексов.
На нижнем уровне записи страницы индексов состоят из префикса, значения ключа и номера строки записи в таблице. На верхних уровнях они включают в себя префикс, значение ключа и номер страницы, которая начинается с записей с соответствующим значением ключа. Если страница начинается с тех же значений ключа, что и предшествующая, то первое недублированное значение перемещается на следующий уровень; если же вся страница целиком состоит из записей, содержащих одни и те же значения ключа, то она не имеет "потомков".
Даты и числа преобразуются в такой формат представления, при котором байты идут слева направо. Сделано это и для сжатия (см. ниже). Все числа в ключе представляются как вещественные с двойной точностью. Перед самим числом записывается его длина (как в Varchar). Если ключевое поле задано как символьное, причём сортировка символов в нём не соответствует сортировке соответствующих кодов символов, то данные приводятся к такому представлению, при котором порядок сортировки символов соответствует порядку сортировки их кодов. Этот процесс может увеличить длину значений ключа.
Значения ключа хранятся в сжатом виде. Если строка заканчивается одним или несколькими пробелами, то они отсекаются. Из-за этого получаются значения ключа переменной длины, что вынуждает добавлять в конец байт-указатель конца значения.
Но наиболее важно сжатие начала ключа. На отдельной странице индексов первое значение ключа появляется без сжатия начала. Во всех последующих значениях опускаются общие первые байты с предыдущим значением. В начала значения пишется общее количество пропущенных байтов. Поясним вышесказанное примером:

Если исходная последовательность значений ключа
aaaa aaab aabc aabd abcd bcde bcde
то в файле БД InterBase она выглядит следующим образом:
0 aaa 3 b 2 bc 3 d 1 bcd 0 bcde 4
Пробелы в примере использованы для удобства чтения, в реальном файле их, естественно, не было бы.
Следует отметить, что такой простой алгоритм сжатия очень эффективен в данном случае благодаря тому, что значение любого поля во время индексации приводится к строке отсортированных байтов.

<<< стр.3 >>>