RDBMS 에서 tree structure 다루기

Graph DB를 사용하는 방법 도 있지만, RDBMS가 일반적으로 사용되기 때문에 여러 가지 이론들이 나와있습니다.

크게 3가지에 대해 다루어 봅니다.

1. Parent-Child
2. Nested Sets
3. Materialized Path

Patenet-Child (Adjacency list)

가장 직관적으로 생각 할 수 있는 구조로, 자식이 부모의 기본키를 가지도록 하는 전략이다.

적용, 활용이 가장 쉽지만, 성능면에서 가장 비효율적인 방법이다.

 

데이터 삽입/편집

자식엔티티가 부모 엔티티의 PK를 들고 있으면 되기에 가장 쉽다.

 

데이터 selection

특정 데이터를 검색하기 매우 어렵다.
계층이 내려갈 때마다 쿼리를 계속 날려야 하기 때문이다.
따라서 데이터 검색을 위해 SQL를 자주 날려줘야 하는 단점이 있다.

 

데이터 삭제

부모를 삭제할 경우 orphan 문제가 발생 할 수 있기 때문에 신중하게 생각해야 함.

디렉토리를 삭제한다고 가정할 경우 CASCADE로 하위 데이터를 날리는 걸 생각할 수 있음.

 

정리

빈번한 구조 변경이 필요한 경우(데이터가 자주 추가, 변경이 발생할 경우) 매우 효율적이다.

하지만 쿼리시 성능이 많이 저하된다.

 

Nested Set

계층적인 데이터 구조를 집합 구조로 생각하고 RDBMS를 설계하는 전략.

각 엔티티는 lft, rgt 필드를 가지고, 자식 엔티티는 그 사이의 lft, rgt 필드값을 가지고 있다.

 

데이터 삽입/편집

부모 엔티티의 lft, rgt를 변경해줘야 해서 매우 어렵다. 이부분은 sql 말고 로직적으로 해결을 해야 함. 또한 id가 아닌 lft, rgt를 가지고 검색등을 해야 하기 때문에 무결성을 따로 책임 져야 한다.

 

데이터 selection

lgt, rgt를 알고 있다면 가장 손쉬운 방법으로 선택할 수 있다.

 

데이터 제거

lgt, rgt를 다시 설정해줘야 한다.

 

정리

데이터 선택을 가장 단순하게 할 수 있지만, 그만큼 삽입/편집이 어렵다.

selection이 빈번하지만, 데이터 추가, 변경이 적은 경우 추천된다.

 

Enumeration Path

웹페이지와 같이 경로를 RDB에 적용하여 계층적인 데이터 구조를 저장하는 방법.

“1/2/3/4”와 같은 path 필드를 엔티티에 추가하여 경로를 저장한다.

데이터 삽입/편집

데이터를 추가하기 위해서는 부모의 경로(id)를 가져고오, 그 위에 자신의 id를 추가해야 한다.

데이터 위치가 변경되거나, 계층 사이에 데이터를 추가해야 하는 경우, 직간접적으로 모든 자식의 path를 수정해야 하는 단점이 있다.

 

데이터 selection

path를 알고 있다면 데이터를 검색하는 건 다른 전략에 비해 매우 간결하다.

SELECT * FROM family WHERE path LIKE '/1/2/%' ORDER BY path ASC;

Like 절로 검색하고자 하는 경로만 지정해주면 된다.

 

데이터 제거

다른 전략과 달리 데이터 삭제시 하위 계층 데이터까지 한번에 삭제하는게 편리하다.

 

정리

selection이 매우 간편하다. 말단에 데이터를 추가하는 것이 매우 편하다.

중간에 데이터를 끼워 넣기가 매우 복잡하다.

 

 

 

reference

https://railsware.com/blog/storing-tree-structures-in-the-rdbms/

https://ibocon.tistory.com/206