평탄화된 데이터 구조에서 트리 성능 최적화하기: 인덱싱과 인접 리스트의 활용

웹 에디터나 복잡한 대시보드를 개발할 때 데이터의 효율적인 관리를 위해 트리 구조의 데이터를 평탄화하여 배열로 관리하는 방식은 매우 일반적입니다. 이는 데이터베이스 저장이나 Zustand, Redux와 같은 상태 관리 라이브러리에서 데이터 일관성을 유지하기에 매우 유리하기 때문입니다.

하지만 노드 수가 수천 개 단위로 늘어나면 평탄화된 배열은 심각한 성능 병목을 일으킵니다. 이번 포스팅에서는 이러한 문제를 해결하기 위해 인접 리스트 개념을 도입하고 탐색 성능을 O(n)에서 O(1)로 최적화한 과정을 상세히 다룹니다.

1. 성능 병목의 원인: O(n) 탐색과 정렬 비용

기존 데이터 구조는 모든 노드가 하나의 플랫 배열에 담겨 있었습니다. 각 노드는 parent_id와 자신의 순서를 나타내는 position 값을 가지고 있습니다.

typescriptconst nodes = [
  { id: "p1", parent_id: null, position: 0, type: "Page" },
  { id: "c1", parent_id: "p1", position: 1, type: "Button" },
  { id: "c2", parent_id: "p1", position: 0, type: "Stack" },
];

이 구조에서 화면을 렌더링하거나 특정 노드를 조작할 때 발생하는 연산은 다음과 같습니다.

노드 조회 (find)

특정 ID를 가진 노드를 찾기 위해 배열 전체를 순회해야 합니다. 배열 순회 비용은 O(n)이며, 캔버스의 모든 노드가 각자 부모를 찾거나 상세 정보를 조회할 때마다 이 비용이 발생합니다.

자녀 노드 렌더링 (filter & sort)

트리 구조를 화면에 다시 그리기 위해서는 부모의 자녀들을 찾아야 합니다.

filter: parent_id가 일치하는 노드들을 찾기 위해 O(n) 연산 수행
sort: 찾은 자녀들을 position 필드 기준으로 정렬하기 위해 O(k log k) 연산 수행

노드가 1,000개일 때 각 노드가 렌더링될 때마다 이 과정을 반복하면 사용자 경험은 급격히 악화됩니다.

2. 해결책: 인접 리스트(Adjacency List) 인덱싱

우리는 원본 데이터의 형태를 유지하면서 조회를 위한 색인(Index)을 별도로 생성하는 전략을 선택했습니다.

도입한 자료구조

nodeMap: id를 키로 사용하는 Record 객체입니다. 특정 ID에 즉시 접근할 수 있게 해줍니다.
childrenMap: parent_id를 키로 가지며 이미 정렬된 자녀 노드들의 배열을 값으로 가집니다. 부모 ID만 알면 즉시 정렬된 자녀 리스트를 얻을 수 있습니다.

3. 구현의 핵심 디테일

Immer 호환성을 위한 Record 사용

Map 대신 일반 객체(Record)를 사용했습니다. 이는 Zustand의 Immer 미들웨어에서 상태 변화를 추적하고 불변성을 유지하는 데 더 적합하기 때문입니다.

루트 노드의 관리

parent_id가 null인 최상위 노드들을 관리하기 위해 "root"라는 특수 키를 childrenMap에 도입했습니다. 이를 통해 루프 조건 없이 일관된 로직으로 트리의 시작점을 찾을 수 있습니다.

인덱스 갱신 로직

데이터가 추가, 삭제되거나 순서가 변경되는 액션이 발생할 때만 딱 한 번 인덱스를 재구축하도록 설계했습니다.

typescriptfunction buildNodeMaps(nodes: WcxNode[] | null) {
  const nodeMap: Record<string, WcxNode> = {};
  const childrenMap: Record<string, WcxNode[]> = {};

  if (!nodes) return { nodeMap, childrenMap };

  // 1Pass: 모든 노드 순회하며 맵 구축
  for (const node of nodes) {
    nodeMap[node.id] = node;

    const parentKey = node.parent_id ?? "__root__";
    if (!childrenMap[parentKey]) {
      childrenMap[parentKey] = [];
    }
    childrenMap[parentKey].push(node);
  }

  // 2Pass: 자녀 배열 정렬
  for (const key in childrenMap) {
    childrenMap[key].sort((a, b) => a.position - b.position);
  }

  return { nodeMap, childrenMap };
}

4. 최적화 적용 결과

삭제 연산의 상향 평준화

기존에는 재귀적으로 자녀를 삭제할 때마다 전체 배열을 filter해야 했습니다. 하지만 개선 후에는 childrenMap을 통해 후손 ID들을 즉시 수집할 수 있어 삭제 로직의 복잡도가 비약적으로 향상되었습니다.

레이어 패널의 렌더링 속도

레이어 패널처럼 트리를 깊게 탐색해야 하는 UI에서 더 이상 filter와 sort를 반복하지 않습니다. 이미 정렬된 데이터를 키 값으로 단번에 가져오기 때문에 수천 개의 노드 환경에서도 부드러운 스크롤과 응답성을 보여줍니다.

5. 결론: 트레이드 오프

이 방식에는 추가적인 메모리 사용이라는 비용이 발생합니다. 하지만 에디터 환경에서 수천 개의 객체 참조를 Map에 저장하는 비용은 수 밀리초마다 발생하는 O(n) 연산의 CPU 비용보다 현저히 낮습니다.

평탄화된 배열 구조를 사용하고 계신다면 이와 같은 인덱싱 기법을 통해 데이터 관리의 편의성과 런타임 성능이라는 두 마리 토끼를 모두 잡아보시기 바랍니다.