C#으로 개발을 하다 보면 벡터 데이터를 효율적으로 다뤄야 할 때가 종종 있다. 특히 AI나 머신러닝 작업에서 벡터 데이터베이스는 빠른 검색과 유사도 계산의 핵심인데, 여기서 KD-tree가 빛을 발한다. KD-tree는 다차원 데이터를 구조화해서 빠르게 탐색할 수 있게 해주는 자료구조로, C#으로 구현하면 꽤 실용적인 결과물을 얻을 수 있다. 이번 글에서는 C#으로 KD-tree를 활용해 벡터 데이터베이스를 만드는 방법을 단계별로 풀어보려 한다. 코딩에 관심 있는 분들이라면 따라 하며 이해하기 좋을 테니, 한 번 읽어보자.
KD-tree가 뭔데?
KD-tree는 K차원 트리(K-Dimensional Tree)의 줄임말로, 다차원 공간에서 데이터를 계층적으로 분할해 저장하는 이진 트리다. 예를 들어 2D 좌표나 3D 벡터 같은 데이터를 다룰 때, 각 노드가 특정 차원을 기준으로 공간을 나눠서 검색 속도를 높인다. 벡터 데이터베이스에서는 주로 ‘최근접 이웃 검색(Nearest Neighbor Search)’이나 ‘범위 검색(Range Search)’에 활용된다. C#으로 구현하면 .NET의 강력한 컬렉션과 연산 기능을 활용할 수 있어서, 머신러닝이나 게임 개발 같은 분야에서 유용하다. 복잡해 보이지만 기본 개념을 잡으면 금방 손에 익는다.
기본 구조 설계하기
KD-tree를 C#으로 구현하려면 먼저 노드 클래스를 만들어야 한다. 각 노드는 벡터 데이터와 분할 축, 좌우 자식 노드를 포함한다. 아래는 간단한 예제 코드다.
public class KDNode
{
public double[] Vector { get; set; } // 벡터 데이터
public int SplitAxis { get; set; } // 분할 기준 차원
public KDNode Left { get; set; } // 왼쪽 자식
public KDNode Right { get; set; } // 오른쪽 자식
public KDNode(double[] vector, int splitAxis)
{
Vector = vector;
SplitAxis = splitAxis;
Left = null;
Right = null;
}
}이 구조는 벡터와 분할 축을 저장하며, 트리가 성장할 수 있게 좌우 자식을 연결한다. 예를 들어 3차원 벡터라면 Vector는 [x, y, z] 같은 배열이 된다. SplitAxis는 0(x), 1(y), 2(z) 중 하나로, 어떤 차원을 기준으로 나눌지 정한다.
KD-tree 구축하기
트리를 만드는 건 재귀적으로 데이터를 삽입하면서 진행된다. 각 단계에서 데이터를 특정 차원으로 정렬하고 중간값을 기준으로 나눈다. C# 코드로 보면 다음과 같다.
public class KDTree
{
private KDNode root;
public void Insert(double[] vector)
{
root = InsertRec(root, vector, 0);
}
private KDNode InsertRec(KDNode node, double[] vector, int depth)
{
if (node == null)
return new KDNode(vector, depth % vector.Length);
int axis = node.SplitAxis;
if (vector[axis] < node.Vector[axis])
node.Left = InsertRec(node.Left, vector, depth + 1);
else
node.Right = InsertRec(node.Right, vector, depth + 1);
return node;
}
}
여기서 depth % vector.Length는 차원을 순환하며 분할하도록 만든다. 3D 벡터라면 x, y, z 순으로 나눈다. 이렇게 하면 트리가 균형 있게 자라서 검색 성능이 좋아진다. 데이터를 넣을 때는 Insert 메서드를 호출하면 된다.
최근접 이웃 검색 구현
KD-tree의 진가는 검색에서 나온다. 특정 벡터와 가장 가까운 이웃을 찾는 로직을 짜보자. 유클리드 거리를 계산하며 트리를 탐색한다.
public double[] FindNearest(double[] target)
{
var result = new { Node = root, Distance = double.MaxValue };
result = NearestRec(root, target, 0, result);
return result.Node.Vector;
}
private dynamic NearestRec(KDNode node, double[] target, int depth, dynamic best)
{
if (node == null)
return best;
double dist = EuclideanDistance(node.Vector, target);
if (dist < best.Distance)
best = new { Node = node, Distance = dist };
int axis = depth % target.Length;
double diff = target[axis] - node.Vector[axis];
KDNode near = diff < 0 ? node.Left : node.Right;
KDNode far = diff < 0 ? node.Right : node.Left;
best = NearestRec(near, target, depth + 1, best);
if (Math.Abs(diff) < best.Distance)
best = NearestRec(far, target, depth + 1, best);
return best;
}
private double EuclideanDistance(double[] a, double[] b)
{
double sum = 0;
for (int i = 0; i < a.Length; i++)
sum += Math.Pow(a[i] - b[i], 2);
return Math.Sqrt(sum);
}
이 코드는 타겟 벡터와의 거리를 계산하며 트리를 탐색한다. 가까운 쪽을 먼저 확인하고, 필요하면 반대쪽도 체크해서 최적의 이웃을 찾는다. 동적 객체를 썼지만, 성능을 중시한다면 별도 클래스로 만드는 게 낫다.
벡터 데이터베이스로 활용하기
KD-tree를 데이터베이스로 쓰려면 삽입과 검색 외에 관리 기능도 필요하다. 예를 들어, List에 벡터를 저장하고 KD-tree로 인덱싱하는 식이다.
public class VectorDatabase
{
private KDTree tree;
private List<double[]> vectors;
public VectorDatabase()
{
tree = new KDTree();
vectors = new List<double[]>();
}
public void AddVector(double[] vector)
{
vectors.Add(vector);
tree.Insert(vector);
}
public double[] SearchNearest(double[] query)
{
return tree.FindNearest(query);
}
}이렇게 하면 벡터를 추가하고 검색할 수 있는 간단한 데이터베이스가 완성된다. 대규모 데이터라면 메모리와 속도를 고려해 트리를 주기적으로 재구성하거나 파일로 저장하는 로직을 추가할 수 있다.
성능과 한계
KD-tree는 차원이 낮을 때(2~10차원) 검색 속도가 O(log n)에 가까워서 효율적이다. 하지만 차원이 20을 넘으면 ‘차원의 저주’ 때문에 성능이 떨어질 수 있다. 이런 경우에는 근사 최근접 이웃 알고리즘(ANN)이나 다른 구조를 고려해야 한다. C#으로 짤 때는 LINQ나 병렬 처리를 활용하면 대규모 데이터에서도 속도를 더 끌어올릴 수 있다.
KD-tree를 C#으로 구현하면 벡터 데이터베이스의 기본 틀을 잡는 데 큰 도움이 된다. 머신러닝 모델의 임베딩 검색이나 게임에서의 충돌 탐지 같은 실무에서 바로 써먹을 수 있다.