[Article] 무한 depth

무한 depth

XXXXX	|  XXXXX  |  XXXXX  | ...........
1depth    2depth    3depth    4depth

depth 별로 5개의 문자열 경로 정보를 갖는다.

• 1depth : 5개의 문자열
• 2depth : 10개의 문자열
• 3depth : 15개의 문자열

  N depth = (N * 5)

5개의 문자열로 나타내므로, 표현 범위가 제한된다. 10개의 숫자로 나타내면 표현 수는
10 ^ 5 = 100,000개로 제한된다. (00000 ~ 99999)

하지만 문자열이기 떄문에 0~9, A~Z, a~z 62개의 문자를 사용할 수 있다.
62 ^ 5 - 916,132,832개로 제한된다. (00000 ~ zzzzz)

데이터베이스 collation

문자열을 정렬하고 비교하는 방법을 정의하는 설정

SELECT table_name, table_colation 
FROM information_schema.TABLES WHERE table_schema = 'comment';

utf8mb4_0900_ai_ci 설정인 것을 확인할 수 있다.
_ci는 대소문자의 순서를 비교할 수 없다. 그래서 utf8mb4_bin 을 사용한다.

create table comment(
	path varcher(25) character set utf8md4 collate utf8md4_bin not null
...
);

create unique index inx_article_id_path on comment(article_id asc, path asc);

무한 depth

00a0z  <- parentPath
├── 00a0z 00000
├── 00a0z 00001
├── 00a0z 00002 <- childernTopPath
└── ?  		└── 00a0z 00002 00000 <- descendantsTopPath

descendantsTopPath 찾아 신규 댓글의 depth * 5까지만 남기고 잘라내면 된다. ex) 00a0z 00002 00000 에서 (신규 댓글의 depth * 2) * 5 = 10개의 문자만 남기고 잘라내면 00a0z 00002를 찾을 수 있다.

select path from comment
 where article_id = {article_id}
   and path > {parentPath} 
   and path like {parentPath}% 
order by path desc 
 limit 1; 

descendantsTopPath를 구할 수 있다.

code

public class CommentPath {
    private String path;

    private static final String CHARSET = "0123456789ABCDEFGHIJKMNLOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

    private static final int DEPTH_CHUNK_SIZE = 5;
    private static final int MAX_DEPTH = 5;

    // MIN_CHUNK = "00000" MAX_CHUNK = "zzzzz"
    private static final String MIN_CHUNK = String.valueOf(CHARSET.charAt(0)).repeat(DEPTH_CHUNK_SIZE);
    private static final String MAX_CHUNK = String.valueOf(CHARSET.charAt(CHARSET.length() - 1)).repeat(DEPTH_CHUNK_SIZE);

• CHARSET에 62개의 문자열 정의
• 최대 Depth 깊이와 Depth 길이 정의
• 시작과 끝 Depth 정의

    public static CommentPath create(String path) {
        if(isDepthOverflow(path)){
            throw new IllegalStateException("depth overflowed");
        }
        CommentPath commentPath = new CommentPath();
        commentPath.path = path;
        return commentPath;
    }

• 팩토리 메서드

    public CommentPath createChildCommentPath(String descendantsTopPath) {
        if (descendantsTopPath == null) {
            return CommentPath.create(path + MIN_CHUNK);
        }
        String childrenTopPath = findChildrenToPath(descendantsTopPath);
        return CommentPath.create(increase(childrenTopPath));
    }

• 자식 여부를 체크해 자식이 없다면 depth 자식 생성, null아니라면 자식 또는 형제 생성
• path가 빈 값이고 descendantsTopPath이 00000 라면 00001을 형제 생성
• 00000이 자식을 생성하려 할때 00000 00000 자식이 존재한다. descendantsTopPath이 00000 00000에서 형제이고 00000 자식인 00000 00001을 생성 한다.

private String findChildrenToPath(String descendantsTopPath) {
        return descendantsTopPath.substring(0, (getDepth() + 1) * DEPTH_CHUNK_SIZE);
}

• 루트에서 형제를 생성한다면 path = "" 뎁스는 0이고, 00000을 반환
• 자식을 생성한다면 path = 00000뎁스는 1이고 00000 00000을 반환

private String increase(String path) {
        // 00000 00000
        String lastChunk = path.substring(path.length() - DEPTH_CHUNK_SIZE);
        if (isChunkOverflow(lastChunk)) {
            throw new IllegalStateException("chunk overflowed");
        }
        int charsetLength = CHARSET.length();

        int value = 0;
        for(char ch : lastChunk.toCharArray()) {
            value = value * charsetLength + CHARSET.indexOf(ch);
        }

        value = value + 1;

        String result = "";
        for(int i = 0 ; i < DEPTH_CHUNK_SIZE ; i++) {
            result = CHARSET.charAt(value % charsetLength) + result;
            value /= charsetLength;
        }

        return path.substring(0, path.length() - DEPTH_CHUNK_SIZE) + result;
    }

• 루트가 형제를 생성하기 위해00000을 받았다면 00001을 반환하고, 자식을 만들기 위해 00000 00000을 받았다면 00000 00001을 반환하게 된다.
• 문자열 청크를 62진수 숫자로 변환하고 1을 증가시킨다.
• 다시 62진수 숫자를 문자열 청크(길이 5)로 변환