X-tree

В информатике X-tree (для расширенного дерева узлов) представляет собой структуру дерева индекса, основанную на R-tree, используемом для хранения данных во многих измерениях. Он появился в 1996 году и отличается от R-деревьев (1984), R + -деревьев (1987) и R * -деревьев (1990) тем, что подчеркивает предотвращение перекрытия ограничивающих рамок, что становится все более серьезной проблемой для больших размеров. В случаях, когда узлы не могут быть разделены без предотвращения перекрытия, разделение узлов будет отложено, что приведет к суперузлам . В крайних случаях дерево будет линеаризоваться, что защищает от наихудшего поведения, наблюдаемого в некоторых других структурах данных.

X-дерево состоит из трех различных типов узлов данных, обычных узлов каталогов и надузлов. Узлы данных X-дерева содержат прямолинейные минимальные ограничивающие прямоугольники (MBR) вместе с указателями на фактические объекты данных, а узлы каталогов содержат MBR вместе с указателями на суб-MBR. Надузлы - это большие узлы каталога переменного размера (кратные размеру обычного блока). Основная цель суперузлов - избежать разделений в каталоге, которые могут привести к неэффективной структуре каталогов.

Викискладе есть материалы, относящиеся к X-деревьям.

1. ^Сельчук Кандан, К.; Луиза Сапино, Мария (31 мая 2010 г.). Издательство Кембриджского университета (ред.). Управление данными для поиска мультимедиа.
2. ^Берхтольд, Стефан; Keim, Daniel A.; Кригель, Ханс-Петер (1996). «X-дерево: структура индекса для данных большого размера». Материалы 22-й конференции VLDB. Мумбаи, Индия: 28–39.

.