다차원 색인구조

다차원 색인이란

다차원 색인구조는 둘 이상의 속성을 동시에 고려하는 색인 기법이다.

공간 좌표, 시간, 특성 벡터처럼 여러 속성이 얽힌 데이터를 빠르게 찾는다.

GIS와 지도 서비스, 유사 이미지 검색에서 쓰임이 넓다.

1차원 색인의 한계

1차원 B트리는 한 속성의 순서만 보존한다.

여러 속성을 함께 묻는 질의에서는 1차원 색인을 여러 개 만들어 교집합을 구한다.

그 결과 나머지 조건은 전체를 훑어 걸러야 하므로 비용이 커진다.

구조와 MBR

다차원 색인은 데이터를 계층으로 나누고, 노드마다 MBR을 기록한다.

루트, 디렉터리, 리프 노드가 위에서 아래로 이어진다.

상위 노드의 MBR로 조건에 맞지 않는 하위 가지를 통째로 건너뛴다.

범위 검색과 가지치기

범위 검색은 질의 영역과 겹치는 노드만 따라 내려간다.

루트 MBR이 질의 영역과 겹치는지부터 검사한다.

겹치는 자식 노드만 재귀적으로 방문하고, 리프에서 최종 확인한다.

이렇게 가지치기로 검색 범위가 줄어든다.

유형 비교

다차원 색인은 데이터 성격과 질의 형태에 따라 여러 구조로 나뉜다.

R-tree 계열은 MBR이 겹칠 수 있어 탐색 경로가 여러 갈래로 늘어난다.

k-d tree와 Quadtree는 공간을 겹치지 않게 나눠 구조가 단순하다.

질의 목적에 따라 정확 검색과 근사 검색 중 선택 기준이 갈린다.

노드 접근 수 계산

백만 건 데이터를 최대 100개 엔트리 노드로 묶는 경우를 계산한다.

리프 노드 수는 N을 M으로 나눈 약 10,000개다.

트리 높이는 log 값으로 근사하면 3이다.

그러므로 점 질의 한 번에 노드 접근은 약 3개다.

정리와 고차원

다차원 색인의 핵심은 여러 속성을 동시에 묶어 공간을 나누는 것이다.

차원이 낮으면 R-tree나 k-d tree로 정확한 영역 검색을 한다.

차원이 높아지면 차원의 저주로 가지치기 효과가 줄어든다.

이때는 근사 최근접 이웃 검색과 차원 축소를 함께 쓴다.