R*-дерево

R*-дерево, побудоване повторюваними вставленнями (в ELKI). В цьому дереві є невеличке перекриття, яке дає в результаті добру продуктивність запитів. Червоні та сині описані прямокутники є індексними блоками, зелені описані прямокутники є листковими вузлами.

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

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

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

Дія різних евристик розщеплення на базі даних із поштовими округами Німеччини

R-дерево із квадратичним розщепленням Гуттмана.[2] Є багато блоків, які простягаються зі сходу на захід по всій Німеччині, і блоків, які сильно перекриваються. Це не корисно для більшості застосувань, що часто потребують лише невеличкої прямокутної області, яка перетинається з багатьма смугами. R-дерево із квадратичним розщепленням Гуттмана.[2] Є багато блоків, які простягаються зі сходу на захід по всій Німеччині, і блоків, які сильно перекриваються. Це не корисно для більшості застосувань, що часто потребують лише невеличкої прямокутної області, яка перетинається з багатьма смугами.  R-дерево з лінійним розщепленням Ана-Тана.[3] Хоча смуги й не простягаються настільки далеко, як в Гуттмана, проблема смуг зачіпає майже кожен листковий блок. Листкові блоки перекриваються лише трохи, але каталогові блоки перекриваються. R-дерево з лінійним розщепленням Ана-Тана.[3] Хоча смуги й не простягаються настільки далеко, як в Гуттмана, проблема смуг зачіпає майже кожен листковий блок. Листкові блоки перекриваються лише трохи, але каталогові блоки перекриваються.  Топологічне розщеплення R*-дерева.[1] Блоки перекриваються дуже мало, оскільки R*-дерево намагається мінімізувати перекриття блоків, а повторне вставлення додатково оптимізує це дерево. Також стратегія розщеплення не віддає перевагу смугам, отримувані в результаті блоки є набагато кориснішими для поширених картографічних застосувань. Топологічне розщеплення R*-дерева.[1] Блоки перекриваються дуже мало, оскільки R*-дерево намагається мінімізувати перекриття блоків, а повторне вставлення додатково оптимізує це дерево. Також стратегія розщеплення не віддає перевагу смугам, отримувані в результаті блоки є набагато кориснішими для поширених картографічних застосувань.

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

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

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

Бібліотеки, що містять R*-дерева:

• Документація rtree Boost.Geometry (C++)
• Документація пакету R*-tree ELKI (Java)
• Бібліотека просторового індексування (C++)
• Модуль R*-tree SQLite (C)
• Бібліотека TPIE (C++)