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

지난번 포스팅에서는 "인접 목록 방식" 알고리즘을 적용해서 댓글을 구현해 봤습니다.

인접 목록 방식이 궁금하다면 - [Algorithm] 인접 목록 방식

 

인접 목록의 약점 중 하나는 트리에서 주어진 노드의 조상들을 얻는 데 비용이 많이 든다는 것입니다.

경로 열거 방법에서는 일련의 조상을 각 노드의 속성으로 저장해 이를 해결합니다.

디렉터리 구조와 비슷한데 /user/local/test/ 와 같은 unix 경로와 비슷하다고 생각하면 됩니다.

 

CREATE TABLE dbo.COMMENT_TEST_PATH 
( 
	comment_id		bigint not null,	
	path			varchar(1000) null,	-- 경로를 저장해줄것 
	comment			nvarchar(500) not null, 
	comment_date		datetime not null, 
	author			varchar(20) not null 
)

ALTER TABLE dbo.COMMENT_TEST_PATH ADD CONSTRAINT PK__COMMENT_TEST_PATH__COMMENT_ID PRIMARY KEY (comment_id)

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

 

parent_id  칼럼을 추가하는 대신 긴  varchar type의 path란 컬럼을 정의합니다.

이 컬럼에 저장되는 문자열은 트리의 꼭대기부터 현재 행까지 내려오는 조상의 나열로, 디렉터리 경로와 비슷합니다.

경로 열거 방식

 

 

만약 1/2/ 하위 답글을 보고 싶으면 아래와 같이 쿼리 하면 됩니다.

SELECT * FROM dbo.COMMENT_TEST_PATH WITH(NOLOCK)
WHERE path LIKE '1/2/%/'

1/2/ 하위 댓글 결과

 

 

또한, 경로열거형 알고리즘을 사용하면 인접 목록 방식을 사용할 때보다 집계 함수를 사용하는 데에도 제약이 없습니다.

예를 들어, 첫 번째 댓글에 총 몇 개의 답글이 달렸는지 조회하고 싶으면 아래와 같이 쿼리 하면 됩니다.

SELECT 
	COUNT(*) AS cnt 
FROM dbo.COMMENT_TEST_PATH WITH(NOLOCK)
WHERE path LIKE '1/%' AND comment_id != 1

집계함수 결과

 

 

새로운 노드를 삽입하고 싶을 때는 INSERT 구문에 경로와 내용을 직접 넣어주면 됩니다.

1/4/ 답글에 대한 답글을 추가해준다고 가정해 봅시다.

새로운 답글 추가

INSERT INTO dbo.COMMENT_TEST_PATH 
(
	comment_id
,	path
,	comment
,	comment_date
,	author
)
VALUES
(
	8
,	'1/4/8/'
,	N'추천 감사합니다.'
,	GETDATE()
,	'kimisangkoong'
)

--1/4/의 하위댓글 모두 조회
SELECT * FROM dbo.COMMENT_TEST_PATH WITH(NOLOCK)
WHERE path LIKE '1/4/%/'

새로운 노드 추가

부모 디렉토리가 1/4/이고 마지막 노드의 번호를 7까지 사용했으니 1/4/8/ 로 디렉터리 경로를 지정해주면 위와 같이

자신의 부모 노드 아래에 댓글이 들어가는 것을 알 수 있습니다.

 

 

하지만, 경로 열거 방법도 단점이 있습니다.

일단, 데이터베이스는 경로가 올바르게 형성되도록 하거나 경로 값이 실제 노드에 대응되도록 강제하기가 어렵습니다.  
결국 문자열을 유지하는 것은 애플리케이션 코드에 종속되며, 이를 검증하는 데는 비용이 많이 든다고 볼 수 있습니다.

VARCHAR 칼럼의 길이를 아무리 길게 잡아도 결국 제한이 있기 때문에, 엄격히 말하면 지원할 수 있는 트리의 깊이

또한 제한됩니다.(디렉터리가 얼마나 깊어질지 알 수 없으므로)

 

이러한 문제를 해결하기 위해 중첩 집합 알고리즘이 존재합니다.

다음 포스팅에서는 중첩 집합 알고리즘을 댓글 구현에서 어떤 식으로 사용하는지 알아봅시다. :)

 

 

 

 

중첩집합 알고리즘이 궁금하다면 - [Algorithm] 중첩 집합(1)