Loading AI tools
З Вікіпедії, вільної енциклопедії
R*-дере́ва (англ. R*-trees) — один з варіантів R-дерев, що застосовується для індексування просторової інформації. R*-дерева мають дещо вищу конструктивну витратність, ніж стандартні R-дерева, оскільки дані можуть потребувати повторного вставляння; але отримуване в результаті дерево зазвичай матиме кращу продуктивність запитів. Як і стандартне R-дерево, воно може зберігати як точкові, так і просторові дані. Його було запропоновано Норбертом Бекманом, Гансом-Петером Крігелем[en], Ральфом Шнайдером та Бернардом Сіґером 1990 року.[1]
Для продуктивності R-дерев вирішальне значення має мінімізація як покриття, так і перекриття. Перекриття означає, що при запиті або вставлянні даних розкриття потребує більш ніж одна гілка дерева (через те, що дані розщеплюються на області, які перекриваються). Мінімізоване покриття покращує продуктивність обрізання, дозволяючи частіше виключати з пошуку цілі блоки, зокрема для заперечних запитів за областями. R*-дерево намагається зменшувати і те, і те, застосовуючи поєднання переглянутого алгоритму розщеплення вузлів, та поняття примусового повторного вставляння при переповненні вузлів. Це ґрунтується на тому спостереженні, що структури R-дерев є дуже чутливими до порядку, в якому вставляються їхні записи, так що структура, побудована вставлянням (а не одночасним завантаженням) є ймовірно не зовсім оптимальною. Вилучення та повторне вставлення записів дозволяє їм «знаходити» місце в дереві, що може бути більш підхожим, ніж їхнє первинне місце.
При переповненні вузла частина записів вилучається з нього, і вставляється до дерева повторно. (Для того, щоби уникнути невизначеного каскаду повторних вставлень, спричиненого наступним переповненням вузла, процедура повторного вставлення може викликатися лише по одному разу на кожному рівні дерева при вставленні будь-якого одного нового запису.) Це дає ефект вироблення краще кластеризованих груп записів у вузлах, що зменшує покриття вузлів. Крім того, фактичні розщеплення вузлів часто відкладаються, в результаті чого середня заповненість вузла зростає. Повторне вставлення можна розглядати як метод поступової оптимізації дерева, що спрацьовує при переповненні вузла.
Дія різних евристик розщеплення на базі даних із поштовими округами Німеччини | ||||||
---|---|---|---|---|---|---|
|
Таким чином, складність запиту та вилучення у найгіршому випадку є ідентичними до R-дерева. Стратегія вставляння до R*-дерева з є складнішою за стратегію лінійного розщеплення () R-дерева, але менш складною, ніж стратегія квадратичного розщеплення () для розміру блока в об'єктів, і має незначний вплив на загальну складність. Загальна складність вставляння залишається порівня́нною з R-деревом: повторне вставлення зачіпає щонайбільше одну з гілок дерева, і відтак повторних вставлень, порівня́нно до виконання розщеплення на звичайному R-дереві. Отже, в цілому складність R*-дерева є такою ж, як і в звичайного R-дерева.
Реалізація повного алгоритму мусить враховувати багато межових випадків та вузьких ситуацій, не обговорених тут.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.