알고리즘

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

ssh9308 2021. 7. 22. 17:04
반응형

지난번 포스팅에서는 중첩 집합 방식 알고리즘을 적용한 댓글 구조에서 답글을 어떤 식으로 삭제하는지 알아봤습니다.

 

중첩 집합 방식에 대한 설명(삭제) - [Algorithm] 중첩 집합(2)

 

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

지난번 포스팅에서는 기본적으로 중첩 집합 방식 알고리즘이 어떤 식으로 작동하는지에 대해 알아봤습니다. 중첩 집합 방식에 대한 설명 - [Algorithm] 중첩 집합(1) 이번 포스팅에서는 중첩 집합

goodbyeanma.tistory.com

 

이번 포스팅에서는 새로운 답변을 생성하는 경우 어떠한 구조로 로직을 생성해야 하는지 알아보겠습니다.

답글 추가 트리

예를 들어 #2에 대한 새로운 답변(#32)을 추가해봅시다. 그럼 위 그림과 같은 트리 형식이 될 것입니다. 

일단 새로운 답글 #32은 #2의 자식 노드로 들어가고 #3의 형제 노드로 들어갈 것입니다.

즉, #3의 nsright값보다 1 큰값을 nsleft 값으로 가질 것이며, nsright 값은 nsleft 값보다 1 큰 값을 가질 것입니다. 

새로운 댓글 #32을 기준으로 부모노드의 nsright는 +2가 될 것이고, 해당 노드보다 오른쪽 노드들의 nsleft, nsright 값은 모두 기존 값들보다 2만큼 커질 것입니다.

UPDATE dbo.COMMENT_TEST_NESTED 
SET nsleft = CASE WHEN nsleft > 4 THEN nsleft + 2 ELSE nsleft END 
,   nsright += 2 
WHERE nsright > 4 


INSERT INTO dbo.COMMENT_TEST_NESTED 
( 
	nsleft 
,	nsright 
,	comment 
,	comment_date 
,	author 
) 
VALUES 
( 
	5 
,	6 
,	N'공부 열심히 하셨나봐요 ~' 
,	GETDATE() 
,	'shambala3421' 
)


-- #32의 상위노드의 정보를 조회
SELECT 
	parent.* 
FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft and parent.nsright 
WHERE me.comment_id = 32 AND parent.comment_id != 32

 

#32의 상위노드 조회 결과

 

 

 

그럼 위의 결과를 이제 일반화하여 Stored Procedure 형태로 만들어본다면 아래와 같습니다.

CREATE PROC dbo.add_comment_test_nested 
	@parent_id bigint	-- 부모노드의 아이디
,	@comment nvarchar(500)	-- 답글 내용
,	@author varchar(20)	-- 작성자
AS 
SET NOCOUNT ON 
SET TRANSACTION ISOLATION LEVEL READ UNCOMMITTED 
BEGIN

    	DECLARE @last_sibling INT -- 마지막 자식 노드의 comment_id 
	,	@last_nsright INT -- 마지막 자식 노드의 nsright 값
	,	@descendants_yn CHAR(1) -- 자손의 여부
        
		--자식노드가 있는지 판단
		IF EXISTS (SELECT *
                   		FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
				INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
                   	  WHERE parent.comment_id = @parent_id and me.comment_id != @parent_id)
		BEGIN
			SET @descendants_yn = 'Y'
		END
		ELSE
		BEGIN
			SET @descendants_yn = 'N'
		END


		IF (@descendants_yn = 'Y')--자식노드가 있는 경우
		BEGIN
			--마지막 자식 노드의 right 값과 comment_id 값을 찾아준다.
			SELECT 
				@last_sibling = comment_id --3
			,	@last_nsright = nsright --4
			FROM dbo.COMMENT_TEST_NESTED WITH(NOLOCK) 
			WHERE nsright = (SELECT 
				           	max(me.nsright) 
                			FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
                			INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
                			WHERE parent.comment_id = @parent_id AND me.comment_id != @parent_id)
		
			
                
				UPDATE dbo.COMMENT_TEST_NESTED 
				SET nsleft = CASE WHEN nsleft > @last_nsright THEN nsleft + 2 ELSE nsleft END 
				,   nsright += 2 
				WHERE nsright > @last_nsright
                
		
				INSERT INTO dbo.COMMENT_TEST_NESTED 
				( 
					nsleft 
				,	nsright 
				,	comment 
				,	comment_date 
				,	author 
				)	 
				VALUES	 
				( 
					@last_nsright + 1
				,	@last_nsright + 2 
				,	@comment 
				,	GETDATE() 
				,	@author 
				) 
	
			
		END
		ELSE--자식노드가 없는경우
		BEGIN
			DECLARE @parent_right	INT
			
			SELECT 
				@parent_right = nsright
			FROM dbo.COMMENT_TEST_NESTED WITH(NOLOCK)
			WHERE comment_id = @parent_id

			UPDATE dbo.COMMENT_TEST_NESTED 
			SET nsleft = CASE WHEN nsleft > @parent_right THEN nsleft + 2 ELSE nsleft END 
			,   nsright += 2 
			WHERE nsright >= @parent_right

			INSERT INTO dbo.COMMENT_TEST_NESTED 
			( 
				nsleft 
			,	nsright 
			,	comment 
			,	comment_date 
			,	author 
			)	 
			VALUES	 
			( 
				@parent_right 
			,	@parent_right + 1 
			,	@comment 
			,	GETDATE() 
			,	@author 
			) 
		END


		IF @@ERROR <> 0 
			ROLLBACK TRAN 
END

 

 

코드 분석을 시작해봅시다.

1. 자신이 댓글을 다려고 하는 댓글노드에 자식이 존재하는지 체크해줍니다.

    	DECLARE @last_sibling INT -- 마지막 자식 노드의 comment_id 
	,	@last_nsright INT -- 마지막 자식 노드의 nsright 값
	,	@descendants_yn CHAR(1) -- 자손의 여부
        
		--자식노드가 있는지 판단
		IF EXISTS (SELECT *
                   		FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
				INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
                   	  WHERE parent.comment_id = @parent_id and me.comment_id != @parent_id)
		BEGIN
			SET @descendants_yn = 'Y'
		END
		ELSE
		BEGIN
			SET @descendants_yn = 'N'
		END

 

 

 

예를 들어 parent.comment_id를 #2로 지정하면 자식 노드가 있으므로 아래와 같이 결과가 나오게 된다.

즉, exists 조건에 걸려 @descendants_yn = 'Y'가 된다.

SELECT *
FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
WHERE parent.comment_id = 2 and me.comment_id != 2

parent 가 #2 인 경우

 

 

하지만, parent.comment_id  를 #3으로 지정하면 자식 노드가 없으므로 exists 조건에 걸리지 않아

@descendants_yn = 'N' 가 된다.

SELECT *
FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
WHERE parent.comment_id = 3 and me.comment_id != 3

parent 가 #3 인 경우

 

 

2. 자식노드가 있는 경우의 처리

--마지막 자식 노드의 right 값과 comment_id 값을 찾아준다.
SELECT 
	@last_sibling = comment_id --3
,	@last_nsright = nsright --4
FROM dbo.COMMENT_TEST_NESTED WITH(NOLOCK) 
WHERE nsright = (SELECT 
			max(me.nsright) 
                 FROM dbo.COMMENT_TEST_NESTED me WITH(NOLOCK) 
                 INNER JOIN dbo.COMMENT_TEST_NESTED parent WITH(NOLOCK) ON me.nsleft BETWEEN parent.nsleft AND parent.nsright 
                 WHERE parent.comment_id = @parent_id AND me.comment_id != @parent_id) --(*1)
		
BEGIN TRAN
                
    	--(*2)
	UPDATE dbo.COMMENT_TEST_NESTED 
	SET nsleft = CASE WHEN nsleft > @last_nsright THEN nsleft + 2 ELSE nsleft END 
	,   nsright += 2 
	WHERE nsright > @last_nsright
                
	--(*3)	
	INSERT INTO dbo.COMMENT_TEST_NESTED 
	( 
		nsleft 
	,	nsright 
	,	comment 
	,	comment_date 
	,	author 
	)	 
	VALUES	 
	( 
		@last_nsright + 1
	,	@last_nsright + 2 
	,	@comment 
	,	GETDATE() 
	,	@author 
	) 

COMMIT TRAN

 

(*1) 번을 보게되면, nsright를 max 값으로 받은 이유는 하나의 댓글 노드에 이전 가장 마지막 댓글 노드 오른쪽으로 

새로운 댓글노드를 추가해줄 것이기 때문이다.

 

(*2), (*3) 번은 위에서 설명한 새로운 답변 생성에 대한 로직이다.

 

 

3. 자식노드가 없는 경우의 처리

			DECLARE @parent_right	INT
			
			SELECT 
				@parent_right = nsright
			FROM dbo.COMMENT_TEST_NESTED WITH(NOLOCK)
			WHERE comment_id = @parent_id

			UPDATE dbo.COMMENT_TEST_NESTED 
			SET nsleft = CASE WHEN nsleft > @parent_right THEN nsleft + 2 ELSE nsleft END 
			,   nsright += 2 
			WHERE nsright >= @parent_right

			INSERT INTO dbo.COMMENT_TEST_NESTED 
			( 
				nsleft 
			,	nsright 
			,	comment 
			,	comment_date 
			,	author 
			)	 
			VALUES	 
			( 
				@parent_right 
			,	@parent_right + 1 
			,	@comment 
			,	GETDATE() 
			,	@author 
			)

자식노드가 없는경우 처리

 

원래 #3의 left 값이 4였지만 자식 노드가 새롭게 추가되면서 자식 노드의 left 값에 자신의 right 값을 준다.

그리고 자식노드의 right = left + 1 이 성립한다. 자연스럽게 그렇게 되면 자신을 품고 있는 상위 노드나

오른쪽에 있는 노드들의 left, right 값은 자연스럽게 2씩 늘어나게 된다.

 

 

 

 

 

 

반응형