[Spring + MyBatis + Oracle] 그래프 탐색(BFS, DFS)를 활용한 무한 계층형 댓글 구현

1. 요구사항

1. 댓글/대댓글 CRUD 기능
   • 댓글을 생성, 수성, 삭제할 수 있어야 함
   • 댓글 삭제 시 하위에 있는 모든 대댓글은 함께 삭제
2. 계층형 댓글 구조
   • 댓글을 계층 구조로 표현하며, 대댓글이 해당 댓글에 속하도록 구현
   • 출력된 목록은 사용자가 쉽게 읽을 수 있도록 표현
3. SQL 사용 최소화
   • 댓글 목록을 조회, 삭제할 때 SQL 쿼리 실행 횟수를 최소화
   • 중복된 쿼리를 피하고 필요한 데이터만을 조회하는 방식을 고려
4. 그래프 탐색 시 O(n)으로 동작하도록 코드 구현
   • 댓글 목록을 계층 구조로 탐색할 때 시간 복잡도가 O(n) 이하여야 함
   • 효율적인 자료구조나 알고리즘을 사용하여 계층 구조를 효율적으로 관리

 

2. 사용 기술 스택

• Java
• Spring5
• MyBatis
• Oracle

 

3. 데이터베이스 설계

Table 구조

주요 Column

• 댓글 번호(reply_id) : Sequence를 활용해 순차적으로 증가
• 그룹 번호(group_id) : Root의 댓글 번호(Roort는 댓글 그룹에 가장 상단에 있는 댓글)
• 부모 번호(parent_id) : 부모 댓글의 댓글 번호
• 깊이(Depth) : tree 구조에서의 depth(댓글 출력 시 들여 쓰기에 사용)

 

4. 자료구조

인접리스트를 활용하여 Tree 구조를 구현하였고, BFS/DFS를 활용해 해당 Tree를 순회하는 로직을 구현했습니다.

Map<Integer, List<Integer>> adjlist = new HashMap<>(); // 인접 리스트

해당 인접리스트는 단방향 인접리스트로 부모 → 자식 방향의 간선만 추가하도록 구현했습니다.

 

5. 주요 로직

1) 댓글 목록 

댓글 목록 요청 Sequence Diagram

먼저 정렬 로직을 수행하기 전에 SQL 쿼리를 한번 수행하여 해당 스터디의 모든 댓글 리스트를 들고 와야 합니다. 이때 group_id, parent_id, reply_id 순서대로 정렬하여 추출하게 되면 Tree 구조의 자식들이 시간순서대로 정렬됩니다.

SELECT S.*,
       TO_CHAR(S.REGDATE, 'yyyy-MM-dd HH24:MI')                                 AS DBDAY,
       (SELECT SR.NICKNAME FROM STUDY_REPLY SR WHERE SR.REPLY_ID = S.PARENT_ID) AS PARENT_NICKNAME
FROM STUDY_REPLY S
WHERE S.STUDY_ID = #{study_id}
ORDER BY GROUP_ID, PARENT_ID, REPLY_ID

DFS 순회 결과와 해당 결과를 토대로 출력한 댓글의 모습

DFS를 수행하기 위해 먼저 SQL을 통해 추출한 데이터를 인접리스트 형태로 만들어야 합니다. 해당 인접리스트에는 부모 -> 자식으로 향하는 간선만 추가하면 DFS, BFS로 순회를 할 때 Tree 구조가 보장되기 때문에 O(n)의 시간복잡도를 가집니다. Service 단에서 구현한 코드는 아래와 같습니다. 

@Override
public List<ReplyVO> getReplyList(int study_id) {
	List<ReplyVO> list = dao.getReplyList(study_id); // repository에서 가져온 댓글 목록

	// 아이디 보호
	markUserId(list);

	// 자료구조 생성 (댓글 HashMap, root 리스트, 인접리스트 생성)
	Map<Integer, ReplyVO> replyMap = new HashMap<>(); // 댓글 HashMap
	Map<Integer, List<Integer>> adjlist = new HashMap<>(); // 인접 리스트
	List<Integer> roots = new ArrayList<>(); // root 리스트

	for(ReplyVO vo : list){
		adjlist.put(vo.getReply_id(), new ArrayList<>());
		replyMap.put(vo.getReply_id(), vo);
	}
	for(ReplyVO vo : list){
		if(vo.getReply_id() == vo.getParent_id()){
			roots.add(vo.getReply_id());
		}
		else{
			adjlist.get(vo.getParent_id()).add(vo.getReply_id());
		}
	}

	// root를 기준으로 dfs 수행
	List<ReplyVO> retval = new ArrayList<>();
	for(int root : roots){
		List<Integer> ordered = new ArrayList<>();
		dfs(root, ordered, adjlist);
		for(int i : ordered){
			retval.add(replyMap.get(i));
		}
	}

	return retval;
}
	// dfs 수행 하면서 방문 수행
	void dfs(int cur, List<Integer> ordered, Map<Integer, List<Integer>> adjlist){
		ordered.add(cur);
		for(int child : adjlist.get(cur)){
			dfs(child, ordered, adjlist);
		}
	}

3) 댓글 삽입

댓글 삽입의 경우엔 루트 댓글, 대댓글 2가지 종류가 있습니다. 삽입의 경우 따로 Java로직이 필요하진 않고 단일 SQL만 실행하여 구현할 수 있습니다. 

/* 루트 댓글 삽입 */
INSERT INTO STUDY_REPLY
VALUES (
    STUDY_REPLY_SEQ.nextval,
    #{study_id},
    #{user_id},
    #{nickname},
    #{msg},
    SYSDATE,
    STUDY_REPLY_SEQ.currval, /* 그룹 번호 */
    STUDY_REPLY_SEQ.currval, /* 부모 번호 */
    0 /* depth */
)

루트 댓글의 경우엔 부모가 없기 때문에 그룹 번호와 부모 번호를 자기 자신으로 설정했습니다. 또한, Depth는 Root이기 때문에 0으로 설정했습니다.

/* 대댓글 삽입 */
INSERT INTO STUDY_REPLY
VALUES (
    STUDY_REPLY_SEQ.nextval,
    #{study_id},
    #{user_id},
    #{nickname},
    #{msg},
    SYSDATE,
    (SELECT GROUP_ID FROM STUDY_REPLY WHERE REPLY_ID = #{parent_id}), /* 그룹 번호 */
    #{parent_id}, /* 부모 번호 */
    (SELECT DEPT FROM STUDY_REPLY WHERE REPLY_ID = #{parent_id}) + 1 /* depth */
)

대댓글의 경우엔 대댓글을 작성하고자 하는 댓글의 그룹번호, 부모번호를 참조하여 설정하였고, depth 또한 부모의 depth에  1을 더하여 저장했습니다.

 

3) 댓글 삭제

댓글 삭제 Sequence Diagram

삭제의 경우 하위 댓글을 전부 삭제해야 하기 때문에 삭제할 댓글을 추출하는 것과 여러 개의 댓글을 삭제하는 SQL을 어떻게 한 번에 삭제할지가 중요한 과제였습니다.

 

먼저 삭제할 댓글의 하위 댓글을 추출하기 위해 해당 댓글과 같은 Group인 댓글의 목록을 Select 하는 SQL 쿼리를 수행했습니다.

/* 같은 그룹 SELECT */
SELECT REPLY_ID, PARENT_ID
FROM STUDY_REPLY
WHERE GROUP_ID = (SELECT GROUP_ID FROM STUDY_REPLY WHERE REPLY_ID = #{reply_id})

Group 전체를 인접리스트로 만든 다음 삭제할 댓글가 root인 Subtree를 구하기 위해 BFS를 수행했습니다. 

2번 댓글 기준 BFS 순회 결과

@Override
public int deleteReply(int reply_id){
	List<ReplyVO> group = dao.getReplyBySameGroup(reply_id);

	// 자료구조 생성(연결리스트, BFS 용 Queue, 삭제할 목록)
	Map<Integer, List<Integer>> adjlist = new HashMap<>(); // 연결리스트
	Queue<Integer> queue = new ArrayDeque<>(); // BFS용 Queue
	List<Integer> deleteList = new ArrayList<>(); // 하위 댓글 목록
	for(ReplyVO vo : group){
		int rid = vo.getReply_id();
		int pid = vo.getParent_id();

		if(rid == pid){
			continue;
		}
		else if(!adjlist.containsKey(pid)){
			adjlist.put(pid, new ArrayList<>());
		}
		adjlist.get(pid).add(rid);
	}

	// BFS 수행(하위 댓글 추출)
	queue.add(reply_id);
	while(!queue.isEmpty()){
		int cur = queue.poll();
		deleteList.add(cur);
		if(adjlist.containsKey(cur)){
			for(int next : adjlist.get(cur)){
				queue.add(next);
			}
		}
	}

	return dao.deleteReplys(deleteList);
}

삭제할 댓글의 목록이 여러 개면 해당 댓글을 삭제하기 위해 SQL을 댓글 개수만큼 수행해야 할까요?

MyBatis에는 이러한 문제를 해결하기 위해 동적쿼리를 제공합니다. 아래는 동적쿼리를 활용해 여러 개의 Row를 동시에 삭제하는 SQL입니다. 

/* 하위 댓글 삭제 동적 쿼리 */
<delete id="deleteReplys" parameterType="java.util.List">
    DELETE FROM STUDY_REPLY
    WHERE REPLY_ID IN
    <foreach collection="list" open="(" separator="," close=")" item="item">
        #{item}
    </foreach>
</delete>

 

6. 구현 결과

계층형 댓글 출력 결과