13 531
правка
Изменения
м
Нет описания правки
* R-дерево: в узлах дерева поиска хранятся n-мерные гиперкубы и ссылки на дочерние узлы. Гиперкубы, хранящиеся в дочерних узлах, всегда принадлежат гиперкубу родительского. При переполнении страницы происходит её разделение на две части и, соответственно, два гиперкуба.
* R*-дерево: то же, что и R-дерево, но также с поддержкой индексации точечных данных, а не только гиперкубов.
* R±дерево: R-дерево без перекрытий. Смысл в том, чтобы при вставке элементов следить за перекрытием областей и своевременно разбивать их на подобласти, возможно, включая разбиение дочерних элементов. Это решает главную проблему R-подобных деревьев — без использования специальных методов при вставке элементов в дерево узлы, находящиеся на одном уровне, могут начать перекрываться, и если искомая точка содержится в области перекрытия, это сразу требует больше чтений из внешней памяти, что сильно ухудшает производительность. В <ref idname="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-дерево.
Для исправления этой ситуации предлагается использовать описанные методы индексации
многомерных данных и свободную СУБД PostgreSQL как «субъект» реализации, по причине
наличия в ней реализации GiST <ref idname="gist95">Joe Hellerstein. GiST: A Generalized Search Tree for Database Systems. A talk given at Hebrew University in Jerusalem, Tel Aviv University, UC Berkeley, Brown University, IBM Almaden Research Center. An extended version of the talk given at VLDB95.</ref> — обобщённого дерева
поиска, позволяющего легко реализовывать собственные методы индексации, не разбираясь
глубоко во внутреннем устройстве самой СУБД. Например, в процессе работы автором доклада
