계층형 게시판 알고리즘 ( 댓글 알고리즘 )

계층형 게시판( 댓글이 있는 )의 구조와 알고리즘에 대해서 알아보자.

설명을 위해 테이블에는 다음과 같은 컬럼들만 있다고 가정한다.

이해를 돕기 위해 수행되는 쿼리와 수행후 테이블의 row를 그려 넣었다. 

no : 글번호(Primary Key)

title : 글제목

grp : 같은 주제를 갖는 게시물의 고유번호. 

       부모글과 부모글로부터 파생된 모든 자식글은 같은 번호를 갖는다.

seq : 같은 그룹내 게시물의 순서

lvl : 같은 그룹내 계층

[MySQL 관련 명령어]

alter table board auto_increment = 1; 

-- 자동증가값 사용시 최초값 셋팅
 

set last_insert_id = 0;

-- 마지막으로 사용된 auto_increment 값 초기화

select last_insert_id() 

-- 마지막으로 사용된 auto_increment 값 반환

예제)

1) 게시판에 첫번째 글이 올라 올때

  

insert into board( title, grp, seq, lvl ) 

values('안녕하세요', (select last_insert_id()+1), 1, 0);

no	title	grp	seq	lvl
1	안녕하세요	1	1	1

새글(글 등록)의 경우,
no 는 AutoIncrement 로부터 받아온 값
grp는 no와 동일한 값 
seq는 1
lvl은 0 이된다.


2) 두번째, 세번째 글이 올라올때

insert into board( title, grp, seq, lvl ) 

values('날씨가 맑습니다', (select last_insert_id()+1), 1, 0);

no	title	grp	seq	lvl
1	안녕하세요	1	1	0
2	날씨가 맑습니다	2	1	0
3	모임이 있습니다	3	1	0

3) 첫번째 글에 댓글이 올라올때

update board

set seq = seq + 1

where grp = 1

and seq > 1;

insert into board( title, grp, seq, lvl ) 

values('반가워요', 1, 1+1, 0+1);

no	title	grp	seq	lvl
1	안녕하세요	1	1	0
2	날씨가 맑습니다	2	1	0
3	모임이 있습니다	3	1	0
4	반가워요	1	2	1

 댓글의 경우, ( 부모글 : '댓글이 달린 바로 상위글' 원본글일수도 있고 댓글일 수도 있음 )

grp 는 부모글의 grp 값

seq 는 부모글의 seq+1

lvl 은 부모글의 lvl+1 이 된다.

댓글을 삽입하기 이전에
한 글에 대한 댓글이 여러개인 경우 우선순위를 맞춰주기 위해서 

부모글과 동일한 그룹 번호에 있으면서 

부모글의 seq 번호보다 큰 게시물의 seq 번호를 모두 1만큼 증가시킨다

4) 첫번째 글의 댓글에 댓글이 올라올때 

(즉, 네번째 글의 댓글이 댓글이 삽입된 후)

update board

set seq = seq + 1

where grp = 1

and seq > 2;

insert into board( title, grp, seq, lvl ) 

values('감사합니다', 1, 2+1, 1+1);

no	title	grp	seq	lvl
1	안녕하세요	1	1	0
2	날씨가 맑습니다	2	1	0
3	모임이 있습니다	3	1	0
4	반가워요	1	2	1

5

감사합니다

1

3

2

5) 첫번째 글의 두번째 댓글이 올라올때

update board

set seq = seq + 1

where grp = 1

and seq > 1;

insert into board( title, grp, seq, lvl ) 

values('감사합니다', 1, 1+1, 0+1);

no	title	grp	seq	lvl
1	안녕하세요	1	1	0
2	날씨가 맑습니다	2	1	0
3	모임이 있습니다	3	1	0
4	반가워요	1	3	1

5

감사합니다

1

4

2

6

환영합니다

1

2

1

6) 여섯번째 게시물에 댓글이 올라올때

update board

set seq = seq + 1

where grp = 1

and seq > 2;

insert into board( title, grp, seq, lvl ) 

values('감사합니다', 1, 2+1, 1+1);

no	title	grp	seq	lvl
1	안녕하세요	1	1	0
2	날씨가 맑습니다	2	1	0
3	모임이 있습니다	3	1	0
4	반가워요	1	4	1

5

감사합니다

1

5

2

6

환영합니다

1

2

1

7

감사합니다

1

3

2

검색(select) 할 때는 grp를 내림차순으로

seq를 오름차 순으로 정렬하면 된다. 

인덱스는 기본키와 grp+seq의 복합 인덱스를 설정하면 된다.

select * from board order by grp desc, seq asc;

[검색결과]

no title     grp seq lvl

--------------------------------------------

3 모임이 있습니다 3 1 0

2 날씨가 맑습니다 2 1 0

1 안녕하세요 1 1 0

6 환영합니다 1 2 1

7 감사합니다 1 3 2

4 반가워요        1 4 1

5 감사합니다 1 5 2

아래 예는 오라클에서 테이블을 구성하고 검색해 볼 수 있는 환경을 위한 SQL 이다. 

오라클은 AutoIncrement 기능이 없기때문에 sequence 를 이용한다.

<DDL> 예제
 

drop table board;

create table board(

no int primary key,

title varchar2(45),

grp int,

seq int,

lvl int);

drop sequence board_no_seq;

create sequence board_no_seq start with 1 increment by 1;

create index board_grp_seq on board(grp desc, seq asc);

<DML> 예제

[첫번째 게시물 입력 - 새 글 입력]

insert into board

values(board_no_seq.nextval, board_no_seq.currval, 1, 0);

[두번째 게시물 입력 - 새 글 입력]

insert into board

values(board_no_seq.nextval, board_no_seq.currval, 1, 0);

[세번째 게시물 입력 - 새 글 입력]

insert into board

values(board_no_seq.nextval, board_no_seq.currval, 1, 0);

[네번째 게시물 입력 - 첫번째 게시물의 답글]

(답글이 올라오는 경우에는 답글에 부여 할 seq를 먼저 확보해준다.)

update board

set seq=seq+1

where grp=1 and seq > 1;

insert into board

values(board_no_seq.nextval, '반가워요', 1, 2, 1);

[다섯번째 게시물 입력 - 네번째 게시물의 답글]

update board

set seq=seq+1

where grp=1 and seq > 2;

insert into board

values(board_no_seq.nextval, '감사합니다', 1, 3, 2);

[여섯번째 게시물 입력 - 첫번째 게시물의 두번째 답글]

update board

set seq=seq+1

where grp=1 and seq > 1;

insert into board

values(board_no_seq.nextval, 1, 2, 1);

[일곱번째 게시물 입력 - 여섯번째 게시물의 답글]

update board

set seq=seq+1

where grp=1 and seq > 2;

insert into board

values(board_no_seq.nextval, '감사합니다', 1, 3, 2);

[게시판을 검색하는 경우, grp로 내림차순, seq로 오름차순으로 정렬하면 됩니다.]

select case when lvl=0 then no

when lvl>0 then null end no

, rpad('+', lvl, '-')||title title

from board

order by grp desc, seq;

[검색결과]

no    title 

----------------

3 모임이 있습니다 

2 날씨가 맑습니다 

1 안녕하세요  

+환영합니다  

+-감사합니다  

+반가워요 

+-감사합니다 

출처 : http://hdm6337.tistory.com/entry/%EA%B3%84%EC%B8%B5%ED%98%95-%EA%B2%8C%EC%8B%9C%ED%8C%90-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%8C%93%EA%B8%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98