댓글 알고리즘 - 중첩집합(1)

지난번 포스팅에서는 경로 열거 방식 알고리즘을 적용해서 댓글을 구현해 봤습니다.

 

경로 열거 방식이 궁금하다면 - [Algorithm] 경로 열거 방식

댓글 알고리즘 - 경로열거(Path Enumeration)

 

경로 열거 방식에서는 경로 값의 무결성과 정합성을 보장할 수 없다는 점과, 결국 문자열로 경로를 저장하기 때문에

경로의 깊이 자체에도 한계가 있다는 단점이 있었습니다.

 

중첩 집합은 각 노드가 자신의 부모를 저장하는 대신 자기 자손에 집합에 대한 정보를 저장합니다.

이 정보는 트리의 각 노드를 두 개의 수로 부호화(ENCODE) 해서 나타낼 수 있는데,

여기서는 nsleft와 nsright로 쓰겠습니다. 또한 트리 순회 방식은 전위 순회(PREORDER) 방식을 사용합니다.

전위 순회 방식을 사용하여 부모 노드와 자식 노드를 구분하면서 nsleft, nsright 값을 늘려주는 구조입니다.

 

중첩집합 댓글 트리

CREATE TABLE dbo.COMMENT_TEST_NESTED 
( 
	comment_id		bigint not null, 
	nsleft			int not null, 
	nsright			int not null, 
	comment			nvarchar(500) not null, 
	comment_date		datetime not null, 
	author			varchar(20) not null 
) 
ALTER TABLE dbo.COMMENT_TEST_NESTED ADD CONSTRAINT PK__COMMENT_TEST_NESTED__COMMENT_ID PRIMARY KEY (comment_id)

INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (1,1,14,N'데이터베이스 어려운가요?',getdate(),'ssh9308'); 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (2,2,5,N'열심히 공부하시면 어렵지 않을겁니다!',getdate(),'kyj9787') 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (3,3,4,N'친절한 답변 감사합니다!',getdate(),'ssh9308') 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (4,6,13,N'SQL 안티패턴 책을 한번 봐보세요',getdate(),'korea1993') 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (5,7,8,N'어려운 내용은 아닐까요?',getdate(),'mansae4433') 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (6,9,12,N'그책은 입문서로는 좀 어렵지 않을까요?',getdate(),'respond9977') 
INSERT INTO dbo.COMMENT_TEST_NESTED VALUES (7,10,11,N'입문서로는 좀 어려울수 있겠군요 ㅜ',getdate(),'youngboys123')

SELECT * FROM dbo.COMMENT_TEST_NESTED WITH(NOLOCK)

댓글구조

해당 알고리즘을 수학적으로 간단하게 풀어보자면 아래와 같습니다.

COMMENT_TEST_NESTED 테이블을 T라고 부르도록 합시다. 그리고 테이블 안에 있는 각 노드를 N이라고 부르면
특정한 노드 Nx에 대해서 Nx의 부모는 아래의 식을 만족합니다.
Parents Of Nx = ∀N ∈ (N.nsleft < Nx.nsleft  ^ N.nsright > Nx.nsleft)

위의 논리를 SQL where 문에 필터링 조건으로 쓰자면 다음과 같습니다.

where Nx.nsleft between N.nsleft and N.nsright

 

즉, 조인 조건을 통해서 자신의 nsleft 값과 다른 노드의 nsleft값, nsright 값을 비교하여 자신의 nsleft 값이 해당 노드의 nsleft와  nsrighrt 값 사이에 있다면 해당 노드의 자식 중 하나라고 생각해주면 됩니다.

 

그럼 자연스럽게 특정한 노드 Nx에 대해서 Nx의 자식은 아래의 식을 만족합니다.

Descendants Of Nx = ∀N ∈ (N.nsleft > Nx.nsleft  ^ N.nsleft < Nx.nsright)

위의 논리를 SQL where 문에 필터링 조건으로 쓰자면 다음과 같습니다.

where N.nsleft between Nx.nsleft and Nx.nsright

 

 

 

예를 들어 #4의 자식 답글을 찾는 쿼리는 아래와 같습니다.

SELECT c2.* FROM dbo.COMMENT_TEST_NESTED c1 WITH(NOLOCK)
INNER JOIN dbo.COMMENT_TEST_NESTED c2 WITH(NOLOCK) ON c2.nsleft BETWEEN c1.nsleft AND c1.nsright
WHERE c1.comment_id = 4 AND c2.comment_id != 4

#4의 자식노드(= 댓글에 대한 답글)

#4의 자식노드(답글들)

 

위의 논리대로 이번에는 #5의 부모 노드를 조회하는 쿼리를 작성해보면 아래와 같습니다.

SELECT c2.* FROM dbo.COMMENT_TEST_NESTED c1 WITH(NOLOCK)
INNER JOIN dbo.COMMENT_TEST_NESTED c2 WITH(NOLOCK) ON c1.nsleft BETWEEN c2.nsleft AND c2.nsright
WHERE c1.comment_id = 5 AND c2.comment_id != 5

#5의 부모노드

#5의 부모노드

 

해당 구조에서 기존 댓글에 대한 답글을 삭제할 때, 어떤 일이 발생하는지는

다음 포스팅에서 설명하도록 하겠습니다. :)