Дерева R: Структура даних, яка робить швидкими запити карти

Що таке R-дерево?

R-дерево — це структура даних у вигляді дерева, розроблена для індексування просторових даних, таких як точки, прямокутники, дороги або плани будівель, щоб їх можна було ефективно шукати за розташуванням. Воно є узагальненням ідеї B-дерева, де кожен внутрішній вузол групує діапазон відсортованих ключів у два або більше вимірів, де кожен внутрішній вузол групує область простору. Кожен об'єкт, що зберігається в R-дереві, будь то окрема точка або складний багатокутник, спочатку оцінюється за допомогою його мінімального контуру обмеження (МКО), найменшого орієнтованого на осі прямокутника, який повністю містить його. Листяні вузли дерева містять ці рамки для фактичних об'єктів. Кожен вузол над листям групує невелику кількість дочірніх рамок і зберігає один більший контейнер, що охоплює всі їх, піднімаючись високо в дереві, ви досягаєте кореневого вузла, який має єдиний прямокутник, що охоплює весь набір даних. Це вкладення означає, що невелике число великих прямокутників поблизу кореня може представляти мільйони невеликих об'єктів біля листя, даючи структурі компактну логарифмічну висоту, подібну до B-дерева, але організовану за просторовою близькістю замість відсоркованого порядку.

Чому запити про діапазон стають швидкими

Виграш цієї вкладеної структури проявляється, коли ви запускаєте просторове запит про діапазон, наприклад, знайти всі ресторани в цьому прямокутнику на карті. Замість перевірки кожного ресторану в наборі даних, пошук починається з кореня і задає простий запитання на кожному вузлі: чи перетинається обмежувальний прямокутник цього дитини із зоною запиту? Якщо обмежувальний прямогульник дитини не перетинає прямокутник запиту, алгоритм з певною мірою впевненості знає, що нічого всередині нього не може відповідати, тому він пропускає весь цей гілку без перевірки об'єктів, що містяться всередині. Тільки гілки, чий обмежувальний прямокутник перетинається з зоною запиту, спускаються в глибину, і процес повторюється рекурсивно на кожному рівні до тих пір, поки пошук не досягне листових вузлів, що містять фактичні об'єкти. Оскільки кожен пропущена гілка може представляти тисячі або мільйони підлеглих об'єктів, один невдалий перевірка накладання на високому рівні дерева може усунути величезну кількість об'єктів із набору даних за один крок. Це дозволяє R-дереву відповідати запитам «що поруч зі мною» або «що знаходиться в цьому районі» проти великих географічних наборів даних за мілісекунди, а не сканувати все лінійно.

Вставка та виклик розділення

Будівництво дерева R складніше, ніж дерево B, оскільки немає природного порядку сортування для двовимірних даних. Під час вставки нового об’єкта алгоритм повинен вибрати, в який піддерево його розмістити, і стандартним евристичним є вибір дитини, яка б потребувала найменшого збільшення прямокутника обмеження, щоб включити новий об’єкт, вирішуючи перешкоди шляхом вибору меншої отриманої площі. Це допомагає підтримувати прямокутники обмеження щільними та групувати близькі просторово об’єкти разом. Кожен вузол має максимальну ємність, і коли запис перевищує цей ліміт, вузол повинен бути розділений на два нових вузли. Ключовим викликом є рішення про те, як розподілити записи між двома новими прямокутниками обмеження так, щоб вони якомога менше перекривалися і кожен залишався таким маленьким і щільним, як це можливо. Погане розділення призводить до того, що прямокутники обмеження розповсюджуються та сильно перекриваються, що змушує майбутні запити займатися багатою кількістю гілок непотрібно та зменшує силу видалення, яка робить всю структуру швидкою. Різні стратегії розділення, від простих квадратичних евристик до більш вичерпних лінійних або R*-дерев, всі прагнуть до однієї мети: мінімізувати перекриття та невикористану площу після розділення.

Основна відмінність від B-дерева

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

Використання в реальних проектах

R-дерева та їхні варіанти є основою практичного просторового індексування в галузі програмного забезпечення. PostGIS, простірний розширення для PostgreSQL, використовує R-дерев'яний індекс (GiST, звичайне дерево пошуку, з логікою рамки у стилі R-tree) для прискорення запитів, таких як знаходження всіх ділянок всередині межі або всіх датчиків у радіусі. Інші географічні бази даних та двигуни ГІС, від Oracle Spatial до SQLite SpatiaLite та геопросторових індексів MongoDB, покладаються на ту ж основну ідею. Картографічні додатки використовують R-дерева для швидкого визначення, які плитки карти, точки інтересу або сегменти доріг потрапляють у поле зору користувача під час масштабування та переміщення. Простірні ігри та симуляції використовують їх для виявлення зіткнень та запитів на близькість, ефективно знаходячи, які об'єкти розташовані поблизу заданого персонажа або регіону без перевірки кожного об'єкта у світі. Більш широко будь-яка система, яка повинна відповідати на питання: що є поруч зі мною, що знаходиться в цьому районі чи які об'єкти перетинаються з цією формою, серед великої кількості просторових даних, отримує користь від R-дерева, роблячи його одним із тихих вертихників, що лежать в основі сучасної технології визначення місцезнаходження.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте R-Trees: The Data Structure That Makes Map Queries Fast і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.