Реализация
В этом разделе рассматриваются детали реализации и другие приемы, которые полезно знать разработчикам классов операторов SP-GiST.
Ограничения SP-GiST
Отдельные кортежи листьев и внутренние кортежи должны умещаться на одной индексной странице (по умолчанию 8 кБ). Поэтому при индексировании значений типов данных переменной длины длинные значения могут поддерживаться только такими методами, как радиксные деревья, в которых каждый уровень дерева включает префикс, достаточно короткий, чтобы уместиться на странице, а последний уровень листа включает суффикс, также достаточно короткий, чтобы уместиться на странице. Класс оператора должен установить longValuesOK в true только в том случае, если он готов организовать это. В противном случае ядро SP-GiST отклонит любой запрос на индексирование значения, которое слишком велико, чтобы поместиться на странице индекса.
Аналогично, класс оператора отвечает за то, чтобы внутренние кортежи не становились слишком большими, чтобы поместиться на индексной странице; это ограничивает количество дочерних узлов, которые могут быть использованы в одном внутреннем кортеже, а также максимальный размер значения префикса.
Еще одно ограничение заключается в том, что когда узел внутреннего кортежа указывает на набор листовых кортежей, все эти кортежи должны находиться в одной индексной странице. (Это дизайнерское решение, позволяющее сократить поиск и сэкономить место в связях, которые соединяют такие кортежи вместе). Если набор листовых кортежей становится слишком большим для страницы, выполняется разбиение и вставляется промежуточный внутренний кортеж. Чтобы это помогло решить проблему, новый внутренний кортеж должен разделить набор значений листа более чем на одну группу узлов. Если функция picksplit класса оператора не справляется с этой задачей, ядро SP-GiST прибегает к чрезвычайным мерам, описанным в разделе «Лимиты SP-GiST».
Когда longValuesOK равен true, ожидается, что последующие уровни дерева SP-GiST будут поглощать все больше и больше информации в префиксах и метках узлов внутренних кортежей, делая требуемые данные листа все меньше и меньше, так что в конце концов они поместятся на странице. Чтобы не вызывать бесконечных циклов вставки, ядро SP-GiST выдаст ошибку, если в течение десяти циклов после вызова метода choose значение leaf datum не станет меньше.
SP-GiST без меток узлов
Некоторые алгоритмы построения деревьев используют фиксированный набор узлов для каждого внутреннего кортежа; например, в четырехмерном дереве всегда есть ровно четыре узла, соответствующие четырем квадрантам вокруг центральной точки внутреннего кортежа. В этом случае код обычно работает с узлами по номерам, и нет необходимости в явных метках узлов. Чтобы отказаться от меток узлов (и тем самым сэкономить место), функция picksplit может вернуть NULL для массива nodeLabels, а функция choose - NULL для массива prefixNodeLabels во время действия spgSplitTuple. Это, в свою очередь, приведет к тому, что nodeLabels будет NULL при последующих вызовах choose и inner_consistent. В принципе, метки узлов можно использовать для одних внутренних кортежей и не использовать для других в том же индексе.
При работе с внутренним кортежем с неразмеченными узлами ошибка заключается в том, что choose возвращает spgAddNode, поскольку в таких случаях набор узлов должен быть фиксированным.
Лимиты SP-GiST
Ядро SP-GiST может переопределять результаты функции picksplit класса operator, когда picksplit не удается разделить предоставленные значения листьев хотя бы на две категории узлов. В этом случае создается новый внутренний кортеж с несколькими узлами, каждый из которых имеет ту же метку (если таковая имеется), которую picksplit присвоил единственному узлу, который он использовал, и значения листьев распределяются случайным образом между этими эквивалентными узлами. Флаг allTheSame устанавливается на внутреннем кортеже, чтобы предупредить функции choose и inner_consistent о том, что кортеж не имеет того набора узлов, который они могли бы ожидать.
При работе с кортежем allTheSame результат choose spgMatchNode интерпретируется как то, что новое значение может быть присвоено любому из эквивалентных узлов; основной код будет игнорировать предоставленное значение nodeN и спускаться в один из узлов случайным образом (чтобы сохранить дерево сбалансированным). Ошибкой является возврат spgAddNode, поскольку в этом случае узлы не будут эквивалентными; если вставляемое значение не соответствует существующим узлам, следует использовать действие spgSplitTuple.
При работе с кортежем allTheSame функция inner_consistent должна возвращать либо все узлы, либо ни один из них в качестве цели для продолжения поиска по индексу, поскольку все они эквивалентны. Это может потребовать или не потребовать какого-либо специального кода, в зависимости от того, насколько функция inner_consistent обычно предполагает значение узлов.