13 531
правка
Изменения
м
→Обзор методов
* R-дерево: в узлах дерева поиска хранятся n-мерные гиперкубы и ссылки на дочерние узлы. Гиперкубы, хранящиеся в дочерних узлах, всегда принадлежат гиперкубу родительского. При переполнении страницы происходит её разделение на две части и, соответственно, два гиперкуба.
* R*-дерево: то же, что и R-дерево, но также с поддержкой индексации точечных данных, а не только гиперкубов.
* R±деревоR<nowiki>+</nowiki>-дерево: R-дерево без перекрытий. Смысл в том, чтобы при вставке элементов следить за перекрытием областей и своевременно разбивать их на подобласти, возможно, включая разбиение дочерних элементов. Это решает главную проблему R-подобных деревьев — без использования специальных методов при вставке элементов в дерево узлы, находящиеся на одном уровне, могут начать перекрываться, и если искомая точка содержится в области перекрытия, это сразу требует больше чтений из внешней памяти, что сильно ухудшает производительность. В <ref name="p028_xtree">Stefan Berchtold, Daniel A. Keim, Hans-Peter Kriegel. The X-tree: An Index Structure for High-Dimensional Data. In VLDB’1996, p.28-39.</ref> авторы показали, что степень перекрытия стремится к 90\% уже при увеличении размерности до 10.
* X-дерево: уход от древовидной структуры R-дерева при большом проценте перекрытия. X-дерево — адаптивная структура, в которой кроме «древовидных» узлов также существуют «списочные», содержащие просто длинный список элементов, не разбитый на области.
* M-дерево: попытка построения аналога R-дерева для шаровидных окрестностей элементов, и попытка его обобщения на случай любой метрики. От проблемы перекрытия страдает точно так же, и возможно, даже больше, чем обычное R-дерево.