🟣 왜 한 축으로는 부족한가
앞 장까지의 트리는 전부 하나의 전제를 공유한다. 키가 한 축으로 정렬된다는 것이다. 학번이든 날짜든 금액이든, 크기를 비교할 수 있는 값 하나로 왼쪽·오른쪽을 가른다. 그런데 현실의 데이터에는 축이 여럿인 경우가 많다. 지도 위의 좌표는 위도와 경도 두 축을 함께 가지고, 이미지 특징 벡터는 수백 축을 가진다.
"위도가 이 범위이면서 동시에 경도가 저 범위인 지점"을 찾는다고 해 보자. B+트리 인덱스는 한 축으로만 정렬돼 있다. 위도로 인덱스를 걸면 위도 범위는 리프 연결로 빠르게 훑지만, 그중 경도 조건은 하나하나 다시 걸러야 한다. 두 축을 이어 붙인 복합 인덱스를 만들어도 앞선 축에만 정렬이 유리하게 작동해, 두 축을 대등하게 좁히는 질의에는 잘 맞지 않는다. 여러 축을 동시에 놓고 공간을 좁히는 인덱스가 따로 필요하다는 뜻이다. k-d 트리가 그 첫 답이다.
🟣 k-d 트리: 축을 번갈아 가며 공간을 가른다
k-d 트리는 이름 그대로 k차원 데이터를 위한 이진 탐색 트리다. 발상은 단순하다. 이진 탐색 트리는 노드마다 하나의 값으로 공간을 왼쪽·오른쪽으로 갈랐다. k-d 트리는 레벨마다 기준으로 삼는 축을 번갈아 가며 같은 일을 한다. 2차원이라면 첫 레벨은 x축으로, 다음 레벨은 y축으로, 그다음은 다시 x축으로 나눈다.
각 노드는 자기 축의 값을 기준으로 공간을 반으로 쪼갠다. x축 노드라면 그 점보다 x가 작은 것은 왼쪽, 큰 것은 오른쪽이다. 다음 레벨의 y축 노드는 그렇게 나뉜 영역을 다시 y로 위아래로 가른다. 트리를 내려갈수록 담당하는 직사각형 영역이 점점 작아진다.
이 구조가 잘하는 것이 두 가지다. 하나는 다차원 범위 검색이다. "x는 이 사이, y는 저 사이"를 물으면, 각 노드에서 담당 축의 값을 조건과 비교해 조건에 걸리지 않는 하위 트리를 통째로 쳐낸다. 다른 하나는 최근접 이웃 검색이다. 특정 지점에서 가장 가까운 점을 찾을 때, 트리를 내려가 후보를 잡고 그 거리보다 가까운 영역만 남겨 되짚어 올라가며 탐색 범위를 줄인다. "내 위치에서 가장 가까운 가게"를 찾는 질의가 정확히 이 형태다.
🟣 공짜는 없다: 고차원의 저주와 균형 문제
k-d 트리도 앞선 트리들이 겪은 문제를 비슷하게 겪는다. 우선 균형이다. k-d 트리는 삽입 순서에 따라 한쪽으로 치우칠 수 있고, 삽입할 때마다 축이 번갈아 바뀌므로 AVL의 회전 같은 국소적 재균형이 곧바로 통하지 않는다. 그래서 실무에서는 점들을 한꺼번에 모아 각 축의 중앙값으로 나눠 균형 잡힌 트리를 통째로 구성하는 방식을 많이 쓴다. 대신 이 방식은 데이터가 자주 바뀌는 상황에는 약하다.
더 근본적인 한계는 고차원의 저주다. 차원이 낮을 때는 k-d 트리가 잘라 내는 영역이 커서 탐색이 효율적이다. 그런데 차원이 수십, 수백으로 올라가면 사정이 달라진다. 고차원에서는 점들 사이의 거리가 서로 엇비슷해지고, 최근접 이웃 탐색에서 쳐내야 할 하위 트리를 좀처럼 못 쳐낸다. 결국 트리의 거의 전체를 뒤지게 되어 전수 탐색과 별로 다르지 않아진다. k-d 트리가 실제로 이득을 보는 것은 대략 낮은 차원까지다.
이 한계 때문에 실무의 다차원 인덱스는 갈래가 나뉜다. 지도 데이터처럼 넓이를 가진 영역을 다룰 때는 R트리 계열을 쓴다. 점이 아니라 최소 경계 사각형으로 객체를 감싸고, B트리처럼 디스크 블록에 맞춰 다분기로 균형을 잡는다. 앞 장의 B트리 발상이 다차원으로 확장된 셈이다. 한편 이미지나 문장 임베딩 같은 초고차원 벡터의 유사도 검색은, 정확한 최근접 대신 근사 최근접 이웃(ANN)으로 방향을 튼다. 고차원에서 정확한 답을 고집하면 비용이 감당이 안 되니, 약간의 부정확을 받아들이고 속도를 얻는 트레이드오프다.
🟣 정리
- 앞선 트리들은 키가 한 축으로 정렬된다는 전제를 공유한다. 위도·경도처럼 여러 축을 대등하게 좁히는 질의에는 맞지 않아 다차원 인덱스가 따로 필요하다.
- k-d 트리는 레벨마다 기준 축을 번갈아 가며 공간을 반씩 가르는 k차원 이진 탐색 트리다. 다차원 범위 검색과 최근접 이웃 검색에 쓴다.
- k-d 트리는 삽입 순서에 균형이 흔들리고, 축이 번갈아 바뀌어 회전식 재균형이 어렵다. 그래서 중앙값으로 한꺼번에 구성하는 방식이 흔하다.
- 차원이 높아지면 거리들이 엇비슷해져 하위 트리를 못 쳐내는 고차원의 저주가 나타나고, k-d 트리의 이득이 사라진다.
- 그래서 공간 데이터는 R트리, 초고차원 벡터는 근사 최근접 이웃으로 갈라진다. 정확도와 속도의 트레이드오프를 매체와 차원에 맞춰 다르게 감수하는 것이다.
면접에서 벡터 검색이나 위치 기반 서비스 이야기가 나오면, k-d 트리에서 시작해 왜 고차원에서 무너지는지, 그래서 R트리나 ANN으로 왜 갈아타는지까지 짚으면 "인덱스는 하나가 아니라 데이터의 형태와 차원에 맞춰 고르는 것"이라는 관점을 보여줄 수 있다.
이 책은 순차 파일의 삽입 비용에서 출발해, 균형 이진 트리로 탐색을 지키고, B+트리로 디스크와 범위 검색을 잡고, k-d 트리로 여러 축까지 넓혀 왔다. 관통하는 질문은 처음부터 하나였다. 느린 저장 장치 위에서 데이터를 어떻게 적은 접근으로 찾을 것인가. 데이터베이스 인덱스 설계는 그 질문에 대한, 지금도 계속되는 답이다.