[Java] 대용량 노드 관계 조회에서 O(N) 성능 고려해보기

1. 문제

노드 간 관계를 관리하는 테이블이 있다.

• NODE_ID : 현재 Node ID
• PARENT_ID : 부모 Node ID

이  테이블의 구조는 전형적인 단방향 트리(또는 포레스트) 형태다.

 

“이 노드는 최종적으로 어떤 Root 노드에 속하는가?”

이번에 내가 구해야하는 목표다.

---

2. 구현 제약 조건

• ❌ 재귀 사용 불가
• ❌ DB 재귀 쿼리 사용 불가
• ❌ 노드 단위 DB 재조회 금지
• ❌ 테이블 구조 변경 불가
• ✅ 대용량 데이터에서도 성능 보장 필요

한 번의 조회 + Java 코드만으로 + 빠르게

---

3. 위 제약 조건의 이유

❌ 재귀 탐색

String findRoot(String id) { 
	if (parent(id) == null) return id; 
    return findRoot(parent(id)); 
}

당연히 쉽게 구현하려면 재귀 탐색을 하면된다.

그러나 현재 상황에서 깊이의 제한이 없다는 문제가 있었다. 

• 깊이가 깊어질수록 Stack 위험
• 동일한 경로를 계속 다시 탐색
• 시간복잡도는 사실상 O(N × depth)

대용량에서는 절대 선택할 수 없는 구조다.

❌ 노드마다 DB 조회

N개의 노드 → N번의 SELECT → 최악의 경우 N²

이건 말 그대로 시스템을 죽이는 패턴이므로 선택할 수 없다.

---

4. 핵심 전환점: “탐색”이 아니라 “압축”이다

❌ “Root를 어떻게 찾을까?”
✅ “이미 찾은 Root를 어떻게 재사용할까?”

이 질문이 O(N) 성능의 출발점이었다.

---

5. 전체 전략 요약

내가 선택한 전략은 단순하지만 강력하다.

1. DB는 단 한 번만 조회
2. 부모 관계를 Map으로 메모리에 적재
3. Root 탐색 중 지나온 경로를 기억
4. Root를 찾는 순간, 경로 전체를 Root로 압축

이 구조는 사실상 Union-Find + Path Compression과 동일하다.

---

6. 메모리 구조 설계

① 부모 관계 Map

Map<String, String> parentMap;

 

child → parent

② 최종 Root 캐시

Map<String, String> rootMap;

procId → rootProcId

---

7. 동작 방식 정리

🔍 탐색 전 상태

이와 같은 구조라면 두 경로가 존재한다.

• A → B → C → R
• D → C → R

🔄 A를 기준으로 Root 탐색

path = [A, B, C] root = R 을 알 수 있게된다.

⚡ Path Compression 적용 후

• A → R
• B → R
• C → R
• D → R

path 정보를 활용해서 A, B, C의 root를 알 수 있게 되었고 실제 D도 이미 C가 부모이므로 C의 root를 따라가게 된다.

이 순간부터 A, B, C, D는 모두 O(1) 접근

---

8. 핵심 코드 (성능의 중심)

for (String procId : parentMap.keySet()) {

    // 이미 계산된 프로세스는 스킵
    if (rootMap.containsKey(procId)) continue;

    String cur = procId;
    List<String> path = new ArrayList<>();

    while (true) {

        // 이미 Root가 계산된 노드를 만난 경우
        if (rootMap.containsKey(cur)) {
            String root = rootMap.get(cur);
            for (String p : path) {
                rootMap.put(p, root);
            }
            break;
        }

        path.add(cur);
        String parent = parentMap.get(cur);

        // Root 도달
        if (parent == null || "0".equals(parent)) {
            for (String p : path) {
                rootMap.put(p, cur);
            }
            break;
        }

        cur = parent;
    }
}

---

9. 이 코드가 O(N)이 되는 이유

🔑 핵심 포인트는 단 하나다

각 노드는 Root 탐색 경로에 최대 한 번만 포함된다

• Path Compression으로 인해 같은 경로를 다시 타지 않는다
• Map 조회는 O(1) 이다.

결과적으로

전체 시간 복잡도 ≈ O(N)
이건 운이 좋으면 O(N) 이 아니라 구조적으로 O(N) 이다.

---

10. 성능 비교 요약

방식	시간복잡도	대용량 데이터 처리
재귀	O(N × depth)	❌
DB 반복 조회	O(N²) 가능	❌
현재 방식	O(N)	✅

---

11. 이 설계에서 가장 중요했던 생각

“탐색을 빠르게 하는 방법”이 아니라
“탐색을 다시 하지 않게 만드는 방법”

 

이 관점 전환이 이번 문제에서 가장 큰 성능 차이를 만들었다.

---

13. 마무리

• 재귀 없는 안정성
• 대용량에서도 예측 가능한 성능
• DB 부하 최소화

트리 구조를 다룬다면, 언젠가 반드시 써먹게 될 패턴인 것 같아서 정리해본다.

---

📌 한 줄 요약

대용량 트리에서 성능을 만든 건
“얼마나 빨리 찾느냐”가 아니라
“얼마나 다시 안 찾느냐”였다.