Разделение на страницы
Описанная в предыдущем разделе структура удобна для хранения и поиска строковых ключей в оперативной памяти. Но для использования её с большими объёмами данных во внешней памяти необходимо эффективно распределять её на страницы фиксированной длины. Заметим, что это важно не только для структур данных, предназначенных непосредственно для хранения во внешней памяти (например для поддержания индексов баз данных), но также для структур данных в оперативной памяти .
Для такого разделения выделим особый тип ссылочных вершин, которые не хранят префиксов и ссылок на другие вершины, а хранят лишь ссылку на другой узел, находящийся в другой странице. Такие вершины пометим флагом external(x); каждая из таких вершин ссылается на некоторую вершину y=J(x) такую, что external(x)⇒not external(J(x)). Введём также понятие ветки. Назовём веткой корневое дерево B такое, что конечные вершины всех путей от корня к листовым вершинам в нём помечены либо final(x), либо external(x). Если в дереве T нет ссылочных вершин, то оно состоит из одной ветки.
Заметим, что любое дерево T может произвольным образом быть разбито на ветки путём вставки перед любой вершиной новой ссылочной вершины. Ссылочная вершина разбивает ветку на две. Если ветки считать узлами, то они также образуют дерево Tb. Отметим также, что ссылочные вершины никак не влияют на минимальность дерева по определению и не являются избыточными.
Страницы могут хранить одинаковый объём данных W байт. В странице могут храниться одна или несколько веток исходного дерева, причём в одной странице могут хранится только ветки с общим прямым предком P(B). Последнее условие необходимо, во-первых, для обеспечения локальности изменений в дереве , а, во-вторых, для обеспечения эффективных блокировок на уровне страниц. Из этого также следует, что на странице, в которой хранится корневая ветка, других веток быть не может.
