R-дерево

R-tree
ТипДерево
Винайдено1984
ВинайшлиАнтонін Гуттманн
Часова складність
у записі великого О
СередняНайгірша
Простір
ПошукO(logMn)
ВставлянняO(n)
Видалення
Простий приклад R-дерева для 2D прямокутників.
Візуалізація R*-дерева для 3D пунктів, використовуючи ELKI[en] (куби — адресні сторінки).

R-дерево (англ. R-trees) — деревоподібна структура даних, яка використовується для організації доступу до просторових даних, тобто для індексації багатовимірної інформації, такої, наприклад, як географічні координати, прямокутники або многокутники. R-дерево було запропоноване в 1984 році Антоніном Гуттманном[1] і знайшло значне застосування як у теоретичному, так і у прикладному аспектах[2]. Типовим запитом з використанням R-дерев міг би бути такий: «Знайти всі музеї у радіусі 2 кілометрів від мого поточного місця розташування» або «знайти всі дороги в межах 2 кілометрів від мого поточного місця розташування» (для навігаційної системи). R-дерево також прискорює пошук найближчого сусіда[3] для різних метрик відстані, включаючи відстань по сфері.[4]

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

Алгоритми вставки і видалення використовують ці обмежуючі прямокутники для забезпечення того, щоб «близько розташовані» об'єкти були поміщені в одну листову вершину. Зокрема, новий об'єкт потрапить у ту листову вершину, для якої потрібно найменше розширення її прямокутника. Кожен елемент листової вершини зберігає два поля даних: спосіб ідентифікації даних, що описують об'єкт, (або самі ці дані) і прямокутник, який обмежує цей об'єкт.

Аналогічно, алгоритми пошуку (наприклад, перетин, включення, окіл) використовують обмежуючі прямокутники для прийняття рішення про необхідність пошуку в дочірній вершині. Таким чином, більшість вершин ніколи не використовуються при пошуку. Як і у випадку з B-деревами, ця властивість R-дерев обумовлює їх придатність для баз даних, де вершини можуть вивантажуватися на накопичувач в міру необхідності.

Для розділення переповнених вершин можуть застосовуватися різні алгоритми, що породжує поділ R-дерев на підтипи: квадратичні та лінійні.

Спочатку R-дерева не гарантували гарних характеристик для найгіршого випадку, хоча добре працювали на реальних даних. Однак, в 2004-му році був опублікований новий алгоритм, що визначає пріоритетні R-дерева. Стверджується, що цей алгоритм ефективний, як і найбільш ефективні сучасні методи, і в той же час є оптимальним для найгіршого випадку.[5]

інші мови
čeština: R-strom
Deutsch: R-Baum
English: R-tree
español: Árbol-R
français: R-arbre
עברית: עץ R
hrvatski: R-stablo
italiano: R-tree
日本語: R木
한국어: R 트리
polski: R-drzewo
português: Árvores R
српски / srpski: Р-стабло
中文: R树