R+-Tree로 포인트 질의 경로를 단일화하는 공간 인덱스
R+-Tree의 비중첩 디렉터리 구조와 리프 엔트리 중복 정책, 공간 질의 성능 및 운영 트레이드오프를 정리한다.
2026-08-14 · 최초 발행 2024-04-29
중첩된 디렉터리가 포인트 질의를 흔드는 이유
대규모 공간 데이터를 다룰 때 디렉터리 영역의 중첩은 검색 비용을 기하급수적으로 키우는 병목이 된다. R+-Tree는 이 중첩을 디렉터리 노드에서 제거한 R-Tree 변형이다. 포인트 질의가 하나의 경로만 따라가도록 만들고, 그 대가로 필요한 객체 엔트리를 리프에 중복 저장한다.
이 구조는 GIS, LBS, 게임·시뮬레이션, CAD처럼 포인트 중심 질의가 많은 환경에서 안정적인 성능을 목표로 한다.
R+-Tree의 핵심 불변식은 다음과 같다.
- 디렉터리 레벨의 노드 MBR(Minimum Bounding Rectangle)은 서로 중첩되지 않는다.
- 하나의 객체는 논리 ID 하나를 가지지만 리프에는 여러 사본(entry)이 존재할 수 있다.
- 트리 높이는 B-Tree와 유사하게 균형을 유지한다.
포인트 질의는 단일 경로로 하강하므로 평균 O(log n) I/O를 추구한다. 반면 범위·교차 질의는 여러 경로로 분기할 수 있고, 결과에서 중복을 제거하는 비용도 포함된다.
디렉터리 비중첩과 리프 복제의 교환
내부 노드의 자식 MBR은 서로 배타적인 분할 영역을 이룬다. 따라서 특정 포인트가 주어지면 하위 노드를 하나만 선택할 수 있다. R+-Tree가 포인트 질의에서 얻는 예측 가능성은 여기서 나온다.
문제는 객체 MBR이 분할 경계를 넘을 때다. 해당 객체는 교차하는 각 디렉터리 영역의 리프에 엔트리로 복제된다. 긴 선분이나 다각형처럼 여러 영역을 걸치는 데이터가 많으면 중복률이 커질 수 있으며, 결과를 돌려줄 때는 반드시 객체 ID로 중복을 제거해야 한다.
노드가 가득 차면 x, y 축 정렬 같은 기준으로 후보 분할을 평가하고, 자식 MBR의 중첩이 0이 되도록 분할을 고른다. 경계를 가로지르는 엔트리는 양쪽 자식에 배치한다. R*-Tree의 강제 재삽입과 달리 R+-Tree는 비중첩 유지에 우선순위를 둔다.
페이지 단위의 고정 용량 관리와 충분한 팬아웃은 트리 높이를 낮추는 데 쓰인다. WAL과 래치 기반 동시성 제어, 분할 전파에 따른 상향식 갱신 절차도 이 구조에 적용할 수 있다.
질의와 갱신이 트리를 통과하는 방식
포인트 질의는 루트에서 리프까지 하나의 경로만 내려간 뒤 리프를 스캔한다. 일반적으로 중복은 없지만, 후보를 반환하는 경로에서는 객체 ID 기준 중복 제거를 적용한다.
범위·교차 질의는 현재 영역과 교차하는 모든 자식을 방문한다. 리프에서 후보를 모은 뒤 객체 ID를 기준으로 중복을 제거한다.
삽입에서는 객체 MBR과 교차하는 모든 자식으로 하강한다. 리프에 엔트리를 넣은 뒤 용량을 넘기면 비중첩 분할을 실행하고, 경계 걸침 엔트리를 복제한다. 이후 상위 MBR 갱신이 전파된다.
삭제 시에는 객체 ID에 연결된 모든 리프 엔트리를 지운다. 언더플로우가 발생하면 병합 또는 재분배를 수행하면서 비중첩 불변식을 지킨다. 중복 엔트리가 계속 늘어나는 환경이라면 주기적인 재구성(repack)도 고려할 수 있다.
락 경합에는 백오프 후 재시도 전략을 적용한다. 중복 결과는 좌표나 MBR 비교가 아니라 객체 ID 기준으로 제거해야 한다. 분할 도중 충돌이 나면 트랜잭션 로그를 기반으로 재시도한다.
R-Tree 계열에서 보는 선택 기준
| 지표 | R-Tree | R*-Tree | R+-Tree |
|---|---|---|---|
| 성능(포인트) | 중첩으로 다중 경로 탐색, 불안정 | 중첩 최소화로 평균 개선 | 단일 경로 보장, 일관된 저지연 |
| 성능(범위/교차) | 보통, 중첩에 민감 | 우수, 실무 기본 선택 | 보통~우수, 중복 제거 비용 존재 |
| 확장성(저장 효율) | 높음(중복 없음) | 높음 | 중간(엔트리 중복으로 10~60% 추가 공간) |
| 일관성(경로 결정성) | 낮음 | 중간 | 높음(디렉터리 비중첩) |
| 안정성(업데이트 비용) | 낮음 | 중간(강제 재삽입 비용) | 중간~높음(복제·분할 비용) |
| 운영 편의(튜닝) | 쉬움 | 보통(파라미터 조정 필요) | 보통(중복률/분할 축 선택 중요) |
수치는 데이터 분포, 페이지 크기, 팬아웃, 디스크/SSD 환경에 따라 달라진다. 최신 환경 기준의 벤치마크는 다시 확인할 필요가 있다.
포인트 중심 워크로드에서의 활용
LBS 포인트 조회
사용자 위치의 위도·경도와 반경 r을 입력으로 받아 포인트 질의로 단일 경로를 하강한다. 리프를 스캔한 뒤 반경 필터와 ID 중복 제거를 거쳐 인접 POI 목록을 반환한다. 모바일 서버에서 낮은 CPU/I/O로 일관된 응답을 확보하는 흐름이다.
게임과 시뮬레이션의 충돌 후보 탐색
이동체 포인트 또는 작은 구체와 영역 장애물 MBR 집합을 대상으로 포인트·소범위 질의를 반복 실행한다. 업데이트 빈도가 높은 데이터는 배치 삽입으로 처리할 수 있다. 반환된 충돌 후보 세트는 프레임 타임 안정화에 기여한다.
CAD 편집기의 선택 연산
커서 포인트나 선택 박스를 입력으로 사용해 포인트 질의 또는 작은 범위 질의를 수행한다. 결과 ID 집합은 중복 제거가 필수다. 이렇게 얻은 선택 객체 목록은 인터랙티브 작업에서 지연 변동을 줄이는 데 쓰인다.
성능 기대치와 운영상 대가
R-Tree와 비교할 때 포인트 질의 지연은 1.32.5배 개선될 수 있으며, 데이터 분포의 편향이 적을수록 향상된다. 평균 단일 경로를 따르면서 페이지 터치 수는 3060% 줄어들 수 있다. 반대로 엔트리 중복률은 10~60% 증가할 수 있고, 긴 폴리라인·폴리곤 데이터에서는 더 높아진다.
중첩을 없애면 최악과 최선 사이의 성능 편차가 줄어든다. 경로 수가 하나로 정해지므로 캐시와 버퍼 관리의 예측 가능성도 높아진다. 다만 최신 하드웨어, 파일시스템, 버퍼 매니저 조합에 따라 체감 효과가 다르므로 도입 전 벤치마크가 필요하다.
분할 정책과 복구 절차에서 확인할 점
분할 축과 전략은 자식 MBR의 중첩을 0으로 만드는 데 우선순위를 두고, 면적 균형은 보조 기준으로 둔다. 비중첩을 강하게 요구할수록 엔트리 복제는 늘어나며 저장과 업데이트 비용도 커진다.
결과 중복 제거에는 객체 ID가 필요하다. 리프에 역참조 테이블(객체ID→유니크 키)을 두는 방안도 검토할 수 있다. 비정규형 다각형은 세그먼트화 같은 프리프로세싱으로 중복률을 완화할 수 있다.
동시성 제어에는 래치 커플링(상위 S→하위 S, 분할 시 대상 노드 X로 승격)을 적용한다. WAL은 페이지 이미지, 분할 메타, 상위 포인터 갱신 순서로 기록한다.
페이지 크기는 4~16KB 범위에서 객체 MBR 평균 크기를 고려하며 팬아웃을 극대화한다. 핫스팟 범위 질의가 많다면 R*-Tree 대비 우위가 약해질 수 있다. 포인트·근접 질의 비중이 높고 업데이트 빈도가 보통이라면 R+-Tree를 검토할 수 있으며, 범위 질의와 복잡 폴리곤이 중심이고 저장 효율을 우선한다면 R*-Tree를 먼저 살펴볼 수 있다.