Перегляд вихідного коду сторінки R*-дерево

{{DISPLAYTITLE:''R''*-дерево}}
'''''R''*-дере́ва''' ({{lang-en|R*-trees}})&nbsp;— один з варіантів [[R-дерево|''R''-дерев]], що застосовується для [[індексування]] [[Просторова база даних|просторової інформації]]. ''R''*-дерева мають дещо вищу конструктивну витратність, ніж стандартні ''R''-дерева, оскільки дані можуть потребувати повторного вставляння; але отримуване в результаті дерево зазвичай матиме кращу продуктивність запитів. Як і стандартне ''R''-дерево, воно може зберігати як точкові, так і просторові дані. Його було запропоновано Норбертом Бекманом, {{нп|Ганс-Петер Крігель|Гансом-Петером Крігелем||Hans-Peter Kriegel}}, Ральфом Шнайдером та Бернардом Сіґером 1990 року.<ref name="rstar">{{Cite book | last1 = Beckmann | first1 = N. | last2 = Kriegel | first2 = H. P. | authorlink2 = Ганс-Петер Крігель | last3 = Schneider | first3 = R. | last4 = Seeger | first4 = B. | chapter = The R*-tree: an efficient and robust access method for points and rectangles | doi = 10.1145/93597.98741 | title = Proceedings of the 1990 ACM SIGMOD international conference on Management of data  - SIGMOD '90 | pages = 322 | year = 1990 | isbn = 0897913655 | pmid =  | pmc =  | url = http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf | accessdate = 19 березня 2016 | archive-date = 17 квітня 2018 | archive-url = https://web.archive.org/web/20180417071129/http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf }} {{Webarchive|url=https://web.archive.org/web/20180417071129/http://dbs.mathematik.uni-marburg.de/publications/myPapers/1990/BKSS90.pdf |date= 17 квітня 2018 }} {{ref-en}}</ref>

== Різниця між ''R''*-деревами та ''R''-деревами ==
[[Файл:RTree 2D.svg|thumb|350px|''R''*-дерево, побудоване повторюваними вставленнями (в {{нп|ELKI}}). В цьому дереві є невеличке перекриття, яке дає в результаті добру продуктивність запитів. Червоні та сині описані прямокутники є індексними блоками, зелені описані прямокутники є листковими вузлами.]]

Для продуктивності ''R''-дерев вирішальне значення має мінімізація як покриття, так і перекриття. Перекриття означає, що при запиті або вставлянні даних розкриття потребує більш ніж одна гілка дерева (через те, що дані розщеплюються на області, які перекриваються). Мінімізоване покриття покращує продуктивність обрізання, дозволяючи частіше виключати з пошуку цілі блоки, зокрема для заперечних запитів за областями. ''R''*-дерево намагається зменшувати і те, і те, застосовуючи поєднання переглянутого алгоритму розщеплення вузлів, та поняття примусового повторного вставляння при переповненні вузлів. Це ґрунтується на тому спостереженні, що структури ''R''-дерев є дуже чутливими до порядку, в якому вставляються їхні записи, так що структура, побудована вставлянням (а не одночасним завантаженням) є ймовірно не зовсім оптимальною. Вилучення та повторне вставлення записів дозволяє їм «знаходити» місце в дереві, що може бути більш підхожим, ніж їхнє первинне місце.

При переповненні вузла частина записів вилучається з нього, і вставляється до дерева повторно. (Для того, щоби уникнути невизначеного каскаду повторних вставлень, спричиненого наступним переповненням вузла, процедура повторного вставлення може викликатися лише по одному разу на кожному рівні дерева при вставленні будь-якого одного нового запису.) Це дає ефект вироблення краще кластеризованих груп записів у вузлах, що зменшує покриття вузлів. Крім того, фактичні розщеплення вузлів часто відкладаються, в результаті чого середня заповненість вузла зростає. Повторне вставлення можна розглядати як метод поступової оптимізації дерева, що спрацьовує при переповненні вузла.

== Продуктивність ==

* Покращена евристика розщеплення виробляє блоки, що є ближчими до квадратних, і відтак кращими для багатьох застосувань.
* Метод повторного вставляння оптимізує наявне дерево, але підвищує складність.
* Дієво підтримує як точкові, так і просторові дані одночасно.
{{clear}}

{{Gallery
|title=Дія різних евристик розщеплення на базі даних із поштовими округами Німеччини
|width=300 | height=300 | align=center | lines=8
|File:Zipcodes-Germany-GuttmanRTree.svg|''R''-дерево із квадратичним розщепленням Гуттмана.<ref name="guttman">{{Cite book | last1 = Guttman | first1 = A. | chapter = R-Trees: A Dynamic Index Structure for Spatial Searching | doi = 10.1145/602259.602266 | title = Proceedings of the 1984 ACM SIGMOD international conference on Management of data  - SIGMOD '84 | pages = 47 | year = 1984 | isbn = 0897911288 | pmid =  | pmc =  | url = http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf | accessdate = 19 березня 2016 | archive-date = 9 березня 2016 | archive-url = https://web.archive.org/web/20160309184553/http://www-db.deis.unibo.it/courses/SI-LS/papers/Gut84.pdf }} {{ref-en}}</ref><br/>Є багато блоків, які простягаються зі сходу на захід по всій Німеччині, і блоків, які сильно перекриваються. Це не корисно для більшості застосувань, що часто потребують лише невеличкої прямокутної області, яка перетинається з багатьма смугами.
|File: Zipcodes-Germany-AngTanSplit.svg|''R''-дерево з лінійним розщепленням Ана-Тана.<ref name="ang-tan">{{cite conference | last1= Ang | first1 = C. H. | last2 = Tan | first2 = T. C. | editor1-first = Michel | editor1-last = Scholl | editor2-first = Agnès | editor2-last = Voisard | year = 1997 | title = New linear node splitting algorithm for R-trees | booktitle = Proceedings of the 5th International Symposium on Advances in Spatial Databases (SSD '97), Berlin, Germany, July 15–18, 1997 | volume = 1262 |series=Lecture Notes in Computer Science | publisher=Springer | pages = 337–349 | doi = 10.1007/3-540-63238-7_38}} {{ref-en}}</ref><br/> Хоча смуги й не простягаються настільки далеко, як в Гуттмана, проблема смуг зачіпає майже кожен листковий блок. Листкові блоки перекриваються лише трохи, але каталогові блоки перекриваються.
|File: Zipcodes-Germany-RStarTree.svg|Топологічне розщеплення '''''R''*-дерева'''.<ref name="rstar" /><br/> Блоки перекриваються дуже мало, оскільки ''R''*-дерево намагається мінімізувати перекриття блоків, а повторне вставлення додатково оптимізує це дерево. Також стратегія розщеплення не віддає перевагу смугам, отримувані в результаті блоки є набагато кориснішими для поширених картографічних застосувань.
}}

== Алгоритм та складність ==

* Для операцій здійснення запитів та вилучення ''R''*-дерево використовує той же самий алгоритм, що й звичайне [[R-дерево|''R''-дерево]].
* При вставлянні ''R''*-дерево застосовує комбіновану стратегію. Для листкових вузлів мінімізується перекриття, тоді як для внутрішніх вузлів мінімізуються поширення та площа.
* При розщепленні ''R''*-дерево застосовує топологічне розщеплення, яке обирає вісь розщеплення на основі периметру, а потім мінімізує перекриття.
* На додачу до вдосконаленої стратегії розщеплення, ''R''*-дерево також намагається уникати розщеплень, повторно вставляючи об'єкти та піддерева до дерева, під натхненням ідеї балансування [[Б-дерево|''B''-дерева]].

Таким чином, складність запиту та вилучення у найгіршому випадку є ідентичними до ''R''-дерева. Стратегія вставляння до ''R''*-дерева з <math>\mathcal{O}(M \log M)</math> є складнішою за стратегію лінійного розщеплення (<math>\mathcal{O}(M)</math>) ''R''-дерева, але менш складною, ніж стратегія квадратичного розщеплення (<math>\mathcal{O}(M^2)</math>) для розміру блока в <math>M</math> об'єктів, і має незначний вплив на загальну складність. Загальна складність вставляння залишається порівня́нною з ''R''-деревом: повторне вставлення зачіпає щонайбільше одну з гілок дерева, і відтак <math>\mathcal{O}(\log n)</math> повторних вставлень, порівня́нно до виконання розщеплення на звичайному ''R''-дереві. Отже, в цілому складність ''R''*-дерева є такою ж, як і в звичайного ''R''-дерева.

Реалізація повного алгоритму мусить враховувати багато межових випадків та вузьких ситуацій, не обговорених тут.

== Примітки ==

{{Примітки}}

== Посилання ==
{{commons category}}

Бібліотеки, що містять ''R''*-дерева:
* [http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/reference/spatial_indexes/boost__geometry_%5Findex__rtree.html Документація rtree Boost.Geometry] (C++)
* [http://elki.dbs.ifi.lmu.de/releases/release0.6.0/doc/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-summary.html Документація пакету R*-tree ELKI] {{Webarchive|url=https://web.archive.org/web/20140419200910/http://elki.dbs.ifi.lmu.de/releases/release0.6.0/doc/de/lmu/ifi/dbs/elki/index/tree/spatial/rstarvariants/rstar/package-summary.html |date=19 квітня 2014 }} (Java)
* [http://libspatialindex.github.io/ Бібліотека просторового індексування] {{Webarchive|url=https://web.archive.org/web/20140814231603/http://libspatialindex.github.io/ |date=14 серпня 2014 }} (C++)
* [http://sqlite.org/rtree.html Модуль R*-tree SQLite] {{Webarchive|url=https://web.archive.org/web/20140725112444/http://sqlite.org/rtree.html |date=25 липня 2014 }} (C)
* [http://www.madalgo.au.dk/tpie Бібліотека TPIE] {{Webarchive|url=https://web.archive.org/web/20141012221408/http://www.madalgo.au.dk/tpie |date=12 жовтня 2014 }} (C++)

{{Дерева (інформатика)}}

[[Категорія:Дерева (структури даних)]]
[[Категорія:Підходи до індексування баз даних]]
[[Категорія:1990 у науці]]