공간 인덱스 (Spatial Index) - Quad-tree 알고리즘

핵심 인사이트 (3줄 요약)

본질: Quad-tree (쿼드 트리) 공간 인덱스는 B-Tree가 다루지 못하는 2차원(X, Y 위도/경도) 다차원 공간 데이터를 처리하기 위해, 전체 공간을 4개의 사분면(Quadrant)으로 재귀적으로 분할하며 내려가는 트리 기반 자료구조다.

가치: "내 주변 2km 이내 식당 찾기"와 같은 위치 기반 반경 검색(Radius Search)이나 공간 포함 관계 질의 시, 검색 범위에 포함되지 않는 거대한 공간(서브 트리)을 통째로 검색 대상에서 배제(Pruning)함으로써 수억 건의 좌표 데이터 중 극소수만 탐색하는 $O(\log N)$의 기적을 만든다.

융합: 데이터베이스의 공간 쿼리(Spatial Query) 최적화뿐만 아니라, 게임 엔진의 충돌 감지(Collision Detection), 컴퓨터 그래픽스의 렌더링 최적화, 이미지 압축 등 컴퓨터 과학 전반의 '공간 파티셔닝(Spatial Partitioning)' 핵심 알고리즘으로 활약한다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: Quad-tree (쿼드 트리) 알고리즘은 2차원 공간을 4개의 동일한 하위 사각형(북서, 북동, 남서, 남동)으로 쪼개고, 그 내부의 데이터 개수가 임계치 이하가 될 때까지 이 분할 과정을 재귀적으로 반복하여 공간적 계층 구조를 생성하는 인덱싱 기법이다.
필요성: 배달 앱에서 "강남역 반경 2km 이내 치킨집"을 찾는다고 가정하자. 만약 인덱스가 없다면 데이터베이스는 전국 10만 개의 치킨집 좌표를 하나씩 꺼내어 피타고라스 정리로 거리를 10만 번 계산해야 한다 (Full Table Scan). 만약 위도(Latitude)나 경도(Longitude) 단일 컬럼에 B-Tree 인덱스를 걸면 어떨까? B-Tree는 1차원 선형 데이터 정렬만 가능하므로, 위도가 비슷하더라도 경도가 완전히 반대인 데이터를 걸러낼 수 없어 사실상 무용지물이 된다. 즉, 다차원 속성이 융합된 공간의 근접성(Proximity)을 이해하려면 공간 자체를 타일처럼 나누고 묶어주는 공간 인덱스(Spatial Index) 구조가 필수 불가결하다.
등장 배경 및 동작 패러다임: 공간 데이터베이스는 점(Point), 선(Line), 다각형(Polygon)을 저장 단위를 갖는다. 이를 빠르게 검색하기 위해 두 가지 철학이 경쟁했다.
1. 데이터 중심 분할 (R-Tree): 데이터가 모여 있는 곳을 묶어서 최소 경계 사각형(MBR)을 그리는 상향식 접근.
2. 공간 중심 분할 (Quad-tree, Geohash): 데이터의 분포와 상관없이 무조건 공간 자체를 바둑판처럼 쪼개고 들어가는 하향식 접근. Quad-tree는 공간 중심 분할의 대표 주자로, 구현이 직관적이고 특히 점(Point) 데이터를 분할하거나 동적으로 빠르게 업데이트해야 하는 환경에서 압도적인 효율을 자랑하며 발전해 왔다.

이 다이어그램은 1차원 검색 방식의 한계와, Quad-tree가 어떻게 2차원 공간을 분할하여 탐색 범위를 극단적으로 줄이는지(Pruning)를 시각화한다.

  ┌───────────────────────────────────────────────────────────────┐
  │         일반 검색(거리 계산) vs Quad-tree 기반 공간 검색        │
  ├───────────────────────────────────────────────────────────────┤
  │                                                               │
  │  [A. 무식한 풀 스캔 방식 (Full Scan)]                           │
  │   DB: "내 위치 (X,Y)와 전국 치킨집 10만 개의 거리를 모두 계산하자" │
  │   연산량: 100,000회 거리 공식 계산 → CPU 병목 발생 💥             │
  │                                                               │
  │  [B. Quad-tree 공간 분할 방식]                                  │
  │   1. 전체 지도를 4등분 (Level 1)                                │
  │     ┌─────────┬─────────┐   내 검색 범위(🟢)가 포함되지 않은       │
  │     │   NW    │   NE    │   나머지 3개 사분면(NE, SW, SE)은      │
  │     │ (서울)🟢│ (강원)  │   내부 데이터가 몇 개든 아예 무시함!     │
  │     ├─────────┼─────────┤   ▶ (Pruning: 가지치기)              │
  │     │   SW    │   SE    │                                       │
  │     │ (전라)  │ (경상)  │   이제 NW 사분면 하나만 남음.          │
  │     └─────────┴─────────┘                                       │
  │                                                               │
  │   2. 남은 NW 사분면을 다시 4등분 (Level 2)                       │
  │     ┌────┬────┐                                               │
  │     │🟢  │    │   마찬가지로 겹치지 않는 공간은 버리고,              │
  │     ├────┼────┤   목표한 정밀도(예: 반경 2km 사각형)에              │
  │     │    │    │   도달할 때까지 이 과정을 재귀적으로 반복함.          │
  │     └────┴────┘                                               │
  │                                                               │
  │  ★ 결과: 10만 번 연산할 것을, 단 몇 번의 트리 탐색만으로 압축 완료!  │
  └───────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 구조도의 핵심은 **가지치기 (Pruning)**의 마법이다. 사용자가 특정 영역(원형 또는 사각형 질의)을 쿼리하면, 알고리즘은 최상위 루트 노드(전체 지도)부터 시작하여 4개의 자식 노드 사각형과 질의 영역이 교차(Intersect)하는지 기하학적 검사를 수행한다. 교차하지 않는 노드는 그 안에 수백만 개의 점이 있더라도 거리 계산을 1도 수행하지 않고 서브 트리 전체를 통째로 폐기한다. 교차하는 노드에 대해서만 더 깊은 레벨로 재귀 하강(Recursive descent)한다. 결국 리프 노드(Leaf Node) 레벨의 작은 타일 크기에 도달했을 때, 그 좁은 타일 안에 들어 있는 소수의 점 데이터(예: 10~20개)에 대해서만 실제 피타고라스 거리 계산을 수행하게 된다. 이것이 공간 인덱스가 $O(N)$ 연산을 고속의 $O(\log N)$ 트래버스 타임으로 변환시키는 물리적 메커니즘이다.

📢 섹션 요약 비유: 두꺼운 전화번호부에서 김 씨를 찾을 때 첫 장부터 다 넘겨보는 대신, 반을 쪼개고 '김'이 없는 뒤쪽 절반은 통째로 버리는 업다운 게임(이진 탐색)을 평면 지도 위에서 '4등분 접기'로 똑같이 수행하는 것과 같습니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

Quad-tree 구성 요소 및 내부 동작

Quad-tree는 메모리 내에 포인트 데이터를 4방향 자식 포인터로 연결하는 트리 구조로 구현된다.

요소명	역할	내부 논리 및 제약 조건	공간 매핑 비유
루트 노드 (Root)	전체 공간의 정의 (경계 상자)	MBR (Minimum Bounding Rectangle) 기준 좌표 소유	대한민국 전체 지도
내부 노드 (Internal Node)	공간의 분할점	4개의 자식 포인터 (NW, NE, SW, SE) 유지	도/시 단위로 자른 선
리프 노드 (Leaf Node)	실제 데이터(좌표) 저장소	최대 수용 한도 (Capacity, 예: 4개) 초과 전까지 데이터 보유	동네 골목 상권 구역
분할 (Subdivide) 알고리즘	용량 초과 시 4등분 실행	리프 노드가 꽉 차면 4개 자식 노드 생성 후 기존 데이터 재분배	너무 빽빽한 지도 확대
질의 (Query) 함수	AABB (Axis-Aligned Bounding Box) 교차 검사	쿼리 영역과 노드 사각형 교차 시 자식 노드로 탐색 이관	레이더 탐지망 스캔

노드 삽입(Insert)과 공간 분할(Partitioning)의 심층 구조

Quad-tree에 새로운 점 데이터를 계속 INSERT 할 때 어떤 일이 일어나는지 내부 트리 구조의 변화를 추적해 보자. 노드 수용 용량(Capacity)을 3으로 가정한다.

  ┌──────────────────────────────────────────────────────────────────┐
  │        Quad-tree 데이터 삽입에 따른 공간 분할 및 트리 구조 매핑      │
  ├──────────────────────────────────────────────────────────────────┤
  │                                                                  │
  │  [1. 공간 분할 상태 (Spatial View)]                              │
  │                                                                  │
  │   (0,100)           (100,100)                                    │
  │      ┌─────────┬────┬────┐     - Root 공간 (0,0 ~ 100,100)       │
  │      │         │ NW │ NE │     - 점 4개가 NE 영역에 뭉쳐서 삽입됨. │
  │      │   NW    ├────┼────┤     - Root의 용량(3) 초과! → 1차 분할.│
  │      │         │ SW │ SE │     - 우상단 NE 영역의 용량(3) 초과!  │
  │      ├─────────┼────┴────┤       → 2차 분할 발생.                │
  │      │         │         │                                       │
  │      │   SW    │   SE    │                                       │
  │      │         │         │                                       │
  │      └─────────┴─────────┘                                       │
  │   (0,0)             (100,0)                                      │
  │                                                                  │
  │  [2. 논리적 메모리 트리 구조 (Logical Tree View)]                   │
  │                                                                  │
  │                    [ Root Node ]                                 │
  │                    /  |   |  \                                   │
  │                  NW  NE  SW  SE                                  │
  │                 /    |    \    \                                 │
  │            (비었음) [Node] (비었음) (비었음)                       │
  │                    / | | \                                       │
  │                  NW NE SW SE                                     │
  │                  /  |  |  \                                      │
  │                 P1 P2 P3  P4 (점 데이터 분배 완료)                   │
  └──────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 초기 루트 노드는 전체 공간(예: 100x100 캔버스)을 담당한다. 여기에 점 데이터 P1, P2, P3이 들어오면 분할 없이 루트 노드의 리스트 배열에 담긴다. 그러나 P4가 들어와 정해진 노드 한계치(Capacity=3)를 초과하는 순간 Subdivide (분할) 연산이 발동된다. 트리 엔진은 공간을 십자(+)로 정확히 4등분하여 내부 자식 노드 4개를 메모리에 할당한다. 그런 다음 기존에 갖고 있던 P1~P4 좌표값을 다시 검사하여, 각각 어느 하위 사분면(NW/NE/SW/SE)에 속하는지 판별하고 데이터를 아래로 흘려보낸다(재분배). 만약 P1~P4가 모두 1사분면(NE)에 몰려 있었다면, NE 자식 노드 역시 생성되자마자 용량이 초과하므로 그 공간을 즉시 한 번 더 4등분하게 된다. 이처럼 데이터 밀도(Density)가 높은 도심 지역은 트리가 아주 깊게 파고들어(Deep Tree) 조밀한 그리드를 형성하고, 사막이나 바다처럼 데이터가 없는 공간은 얕은 깊이(Shallow Tree)의 큰 사각형으로 남아 메모리 공간을 극도로 절약하는 우아한 적응형(Adaptive) 구조가 완성된다.

📢 섹션 요약 비유: 우체국 택배 분류와 같습니다. 택배(데이터)가 적은 시골은 '도' 단위로 한 바구니에 담고, 택배가 쏟아지는 강남구는 '동' 단위를 넘어 '아파트 동' 단위 바구니까지 잘게 쪼개어 분류함으로써 찾는 시간을 단축하는 원리입니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

공간 인덱스 양대 산맥: Quad-tree vs R-Tree

RDBMS 공간 인덱스 엔진 구현 시 아키텍트가 직면하는 가장 큰 갈림길이다.

비교 항목	Quad-tree (공간 분할)	R-Tree (데이터 묶음)
분할 철학	Top-Down (공간을 무조건 4등분 절단)	Bottom-Up (데이터 주변으로 MBR 상자를 감쌈)
노드 겹침 유무	사분면이 명확히 잘리므로 겹침(Overlap) 없음	데이터 분포에 따라 MBR 상자끼리 겹침 발생
탐색 성능 병목	데이터 밀집 시 트리가 깊어져 순회 오버헤드 증가	MBR 겹침 구역 탐색 시 여러 노드를 동시 탐색해야 함
주 데이터 형태	점(Point) 데이터, 픽셀 맵	다각형(Polygon), 선(Line) 등 공간 범위를 갖는 객체
장단점 및 융합	구조가 단순해 Update 빠름 (게임 충돌, 실시간 로케이션)	B-Tree와 유사해 RDBMS (PostGIS, MySQL) 이식 유리

[비교 심층 해석] Quad-tree는 공간 자체를 두부 썰듯 자르기 때문에 사각형끼리 절대 겹치지 않는다. 따라서 특정 점을 검색할 때 루트에서 리프까지 단 하나의 경로(Single Path)만 존재하여 탐색 알고리즘이 명쾌하고 빠르다. 그러나 빌딩이나 호수처럼 넓은 다각형(Polygon)을 저장할 때는, 다각형이 절단선(경계선)을 가로지르는 문제가 발생해 쿼드 트리 내 여러 노드에 데이터가 중복 등록되는 치명적 파편화 이슈가 생긴다. 반면 R-Tree는 다각형 객체 하나를 감싸는 상자(MBR)를 만들기 때문에 파편화가 없지만, 강남구 상자와 서초구 상자가 겹칠 수 있다. 겹치는 영역에 쿼리를 던지면 두 상자를 모두 까봐야 하는 '다중 경로 탐색' 병목이 발생한다. 따라서 실무에서 '점 데이터(유저 위치)' 위주라면 Quad-tree 파생(Geohash 등)을, 면적 데이터(지적도, 행정구역) 위주라면 R-Tree를 선택하는 것이 아키텍처의 정석이다.

컴퓨터 그래픽스와의 융합

Frustum Culling (시야 절두체 선별): 3D 게임 엔진(Unreal, Unity)은 카메라(플레이어 시야)에 보이지 않는 수천 개의 나무와 돌멩이를 렌더링하지 않기 위해 쿼드 트리(3D 모델로는 Octree)를 사용한다. 카메라 시야 영역과 교차하지 않는 공간 노드는 렌더링 파이프라인에서 통째로 드롭(Drop)시켜 초당 60프레임(FPS)을 방어한다. 이는 DB의 쿼리 프루닝과 수학적으로 완전히 동일한 개념이다.
📢 섹션 요약 비유: 쿼드 트리는 '바둑판 선 긋기'이고 R-Tree는 '물건 크기에 맞춰 박스 포장하기'입니다. 작은 구슬(점 데이터)을 관리할 땐 바둑판이 편하지만, 긴 우산이나 넓은 방석(다각형)을 다룰 때는 박스 포장이 낫습니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오 및 의사결정

시나리오 — 배달 라이더 실시간 매칭 시스템 부하: 초당 수만 명의 라이더가 앱에 GPS 좌표를 쏘아대고(Update), 서버는 고객 반경 3km 내 라이더를 매칭해야 한다. 기존 MySQL의 R-Tree (Spatial Index)를 사용했으나, 라이더 좌표가 바뀔 때마다 트리 구조를 재조정(Split/Merge)하느라 심각한 DB Lock과 I/O 병목이 발생하여 시스템이 뻗었다.
- 의사결정: RDBMS의 무거운 R-Tree 인덱스 대신 인메모리(In-Memory) NoSQL인 Redis의 GEO 명령어를 도입한다. Redis의 Geo는 내부적으로 좌표를 Z-order Curve (Quad-tree의 공간 채움 곡선 변형인 Geohash) 알고리즘을 이용해 1차원 문자열 숫자로 매핑한 뒤 Sorted Set에 저장한다. 이를 통해 무거운 트리 갱신 연산 없이, 가벼운 1차원 숫자 범위(Range) 검색으로 반경 매칭을 1ms 내에 쳐내는 고성능 아키텍처로 전환한다.
시나리오 — 지적도(Polygon) 기반 부동산 앱 쿼리 지연: 전국 건물 폴리곤(면적) 정보 5천만 건이 담긴 PostgreSQL(PostGIS)에서, 지도 축소 뷰(전국 뷰)를 열 때마다 지도 화면 영역과 교차하는 MBR을 구하는 쿼리가 5초 이상 타임아웃이 난다.
- 의사결정: 화면이 넓어지면 Quad-tree/R-Tree의 프루닝 효과가 사라지고 전체 트리를 순회해야 하므로 발생한 한계다. 질의 범위를 제한하는 비즈니스 룰을 강제(줌 레벨 제한)하거나, 미리 격자(Grid) 단위로 집계해 놓은 요약 통계 테이블(Materialized View)을 만들어 넓은 화면에서는 원본 인덱스를 타지 않도록 쿼리 라우팅 로직을 추가해야 한다.

공간 인덱스 적용을 위한 의사결정 트리

  ┌───────────────────────────────────────────────────────────────────┐
  │           공간 인덱스(Spatial Index) 알고리즘 선택 플로우            │
  ├───────────────────────────────────────────────────────────────────┤
  │                                                                   │
  │   [처리할 지리 데이터의 주 특성 파악]                                │
  │                │                                                  │
  │                ▼                                                  │
  │      데이터의 형태가 점(Point)인가, 면적(Polygon/Line)인가?         │
  │          ├─ 면적(Polygon) ──▶ [R-Tree 계열 선택 (PostGIS 권장)]     │
  │          │                   (MBR 기반 인덱스로 분리 교차 방지)       │
  │          │                                                        │
  │          └─ 점(Point)                                             │
  │                │                                                  │
  │                ▼                                                  │
  │      좌표의 갱신(Update)이 실시간으로 매우 빈번하게 일어나는가?        │
  │          ├─ 예 (예: 택시/라이더) ──▶ [Geohash / Redis GEO 도입]     │
  │          │                          (Quad-tree 기반의 1차원 해싱)   │
  │          │                                                        │
  │          └─ 아니오 (예: 식당 위치) ──▶ [RDBMS 기본 공간 인덱스 활용]  │
  │                                                                   │
  │   판단 포인트: 트리 리밸런싱 비용(Write)과 검색 비용(Read) 간의 저울질 │
  └───────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이 의사결정 트리는 "모든 지도 서비스는 똑같다"는 착각을 경계한다. 움직이지 않는 고정된 객체(식당, 건물)는 쓰기(Insert/Update)가 거의 발생하지 않으므로, 읽기(Read) 쿼리 최적화에 강한 정통 R-Tree (RDBMS 내장) 계열을 사용하는 것이 데이터 무결성 조인에 유리하다. 그러나 배달 라이더나 모빌리티 차량처럼 좌표가 1초마다 변하는 다이나믹 포인트(Dynamic Point) 워크로드에서 무거운 디스크 기반 트리를 쓰면 B-Tree/R-Tree 특유의 노드 스플릿(Node Split) 오버헤드 때문에 시스템이 버티지 못한다. 이때는 Quad-tree의 공간 분할 특성을 1차원 문자열로 압축시킨 Geohash 인코딩(Redis 등)을 활용해 인메모리 키-값(Key-Value) 형태로 가볍게 우회 설계하는 것이 최적의 기술사적 방안이다.

안티패턴

위도/경도 컬럼의 B-Tree 독립 인덱싱: WHERE lat BETWEEN A AND B AND lng BETWEEN C AND D 쿼리를 위해 위도 컬럼과 경도 컬럼에 각각 B-Tree 인덱스를 거는 행위. DB 옵티마이저는 보통 둘 중 하나(예: 위도)의 인덱스만 타고, 나머지 경도 조건은 메모리에 퍼올린 수만 건의 데이터에 대해 무식한 필터링(Filter)을 수행하게 되어 극심한 성능 저하를 부른다. 2차원 조건은 반드시 ST_Distance 같은 공간 전용 함수와 공간 인덱스를 연동해야 한다.
📢 섹션 요약 비유: 날아다니는 파리(실시간 라이더)를 잡을 때와 가만히 있는 과녁(식당)을 맞출 때 사용하는 무기가 다르듯, 공간 데이터의 변동성에 따라 트리 기반의 정밀 인덱스를 쓸지, 가벼운 해시 격자(Geohash)를 쓸지 판단해야 합니다.

Ⅴ. 기대효과 및 결론

정량/정성 기대효과

구분	공간 인덱스 미적용 (Full Scan)	Quad-tree / R-Tree 적용	개선 효과
정량	수만 번의 좌표 거리 연산 (CPU 집약적)	공간 프루닝으로 탐색 범위를 소수로 제한	반경 쿼리 속도 수십 배 ~ 수백 배 향상
정량	I/O 버퍼 풀 대량 소진	필요한 타일 노드만 디스크 I/O 발생	DB 로드 감소, 동시 동접자 처리량 (TPS) 증가
정성	복잡한 삼각함수 연산 쿼리 하드코딩	DB 내장 공간 연산자(`ST_Within` 등) 활용	애플리케이션 코드 간소화 및 표준화

미래 전망

3차원 공간으로의 확장 (Octree): 자율주행 자동차 라이다(LiDAR) 데이터, 드론 관제, 메타버스 공간 등 고도(Z축) 개념이 포함된 포인트 클라우드(Point Cloud) 데이터를 실시간 질의하기 위해, 평면을 4등분하는 Quad-tree는 정육면체를 8등분하는 Octree (옥트리) 구조로 진화하여 3D 공간 데이터베이스의 표준으로 자리 잡고 있다.
분산 환경 공간 인덱싱 (Hadoop / Spark 연동): 수 페타바이트에 달하는 위성 기상 데이터나 통신사 기지국 트래픽 데이터를 분석하기 위해, 아파치 세도나(Apache Sedona)처럼 분산 클러스터 위에서 Quad-tree 기반의 글로벌 공간 파티셔닝을 병렬 연산하는 분산 GIS 프레임워크가 부상하고 있다.

참고 표준

OGC (Open Geospatial Consortium): 지리 정보 시스템의 공간 객체(Geometry) 모델 및 쿼리 인터페이스(Simple Feature Access) 국제 표준 규격

데이터베이스는 태생적으로 테이블이라는 1차원적인 로우(Row) 구조에 최적화되어 발전해 왔다. 하지만 우리가 살아가는 현실 세계는 다차원적인 공간이다. Quad-tree와 R-Tree 알고리즘은 이 1차원적 데이터베이스가 2차원, 3차원 현실 공간의 근접성과 포함 관계를 이해하고 소통할 수 있도록 만들어주는 훌륭한 수학적 브리지(Bridge)다. 모빌리티와 O2O 비즈니스가 모든 서비스의 근간이 되는 현대 아키텍처에서 공간 인덱스의 작동 원리를 꿰뚫는 것은 백엔드 엔지니어의 핵심 무기가 될 것이다.

📢 섹션 요약 비유: 선분(1차원) 위에 숫자들을 예쁘게 줄 세우는 것이 기존의 데이터베이스였다면, 쿼드 트리 공간 인덱스는 데이터베이스에게 십자선(+)을 그어 종이(2차원 면)를 접는 법을 가르쳐 줌으로써, 비로소 컴퓨터가 현실의 지도를 눈치채고 볼 수 있게 만든 마법의 안경입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
R-Tree (Rectangle Tree)	상향식 MBR 묶음 방식으로, Quad-tree와 대칭되는 다각형 객체(Polygon) 공간 인덱스의 업계 표준이다.
Geohash (지오해시)	2차원 공간 분할(Quad-tree 특성)을 Z-order 커브를 이용해 1차원 영문/숫자 해시 문자열로 인코딩하는 인메모리 친화적 기법이다.
PostGIS	PostgreSQL의 공간 확장 모듈로, OGC 표준을 완벽히 지원하며 R-Tree 계열 인덱스(GiST)를 통해 막강한 GIS 분석을 제공한다.
MBR (Minimum Bounding Rectangle)	다각형과 같은 복잡한 공간 객체를 감싸는 직교 형태의 최소 사각형으로, 교차 연산 1차 필터링 비용을 극단적으로 낮춘다.
Octree (옥트리)	2차원 평면을 4등분하는 Quad-tree 철학을 3차원 육면체 공간에 적용하여 8등분하는 구조로, 3D 렌더링에 필수적이다.

👶 어린이를 위한 3줄 비유 설명

넓은 바다 어딘가에 숨겨진 보물 상자를 찾아야 하는데, 다이빙을 1번만 할 수 있다고 해봐요.
쿼드 트리는 바다 지도를 십자(+)로 접어서 4칸으로 나눈 다음, 나침반이 "왼쪽 위 칸에 있어요!"라고 알려주면 나머지 3칸 바다는 거들떠보지도 않고 잘라버리는 마법 지도예요.
남은 작은 바다를 다시 4등분으로 접고 또 버리는 것을 반복하면, 단 몇 번 만에 보물 상자가 묻힌 정확한 점을 힘들이지 않고 찾아낼 수 있답니다!