들어가기 전에

오랜만에 새로운 책을 사기 위해 퇴근 후에 광화문 교보문고에 갔고, 『SQL Anti Patterns - 빌 카윈 지음, 윤성준 옮김(인사이트, 2011)』 라는 책을 건져왔다. 잠깐 읽을 요량으로 목차를 살펴보고 있는데, 3장 이름이 순진한 트리 여서, 요즘 작업하는 프로젝트에서 다루는 계층 있는 데이터 구조가 떠오르더라. 혹시나 해서 봤더니 역시나 안티패턴이었다, orz.

그래서 이 기묘하고 어려운 문제를 어떻게 해쳐나가야 하는가에 대한 답을 얻기 위해 읽어봤고, 느낀 바… 는 없지만 공유하고자 하는 목적이 있어 블로그 포스팅을 작성하게 되었다.

• 구글에서 검색하면 더 쉽게 정리된 내용이 나올 것이라 생각은 하고 있다.

데이터와 트리

계층 구조를 가지는 데이터는 도처에 있다. 흔하게 구전되어 내려오는 예시로는 직원 트리(사장이 있고, 경영진이 있고, 중간 관리자가 있고, 하부 조직장이 있고, 직원이 있고…. 있는데, 모두가 직원이다.)가 있을 텐데, 조금 다른 예시를 들고 오고자 한다. 어쨌든 여기는 내 블로그니까 좀 참신한 예시가 필요하지 않겠는가.

상속이 필요해

자바 개발자로서 더 알기 좋은 것은 Object 와 수많은 하위 클래스 간의 상속관계이다. 모두 Object이고(원시 타입과 함수는 정신건강을 위해 생략할 필요가 있다.) 아래와 같은 특징을 가진다.

• 클래스는 해당 클래스를 상속받은 하위 클래스를 가질 수 있다.
• 클래스는 여러 개의 하위 클래스를 가질 수 있다
• 하위 클래스는 다시, 새로운 하위 클래스를 가질 수 있으며, 상속의 깊이에는 제한이 없다.

이 정도의 일반적인 생각과

• 추상화라는 미명 하에, 하위 클래스가 상위 클래스에 속하는지 확인해야 할 수도 있다.
• 다형성이라는 미명 하에, 상위 클래스가 하위 클래스를 가지는지 확인해야 할 수도 있다.
• 깊이는 관계가 없다

이 정도의, 조금 더 깊은 생각이 필요한 특징 말이다. 물론 더 엄밀하게 따지면, Object와 명세의 그 어느 사이에 낀 인터페이스 나 추상 클래스 가 지금 하고자 하는 이야기를 복잡하게-인터페이스는 다중 구현이 가능하고, Object를 상속하지도 않는다. 추상 클래스 자체로는 인스턴스를 만들 수 없다.- 만들겠지만, 내가 이 비유를 바탕으로 글을 쓰고 싶어하기 때문에-억지라는건 잘 알고 있다.- 과감하게 생략하였다.

여하간, 나는 어느 날 우연히 팔자에도 없는 IDE의 타입 체크 기능을 맡아 개발하게 되었고, 이를 위해 객체들의 족보를 따져볼 필요가 생겼다. 상속 정보 저장에 DB를 사용한다 가정하였을때, 어떻게 테이블을 구성해야 할까?

나의 부모님이 누구인가

가장 먼저 떠올릴 수 있는, 그래서 가장 많이 사용하게 될지도 모르는-확실한 이야기는 아니다- 방법은 테이블에 부모 키 컬럼을 추가하는 것이다.

• obj_table

테이블을 보았을 때 직관적으로 단순명료하다는 점 이외에, 이러한 구조는 다음과 같은 장점을 가진다.

• 참조하는 데이터의 정합성을 보장 가능하다.
• 인접하는 부모 데이터를 손쉽게 찾을 수 있다.
• 인접하는 자식 데이터 역시 손쉽게 찾을 수 있다.
• 단말 노드를 추가하는 것에 큰 비용이 들지 않는다

음, 쓸만하다. 그런데 다음과 같은 구조에선 어떻게 해야 하지?

public class MyObjectA {

}

public class MyObjectAa extends MyObjectA {

}

public class MyObjectAaa extends MyObjectAa {

}

public interface MyUtil {
    // 구현체는 따로 적지 않는다.
    void consume(MyObjectA a);
}

public class Main {
    public static void main(String args[]) {
        Myutil util = new MyUtilImpl();
        // MyObjectAaa 가 MyObjectA 패밀리의 일원이라는 것은 어떻게 찾을 수 있을까?
        util.consume(new MyObjectAaa);
    }
}

문제점

• 특정 노드의 모든-깊이-자식 조회가 대단히 어렵다.
• 반대로, 특정 단말의 모든 부모를 조회하기도 어렵다.
• 비단말 노드를 추가 / 삭제하는 비용이 강렬하다.

이러한 문제 때문에, 이러한 테이블 구조를 사용하는 애플리케이션에서는 모든 자식을 찾거나, 카운트 하기 위해 모든 데이터를 꺼내어 애플리케이션 로직 상에서 트리 구조로 재구성해야 한다는 문제점을 가진다.

이러한 설계를 사용하였다는 전조-안티패턴 사용의 빨간 불-는 다음과 같은 질문으로 인식 가능하다(36페이지)

트리에서 얼마나 깊은 단계를 지원해야 하지?

트리 데이터 구조를 관리하는 코드는 건드리는게 겁나.

트리에서 고아 노드를 정리하기 위해 주기적으로 스크립트를 돌려야 해.

1호 대안 - 저는 파일 시스템입니다.

실례, 거짓말이었습니다.

반드시 참조가 필요하다는 발상에서 벗어나, 경로를 나타내는 문자열 을 추가하여 부모 참조의 문제점을 해결할 수 있다. 예시는 아래와 같다.

• obj_table

‘이 무슨 해괴하고 망측한 발상인가’ 를 생각하기 전에, 이 테이블은 의외로 근본이 있는 모델링이다. 최소한, 트리를 만들고 관리하는데 사용하고자 하는 기능은 모두 구현이 가능하다.

• 조상 찾기

SELECT *
FROM obj_table AS o
WHERE '1/2/5/6/' LIKE o.path || '%';

• 후손 찾기

SELECT *
FROM obj_table AS o
WHERE o.path LIKE '1/2/' || '%';

이외에, 새로운 노드 추가도, 그것이 단말 노드인가 비단말 노드인가에 관계 없이 가능하며, 계층 구조에 근거한 데이터 정렬도 간단하다.

문제점

하지만 이 모델은 처음 생각하였듯 해괴하고 망측한 면이 존재한다, 경로 부분이다. 이 문자열 기반의 경로는 참조 정합성을 보장하지 않는다. 내용 또한, 테이블 컬럼 선언에 의해 길이가 제한받는다. 일정 뎁스가 넘어가거나, 데이터 키의 길이가 길어지면 문제가 발생할 수 있다는 의미가 된다. 또한 경로 문자열을 생성하는 것은 전적으로 애플리케이션 로직 의 영역이 된다.

2호 대안 - 수학적으로 머리를 써보는 것이에요.

중첩 집합은, 각 노드가 자신의 부모를 저장하는 대신, 자기 자손의 집합에 대한 정보를 저장한다. (42페이지)

중첩 집합은 개발자로 하여금, 머리를 쓰는 것을 강요한다. 기본적인 모델링 컨셉은 아래와 같다.

• obj_table

이렇게만 보면 잘 모르겠다. (그림을 그리면 조금더 알아보기 쉬울까 싶기도 하지만, 그림까지 그리고 싶은 것은 아니다.)

왼쪽 은 모든 자식 노드의 왼쪽 보다 작아야 한다(합을 의미하는 것이 아니라, every). 반면, 오른쪽 은 모든 자식 노드의 오른쪽 보다 커야 한다. 요는, DFS를 하면서 내려갈 때는 왼쪽, 올라갈 때는 오른쪽에 번호를 순차적으로 매겨주면 된다는 의미이다.

• 왼쪽 값이 현재 노드의 왼쪽과 오른쪽 사이 범위에 있는 노드들은 현재 노드의 자손들이다

• 반대로, 현재 노드의 왼쪽 값을 왼쪽과 오른쪽 사이 범위에 두고 있는 노드들은 현재 노드의 부모들이다.

중첩 집합은 노드의 삭제에 대해 유연하며, 손쉽게 하위 트리를 얻을 수 있고, 부모 트리도 쉽게 찾을 수 있다.

문제점

수학적으로 머리를 굴려야 하는 것에서 알 수 있듯, 당연히 중첩 트리에도 문제가 있다.

• DBMS가 DFS를 해주진 않는다.
  • 이는 트리 구조가 변경될 때마다 왼쪽 과 오른쪽 값을 다시 계산해주어야 한다는 문제점을 발생시킨다.
• 인접한 부모나 자식을 조회하기 어렵다.
• 역시나 참조 정합성을 보장하진 않는다.

중첩 트리는 트리 구조가 쉬이 변하지 않으며, 서브트리를 조회해야 할 일이 많을 때 적합한 구조이다.

3호 대안 - 클로저 테이블

클로저 테이블은 계층구조를 저장하는 단순하고 우아한 방법이다 (46페이지)

정말 우아하다.

클로저 테이블은 그 이름과 같이, 노드 간 연관(조상-후손)에 대한 정보를 추가적인 테이블에 저장한다.

• obj_table

• clo_table

• 자기 자신으로의 링크에 대한 정보 또한 저장하는 것을 확인할 수 있다.

클로저 테이블을 구성하면, 조상이나 자손을 조회하는 쿼리가 직관적이다.

• MyObjectAaa 의 모든 조상을 얻는 쿼리는 다음과 같다.

SELECT o.*
FROM clo_table AS c
JOIN obj_table AS o ON o.id = c.ancestor
WHERE c.descendant = 6;

• #4 에 새로운 단말 노드를 추가하는 방법은 아래와 같다.

1. 자기 자신을 참조하는 행 추가
2. clo_table 에서 #4 를 descendant 로 참조하는 모든 행을 복사하여, descendant 를 새롭게 추가된 단말 노드의 id로 바꿔 저장한다.

INSERT INTO clo_table (ancestor, descendant)
    SELECT c.ancestor, 8
    FROM clo_table AS c
    WHERE t.ancestor = 4
UNION ALL
    SELECT 8, 8;

• 단말 노드를 삭제할 때에는, 해당 단말 노드의 id 를 descendant 로 참조하는 모든 행을 삭제하면 된다.

DELETE FROM clo_table WHERE descendant = #{id}

• 특정 서브트리를 제거하려면 해당 서브트리의 루트를 descendant 로 참조하는 모든 행과, 해당 루트의 자손을 descendant 로 참조하는 모든 행을 차례대로 모두 삭제하면 된다.
  • 이 때, clo_table 에서 행이 삭제된다는 것이 클래스 데이터 자체를 삭제한다는 의미는 아니다.

DELETE
FROM clo_table
WHERE descendant IN (
    SELECT descendant
    FROM clo_table
    WHERE ancestor = #{id}
)

장점과 단점

클로저 테이블은 여러 장점과, 소소한 트레이드-오프를 발생시킨다.

• 조상과 자손의 조회가 간편하다.

  • 인접한 부모와 자손의 조회를 더욱 편하게 하기 위해서, 테이블에 깊이 정보를 추가할 수 있다.

    • 변형된 clo_table 테이블의 예시

(사족 - 깊이depth 컬럼이 있다면 인접한 부모/자손뿐만 아니라 루트 노드를 찾기도 쉬워지지 않을까 싶은데, 나중에 확인해볼 필요가 있겠다.)

• 서브트리의 계층 구조를 유지하기 편하다.
• 데이터의 삽입과 삭제가 용이하다.
• 참조 정합성을 유지할 수 있다.
• 별도 테이블을 사용한다는 점에서, 다른 계층 구조 저장 방식에 비해 저장공간을 많이 사용한다.