555. 다차원 인덱스 (K-d 트리)

⚠️ 이 문서는 "나이 30세 이상이면서 연봉 5천만 원 이상인 사람" 또는 "위도 x, 경도 y 좌표에서 반경 5km 이내의 식당"처럼, 두 개 이상의 속성(차원)을 동시에 만족하는 데이터를 고속으로 탐색하기 위해 공간을 재귀적으로 분할해 나가는 **다차원 데이터 인덱싱 구조인 K-d 트리(K-Dimensional Tree)**를 다룹니다.

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

  1. 본질: 1차원의 데이터(예: 나이만)를 기준으로 좌우를 나누는 이진 탐색 트리(BST)를 확장하여, K개의 차원(예: 1번 층은 나이, 2번 층은 연봉, 3번 층은 나이...)을 번갈아 가며 공간을 반으로 쪼개나가는 트리 구조다.
  2. 가치: 일반 B-Tree로 복합 인덱스(A, B)를 만들면 "A조건 없이 B조건만" 검색할 때는 인덱스를 전혀 타지 못하지만, K-d 트리는 다변량(Multi-variate) 질의와 공간(Spatial) 질의에서 압도적인 다차원 탐색 속도를 제공한다.
  3. 기술 체계: 노드를 분할할 때마다 축(Axis)이 순환하며 초평면(Hyperplane)을 그어 다차원 공간을 분리하지만, 데이터 삽입/삭제 시 트리의 균형이 쉽게 깨지는 단점이 있어 정적인 데이터 탐색에 주로 쓰이거나 R-Tree로 대체되곤 한다.

Ⅰ. B-Tree 복합 인덱스의 한계

일반적인 관계형 DB의 인덱스는 선형적인 1차원 정렬에 최적화되어 있다.

  1. 복합 인덱스 (Composite Index)의 순서 종속성:
    • CREATE INDEX idx_age_salary ON emp(age, salary);
    • 이 인덱스는 먼저 나이(age) 순으로 줄을 세운 뒤, 나이가 같을 때만 연봉(salary) 순으로 정렬한다. (전화번호부와 같음)
  2. 부분 검색의 병목:
    • WHERE age > 30 AND salary > 5000 쿼리는 인덱스를 잘 탄다.
    • 하지만 WHERE salary > 5000 쿼리는 선행 컬럼인 나이 조건이 없기 때문에, 전화번호부에서 성씨를 모른 채 이름만으로 사람을 찾는 격이 되어 결국 테이블 전체를 뒤져야(Full Scan) 한다.
  3. 다차원 인덱스의 필요성:
    • 나이(X축)와 연봉(Y축)을 평등한 2차원 평면의 좌표로 보고, 두 조건을 모두 빠르고 평등하게 잘라내며 찾을 수 있는 자료구조가 필요하다.

📢 섹션 요약 비유: 도서관 책들이 '주제별'로 꽂힌 뒤 '가나다순'으로 정렬되어 있을 때(B-Tree), 주제를 모르면 가나다순으로 책을 찾을 수 없는 한계를 극복하기 위해, 바둑판의 가로줄(주제)과 세로줄(가나다)을 동시에 십자 모양으로 잘라 들어가며 책을 찾는 방식입니다.

Ⅱ. K-d 트리 (K-Dimensional Tree)의 구조와 분할 원리

공간을 칼로 계속해서 반 토막 내는 방식이다.

  1. 축의 교대 분할 (Alternating Axes):
    • 2차원(나이, 연봉) 데이터가 있다면, 트리의 루트 노드에서는 데이터들의 '나이' 중간값(Median)을 기준으로 공간을 수직($|$)으로 나눈다.
    • 자식 노드 층에서는 분할 기준을 '연봉'으로 바꿔 공간을 수평($-$)으로 나눈다.
    • 손자 노드 층에서는 다시 '나이'로 수직($|$) 분할하는 과정을 데이터가 하나씩 방에 들어갈 때까지 반복한다.
  2. 트리 탐색 (Search)의 마법:
    • "나이 35세, 연봉 6천만 원"인 사람을 찾으려면, 1층(나이 축)에서 오른쪽으로 가고, 2층(연봉 축)에서 위쪽으로 가는 식으로 공간을 1/2씩 좁혀나간다 (이진 탐색의 $O(\log n)$ 속도 유지).
    • "나이 조건 없이 연봉 6천 이상"을 찾더라도, 연봉을 기준으로 나눈 2층의 수평선들만 검사하면서 불필요한 아래쪽 공간을 뭉텅이로 잘라내 버릴(Pruning) 수 있다.

📢 섹션 요약 비유: 피자를 자를 때 처음엔 세로로 한 번 자르고, 다음엔 각각의 조각을 가로로 자르고, 다시 세로로 자르기를 반복하여 조각을 작게 만든 뒤, 내가 원하는 조각(데이터)이 피자의 어느 사분면에 있는지 찾아 들어가는 공간 분할법입니다.

Ⅲ. K-d 트리의 트레이드오프와 최신 대안 (R-Tree)

단순하고 강력하지만 데이터가 자주 변하면 치명적인 문제가 생긴다.

  1. 동적 삽입/삭제의 불리함:
    • K-d 트리는 초기에 모든 데이터의 중간값을 정확히 계산해 공간을 십자 모양으로 균등하게 잘라놨을 때(Balanced) 최적의 성능을 낸다.
    • 나중에 편향된 데이터가 계속 추가되면 한쪽 공간에만 데이터가 몰리게 되어 트리의 깊이가 비정상적으로 깊어지고 성능이 $O(N)$으로 곤두박질친다. 이를 막으려면 트리 전체를 허물고 처음부터 다시 지어야(Rebuild) 한다.
  2. 선(Line)과 면(Area) 처리의 한계:
    • 점(Point) 데이터 검색에는 좋지만, 지도상의 '건물의 면적'이나 '도로의 선' 같은 다각형 공간 데이터를 표현하기 어렵다.
  3. 대안: R-Tree (Rectangle Tree):
    • 이 단점들을 극복하기 위해 오라클 Spatial, PostGIS 등 상용 공간 데이터베이스들은 점이 아닌 데이터를 겹치는 사각형(MBR, 최소 경계 사각형) 단위로 묶어서 동적으로 관리하는 R-Tree를 주로 사용한다.

📢 섹션 요약 비유: K-d 트리는 빈방의 가벽을 미리 십자 모양으로 예쁘게 쪼개서 사람을 한 명씩 넣는 구조라 나중에 뚱뚱한 사람이 오면 방에 넣기 힘들지만, R-Tree는 사람들이 서 있는 무리 주위에 고무줄(MBR 사각형)을 치고 그 고무줄 묶음들을 트리로 관리해 유연성이 뛰어난 현대식 방식입니다.