X-дерево
| X-дерево | ||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Тип | Дерево | |||||||||||
| Изобретенный | 1996 | |||||||||||
| ||||||||||||
информатики В древовидных структурах данных ( X-дерево для расширенного дерева узлов) [1] ) — это индексная древовидная структура, основанная на R-дереве , используемом для хранения данных во многих измерениях. Он появился в 1996 году, [2] и отличается от R-деревьев (1984), R+-деревьев (1987) и R*-деревьев (1990), поскольку в нем делается упор на предотвращение перекрытия ограничивающих рамок, что все больше становится проблемой в больших размерностях. В тех случаях, когда узлы не могут быть разделены без предотвращения перекрытия, разделение узлов будет отложено, что приведет к образованию суперузлов . В крайних случаях дерево будет линеаризовано, что защищает от наихудшего поведения, наблюдаемого в некоторых других структурах данных.
Структура [ править ]
X-дерево состоит из узлов трех разных типов: узлов данных, обычных узлов каталогов и суперузлов. Узлы данных X-дерева содержат прямолинейные минимальные ограничивающие прямоугольники (MBR) вместе с указателями на фактические объекты данных, а узлы каталогов содержат MBR вместе с указателями на суб-MBR. Суперузлы — это большие узлы каталогов переменного размера (кратного обычного размера блока). Основная цель суперузлов — избежать разделения каталога, которое могло бы привести к неэффективной структуре каталогов.
Ссылки [ править ]
- ^ Сельчук Кандан, К.; Луиза Сапино, Мария (31 мая 2010 г.). Издательство Кембриджского университета (ред.). Управление данными для поиска мультимедиа . ISBN 9781139489584 .
- ^ Берхтольд, Стефан; Кейм, Дэниел А.; Кригель, Ханс-Петер (1996). «X-дерево: структура индекса для многомерных данных» . Материалы 22-й конференции ВЛДБ . Мумбаи, Индия: 28–39.
 | Эта алгоритмам или структурам данных, статья, посвященная является незавершенной . Вы можете помочь Википедии, расширив ее . |