Postgres - статьи



              

Пример: R-Tree GiST для прямоугольников


Для описания сложных объектов часто используют более простые фигуры, аппроксимирующие сложную форму, которые характерны тем, что полностью содержат в себе эти объекты. Такие фигуры называют bounding volume и их гораздо проще использовать для проверки на различные условия, например, на пересечение двух объектов. В качестве bounding volume часто используют сферу, цилиндр или куб. Мы будем рассматривать куб, который называют bounding box,или BB.

R-Tree - это структура данных, которая используется для индексирования многомерных данных. Она была предложена Гуттманом [Gut84] как расширение B-tree на многомерное пространство, которое разбивается на иерархически вложенные и возможно перекрывающиеся BB (прямоугольники для двумерного случая, в случае 3-х измерений - кубики), Каждый узел R-Tree может содержать переменное количество записей, но не больше заранее определенного максимума. Каждая запись во внутренних узлах содержит ссылку на дочерний узел и BB, который содержит все записи этого дочернего узла. Каждая запись концевого узла (leaf node) содержит ссылку на данные и BB этих данных. При вставке новых данных отслеживается, чтобы близкие данные лежали "близко", в одном концевом узле, в частности, это достигается с помощью правила наименьшего увеличения BB этого узла после вставки. При поиске сравниваются BB-ы запроса и текущего узла и если нет пересечений, то последующие проверки с узлами этого поддерева уже не нужны, чем сильно уменьшается количество просмотренных узлов и достигается выигрыш в производительности.

MBR of Greece cities (fragment)

R-tree для для городов и деревень Греции. Данные взяты с rtreeportal.org

На рисунке изображен фрагмент дерева (полное дерево), построенного с помощью модуля rtree_gist и - специального модуля, предназначенного для разработчиков расширений с использованием GiST. Исходными данными являются MBR (minimum bounding rectangles) городов и деревень Греции. Изображены данные на концевых узлах (маленькие прямоугольники) и на 1-м уровне (большие прямоугольники). Подробнее можно прочитать здесь.




Содержание  Назад  Вперед