계층형 구조 만들기3 (Hierarchical Structure, 중첩집합,NestedSet)

와 이거 구현하기 힘들었다... 바로 가보자 생각보다 신경 쓸 것이 많았고, 놓친 부분이 많아서 테스트 엄청 돌려봤다.

중첩집합 이란 ?

우리는 지금껏 노드의 관계를 표현하기 위해 새로운 테이블 혹은 패스를 기록하거나 아니면 fk를 조인시키는 등의 과정을 지나왔다.

중첩집합 은 이런 거 없이 현재 가지고 있는 엔티티에 left right 값을 추가해주어 left right 값에 의해 노드 간의 관계를 유지하는 방법이다.

 

위와 같은 사진으로 구현하는 게 중첩 집합이다. 나름 직관적이지 않은가?  바로 가보자.

엔티티

public class Comment {

    @Id @GeneratedValue(strategy = GenerationType.IDENTITY)
    private Long id;

    private String comment;
    @Column(name ="left_node")
    private int left;
    @Column(name = "right_node")
    private int right;
    private int level;

    public void updateComment(String newComment){
        this.comment = newComment;
    }
}

left 랑 right는 join 예약어로 사용되니 에러 만나요( 테스트 돌리는데 테이블이 없다고 해서 당황스러웠다. 쿼리 가져다가 콘솔에 써보니 left right 때문이더라 ㅠ)

 

Interface Repository

@Repository
public interface CommentRepository extends JpaRepository<Comment,Long> {
    Optional<Comment> findByComment(String comment);
}

---

- 잡소리

사실 이거 하기 전에 테이블에 데이터가 하나라도 있다면 루트 즉 최상위 계층을 넣어주거나 아니면 아래로 넣어주는 방식으로 작성하려고 쿼리를 생각하다가 쿼리를 작성하려고 보니 궁금했다. 그래서 exsit 말고 다른방법을 찾다 보니 
select * from table / select 1 from table을 해보니 두 개의 쿼리 타는 방법이 달랐다.

왼쪽이 fullscan 오른쪽이 index scan 이였다. 뭐 때문에 이렇게 타입이 나뉘어서 타는지 궁금해서 알아보니 * 이용해서 조회를 하게 되면 index 가  없는 키도 조회해야 하기 때문에 저런 식의 타입으로 expain 조회하면 나오더라. 당연히 pk fk fk 등으로 조합해서 select 찍어오면 이런 경우는 없다. 

explain으로 검색할 때 type에서 index all 은 피해야 할 타입 중 하나 이기 때문에 이걸 개선하고 싶어서 삽질 좀 했다 

select top 1 1 from table limit 1 oracle에서는 이게 지원된다 1개의 로우가 찾는 즉시 멈추는 쿼리 다 즉 row를 일일이 다 헤짚어 다니지 않아도 된다.

이런 방식이 mysql 에는 없나 궁금해서 찾다 보니 mysql 공홈에서 제안하는 방법이 있다.

prefer_ordering_index  = off로 꺼주면 range 스캔까지 끌어올릴 수 있다 이 내용을 어디서 읽은 거 같은데 이렇게 다시 보니 반갑다 ㅋ

물론 이게 옳은 방법이 아닐지 모르나 만약 데이터가 너무 많아서 속도가 안 나온다면 이 방법을 이용해서 조회 성능을 향상할 수 있는 방법 중 하나로 기억하고 나중에 써먹자.

---

 

바로 인서트부터 구현해 보자.

private NumberExpression<Integer> getLeftCaseBuilder(int target) {
    return new CaseBuilder()
            .when(comment1.left.goe(target))
            .then(comment1.left.add(2))
            .otherwise(comment1.left);
}
public void insertUpdateLeftRight(int target){
    queryFactory.update(comment1)
            .set(comment1.left, getLeftCaseBuilder(target))
            .set(comment1.right,comment1.right.add(2))
            .where(comment1.right.goe(target))
            .execute();
}
    
public void insertComment(Comment parents, String comment){

    insertUpdateLeftRight(parents.getRight());
    // insert
    commentRepository.save(Comment.builder()
                    .left(parents.getRight())
                    .right(parents.getRight() + 1)
                    .level(parents.getLevel() + 1)
                    .comment(comment).build()
    );
}

 

하나의 데이터가 들어갈 때마다 right와 left를 업데이트해준다. 부모를 잡고 들어가기 때문에 부모의 오른쪽을 기준으로  오른쪽 보다 큰 경우만 업데이트해주면 된다. 단 왼쪽 노드 의 업데이트는 조심해야 한다. 부모 노드보다 작은 왼쪽 노드들은  업데이트를 해줄 필요가 없기 때문에 caseBuilder를 이용해서 위와 같이 작성했다.

 

QueryDsl에서는 update set을 그냥 체이닝 해서 쓰면 원하는 만큼 할 수 있다. 

CaseBuilder의 반환 값이 Expression 인 점을 이용해 위와 같이 작성했다.

테스트 코드 기본 세팅

class CommentTest {
    @Autowired
    private CommentRepository commentRepository;
    @Autowired
    private CommentQuery commentQuery;
    @Autowired
    private EntityManager em;

    @BeforeEach
    private void init(){
        //insert root
        Comment root = Comment.builder()
                .left(1)
                .right(2)
                .level(0)
                .comment("3 대 500 인 사람 댓글 달아봐")
                .build();

        Comment save = commentRepository.save(root);
        //insert 1st Layer
        insertCommentAndFlushClear(save,"3대 500 아래는 없어요 ?");
        insertCommentAndFlushClear(save,"3대 520 언더아머 회원임");

//        //insert 2nd Layer
        Comment comment1 = commentRepository.findByComment("3대 500 아래는 없어요 ?").get();
        insertCommentAndFlushClear(comment1,"3대 490 ㅠㅠ");
        insertCommentAndFlushClear(comment1, "300 인대요 ? 사람이세요?");

//        //insert 2nd Layer
        Comment comment2 = commentRepository.findByComment("3대 520 언더아머 회원임").get();
        insertCommentAndFlushClear(comment2,"스벤데 몇이고");
        insertCommentAndFlushClear(comment2,"3대 660");

//        //insert 3rd Layer
        Comment comment3 = commentRepository.findByComment("스벤데 몇이고").get();
        insertCommentAndFlushClear(comment3,"구라네 10 이 비는데 ?");
    }

    @AfterEach
    public void afterInit(){
        em.flush();
        em.clear();
    }

    private void insertCommentAndFlushClear(Comment parent,String comment){
        commentQuery.insertComment(parent,comment);
        em.flush();
        em.clear();
    }

코드를 한꺼번에 넣기 때문에 flush clear를 하지 않으면 right left 노드 의 숫자가 자기 멋대로다. 꼭 해주자.

 

저거 말고 중간에 끼워 넣는 걸 해보고 싶었다. 

구현

    public void insertBetween(Comment head,Comment tail,String comment){
        queryFactory.update(comment1)
                .set(comment1.left, comment1.left.add(1))
                .set(comment1.right, comment1.right.add(1))
                .set(comment1.level, comment1.level.add(1))
                .where(comment1.left.goe(tail.getLeft()),
                        comment1.right.loe(tail.getRight()))
                .execute();

        queryFactory.update(comment1)
                .set(comment1.left,getLeftCaseBuilderWithoutRoot(tail.getLeft()))
                .set(comment1.right,comment1.right.add(2))
                .where(comment1.right.gt(tail.getRight()),
                        comment1.ne(tail))
                .execute();

        commentRepository.save(Comment.builder()
                .left(head.getLeft()+1)
                .right(tail.getRight()+2)
                .level(head.getLevel() + 1)
                .comment(comment).build());
    }

쿼리를 무려 3번이나 던져야 한다. 저장을 위한 쿼리와 사이에 끼여 들어간다면 사이에 끼이는 기준으로 부모가 가지고 있는 하위 노드 와 부모 보다 큰 노드 들에 대해 다른 업데이트를 날려야 하기 때문에 위와 같이 작성했다.

 

테스트 코드

    @Test
    public void insertBetween() throws Exception{
        Comment comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Comment tail = commentRepository.findByComment("3대 520 언더아머 회원임").get();
        commentQuery.insertBetween(comment,tail,"3대 1억");
        em.clear();
        em.flush();

        List<Comment> all = commentRepository.findAll();
        for (Comment comment1 : all) {
            System.out.println(comment1);
        }

        comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Assertions.assertThat(comment.getLeft()).isEqualTo(1);
        Assertions.assertThat(comment.getRight()).isEqualTo(18);
    }

 

삭제구현

public void deleteComment(Comment comment){
        queryFactory.update(comment1)
                .set(comment1.left, subTractWithoutLeftRoot(comment.getLeft()))
                .set(comment1.right, comment1.right.subtract(2))
                .where(comment1.right.gt(comment.getRight()))
                .execute();

        queryFactory.update(comment1)
                .set(comment1.left, comment1.left.subtract(1))
                .set(comment1.right, comment1.right.subtract(1))
                .set(comment1.level, comment1.level.subtract(1))
                .where(comment1.left.gt(comment.getLeft()),
                        comment1.right.lt(comment.getRight()))
                .execute();


        queryFactory.delete(comment1).where(comment1.eq(comment)).execute();
    }

삭제도 마찬가지로  2번의 업데이트가 필요하다 중간에서 삭제되는 경우가 있기 때문에 이걸 고려해 주어야 한다.

 

테스트 코드

@Test
void deleteComment() throws Exception{
    Comment comment = commentRepository.findByComment("3대 500 아래는 없어요 ?").get();

    commentQuery.deleteComment(comment);

    em.flush();
    em.clear();

    List<Comment> all = commentRepository.findAll();
    for (Comment comment1 : all) {
        System.out.println(comment1);
    }
    Comment comment1 = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
    Assertions.assertThat(comment1.getRight()).isEqualTo(14);
}

이 중첩 모델의 장점 중 하나는 바로 조회에 있다고 생각한다. 

public List<Comment> findByLayer(int level){
    return queryFactory.selectFrom(comment1)
            .where(comment1.level.eq(level))
            .fetch();
}

public List<Comment> getAllCommentFromComment(Comment comment){
    return queryFactory.selectFrom(comment1)
            .where(comment1.left.gt(comment.getLeft()),
                    comment1.right.lt(comment.getRight()))
            .fetch();
}

처음 entity에 level 필드를 생성했다. 이런 계층 별 탐색도 추가해보고 싶어서 추가했는데 나름 조회 쿼리를 짜는데 손쉽게 된다.

인접노드 블로그 글 쓸 때 조회 할 때 정말 고민을 많이 하면서 작성했는데 이렇게 쉽게 된다. 현재 노드를 기준으로 왼쪽은 크고 오른쪽은 작은 거 그냥 긁어오면 자식(즉 서브 트리) 모두를 조회할 수 있다.

 

이 중첩모델은 조회에서 어마어마한 이점이 있으나 위에서 보는 바와 같이 업데이트 삭제 삽입 하는데 생각보다 복잡했다. 서브트리의 이동 이 라던지 루트 위에 다시 루트를 생성한다는 등 배제한 경우 가 있음에도 이렇게 코드가 생각보다 길다. 

 

중첩모델을 사용함에 있어서는 인서트가 자주 일어난다면.. 다시 한번 고려해보고 사용해야 할 거 같다. 그렇지만 조회를 자주 한다면 최고인 것 같다.

 

테스트 코드 전문

package com.example.dowhateveriwant.entity;

import com.example.dowhateveriwant.repository.commet.CommentQuery;
import com.example.dowhateveriwant.repository.commet.CommentRepository;
import org.assertj.core.api.Assertions;
import org.junit.jupiter.api.AfterEach;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.test.context.SpringBootTest;
import org.springframework.transaction.annotation.Transactional;

import javax.persistence.EntityManager;

import java.util.List;

@SpringBootTest
@Transactional
class CommentTest {
    @Autowired
    private CommentRepository commentRepository;
    @Autowired
    private CommentQuery commentQuery;
    @Autowired
    private EntityManager em;

    @BeforeEach
    private void init(){
        //insert root
        Comment root = Comment.builder()
                .left(1)
                .right(2)
                .level(0)
                .comment("3 대 500 인 사람 댓글 달아봐")
                .build();

        Comment save = commentRepository.save(root);
        //insert 1st Layer
        insertCommentAndFlushClear(save,"3대 500 아래는 없어요 ?");
        insertCommentAndFlushClear(save,"3대 520 언더아머 회원임");

//        //insert 2nd Layer
        Comment comment1 = commentRepository.findByComment("3대 500 아래는 없어요 ?").get();
        insertCommentAndFlushClear(comment1,"3대 490 ㅠㅠ");
        insertCommentAndFlushClear(comment1, "300 인대요 ? 사람이세요?");

//        //insert 2nd Layer
        Comment comment2 = commentRepository.findByComment("3대 520 언더아머 회원임").get();
        insertCommentAndFlushClear(comment2,"스벤데 몇이고");
        insertCommentAndFlushClear(comment2,"3대 660");

//        //insert 3rd Layer
        Comment comment3 = commentRepository.findByComment("스벤데 몇이고").get();
        insertCommentAndFlushClear(comment3,"구라네 10 이 비는데 ?");
    }

    @AfterEach
    public void afterInit(){
        em.flush();
        em.clear();
    }

    private void insertCommentAndFlushClear(Comment parent,String comment){
        commentQuery.insertComment(parent,comment);
        em.flush();
        em.clear();
    }

    @Test
    void insertTest() throws Exception{
        List<Comment> all = commentRepository.findAll();
        for (Comment comment1 : all) {
            System.out.println(comment1);
        }

        Comment comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Assertions.assertThat(comment.getLeft()).isEqualTo(1);
        Assertions.assertThat(comment.getRight()).isEqualTo(16);
    }

    @Test
    public void insertBetween() throws Exception{
        Comment comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Comment tail = commentRepository.findByComment("3대 520 언더아머 회원임").get();
        commentQuery.insertBetween(comment,tail,"3대 1억");
        em.clear();
        em.flush();

        List<Comment> all = commentRepository.findAll();
        for (Comment comment1 : all) {
            System.out.println(comment1);
        }

        comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Assertions.assertThat(comment.getLeft()).isEqualTo(1);
        Assertions.assertThat(comment.getRight()).isEqualTo(18);
    }

    @Test
    public void updateComment() throws Exception{
        String updateOne = "업데이트 된 커멘트";
        Comment comment = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        comment.updateComment(updateOne);

        em.flush();
        em.clear();

        comment = commentRepository.findByComment(updateOne).get();
        Assertions.assertThat(comment.getComment()).isEqualTo(updateOne);
    }

    @Test
    void deleteComment() throws Exception{
        Comment comment = commentRepository.findByComment("3대 500 아래는 없어요 ?").get();

        commentQuery.deleteComment(comment);

        em.flush();
        em.clear();

        List<Comment> all = commentRepository.findAll();
        for (Comment comment1 : all) {
            System.out.println(comment1);
        }
        Comment comment1 = commentRepository.findByComment("3 대 500 인 사람 댓글 달아봐").get();
        Assertions.assertThat(comment1.getRight()).isEqualTo(14);
    }

    @Test
    void selectSpecificLayer() throws Exception{
        for (int i = 0; i < 3; i++) {
            List<Comment> byLayer = commentQuery.findByLayer(i);
            System.out.println("========= " + i + " ============");
            for (Comment comment : byLayer) {
                System.out.println(comment);
            }
        }
    }

    @Test
    void getAllChildByComment() throws Exception{
        //2번째 레이어 2개의 댓글 에 한개의 대댓글
        Comment comment = commentRepository.findByComment("3대 520 언더아머 회원임").get();
        List<Comment> allCommentFromComment = commentQuery.getAllCommentFromComment(comment);
        Assertions.assertThat(allCommentFromComment.size()).isEqualTo(3);
        for (Comment comment1 : allCommentFromComment) {
            System.out.println(comment1);
        }
    }
}

CommentQuery 클래스 

package com.example.dowhateveriwant.repository.commet;

import com.example.dowhateveriwant.entity.Comment;
import com.querydsl.core.types.dsl.CaseBuilder;
import com.querydsl.core.types.dsl.NumberExpression;
import com.querydsl.jpa.impl.JPAQueryFactory;
import org.springframework.stereotype.Repository;

import javax.persistence.EntityManager;
import java.util.List;

import static com.example.dowhateveriwant.entity.QComment.comment1;


@Repository
public class CommentQuery {
    private JPAQueryFactory queryFactory;
    private CommentRepository commentRepository;

    public CommentQuery(EntityManager em,CommentRepository cm) {
        this.queryFactory = new JPAQueryFactory(em);
        this.commentRepository = cm;
    }

    public void insertComment(Comment parents, String comment){

        insertUpdateLeftRight(parents.getRight());
        // 데이터 인설트
        commentRepository.save(Comment.builder()
                        .left(parents.getRight())
                        .right(parents.getRight() + 1)
                        .level(parents.getLevel() + 1)
                        .comment(comment).build()
        );
    }
    public void insertUpdateLeftRight(int target){
        queryFactory.update(comment1)
                .set(comment1.left, getLeftCaseBuilder(target))
                .set(comment1.right,comment1.right.add(2))
                .where(comment1.right.goe(target))
                .execute();
    }
    public void insertBetween(Comment head,Comment tail,String comment){
        queryFactory.update(comment1)
                .set(comment1.left, comment1.left.add(1))
                .set(comment1.right, comment1.right.add(1))
                .set(comment1.level, comment1.level.add(1))
                .where(comment1.left.goe(tail.getLeft()),
                        comment1.right.loe(tail.getRight()))
                .execute();

        queryFactory.update(comment1)
                .set(comment1.left,getLeftCaseBuilderWithoutRoot(tail.getLeft()))
                .set(comment1.right,comment1.right.add(2))
                .where(comment1.right.gt(tail.getRight()),
                        comment1.ne(tail))
                .execute();

        commentRepository.save(Comment.builder()
                .left(head.getLeft()+1)
                .right(tail.getRight()+2)
                .level(head.getLevel() + 1)
                .comment(comment).build());
    }

    public List<Comment> findByLayer(int level){
        return queryFactory.selectFrom(comment1)
                .where(comment1.level.eq(level))
                .fetch();
    }

    public List<Comment> getAllCommentFromComment(Comment comment){
        return queryFactory.selectFrom(comment1)
                .where(comment1.left.gt(comment.getLeft()),
                        comment1.right.lt(comment.getRight()))
                .fetch();
    }

    public void deleteComment(Comment comment){
        queryFactory.update(comment1)
                .set(comment1.left, subTractWithoutLeftRoot(comment.getLeft()))
                .set(comment1.right, comment1.right.subtract(2))
                .where(comment1.right.gt(comment.getRight()))
                .execute();

        queryFactory.update(comment1)
                .set(comment1.left, comment1.left.subtract(1))
                .set(comment1.right, comment1.right.subtract(1))
                .set(comment1.level, comment1.level.subtract(1))
                .where(comment1.left.gt(comment.getLeft()),
                        comment1.right.lt(comment.getRight()))
                .execute();


        queryFactory.delete(comment1).where(comment1.eq(comment)).execute();
    }
    private NumberExpression<Integer> subTractWithoutLeftRoot(int target) {
        return new CaseBuilder()
                .when(comment1.left.gt(target))
                .then(comment1.left.subtract(2))
                .otherwise(comment1.left);
    }

    private NumberExpression<Integer> getLeftCaseBuilderWithoutRoot(int target) {
        return new CaseBuilder()
                .when(comment1.left.gt(target))
                .then(comment1.left.add(2))
                .otherwise(comment1.left);
    }

    private NumberExpression<Integer> getLeftCaseBuilder(int target) {
        return new CaseBuilder()
                .when(comment1.left.goe(target))
                .then(comment1.left.add(2))
                .otherwise(comment1.left);
    }
}

 

현재까지 인접노드, 열거형 모델, 클로저 테이블, 중첩모델을 알아봤다. 

인접목록 => 자식조회가 쉽고, 구현이 쉽다. 삽입과 삭제 가 쉽지만 트리를 조회하는 데 있어 문제점이 발생했다

 

그래서 제안된 방법이 열거형 클로저 중첩모델이다.

 

열거형 => 인접목록의 트리 조회를 쉽게 할 수 있었다. 다만 참조의 정합성 문제가 발생했다. 없는 노드 도 열거형에 넣을 수 있으며 얼마나 깊은 계층까지 만들어야 하는가 에 매번 신경을 써야 하는 단점이 존재했다.

 

클로저 => 두 개의 테이블을 운용해 트리의 모든 경로를 기록하기 때문에 조회가 무척 쉬웠다. 심지어 열거형, 중첩 모델의 문제인 참조의 정합성 문제도 해결해주는 완벽한 듯해 보였으나. 계층 구조를 사용하는 데 있어 많은 저장공간을 사용하는 아쉬운 점이 존재한다.

 

중첩 => 노드 의 좌우측 번호를 매겨 트리의 계층을 유지하는 모델이다. 트리를 수정하고 데이터를 집어넣는 경우 매우 효과적이지 못하다는 것을 코드를 구현하면서도 느낀다. 반면 조회에 있어서 만큼의 편리함은 이루 말할 수 없다. 

 

각각의 장단점이 존재한다. 가장 주가 되는 기준을 정하고 그 기준에 부합하는 모델을 사용하면 된다고 생각한다. 개인적으로 모든 모델을 구현하면서 중첩 모델이 가장 어려웠다.