segment tree와 DB

시작.

Notion API 사용 프로젝트에서 이에 대한 구상안을 만드는 중, erdiagram을 짜다가 생각나게 된 아이디어.

아이디어.

DB로부터 검색을 하고 게시판에 글(여러 다양한 종류가 있겠지만 여기선 글이라고 말한다.)을 읽거나 쓸때 각각의 글에 다층적인 카테고리가 형성되있을 때 사용한다.

프로그래밍 구조.

엄밀하게 말해서 segment tree를 곧바로 사용하는 것은 아니고, 이와 비슷한 각각의 node에 children이 여러개인-segment tree는 binary tree로부터 온 것이기 때문에- rooted tree 형태와 list에서 segment tree를 다루는 작동 방식을 복합적용시킨 구조를 사용한다.

사용.

카테고리가 있는 DB에 사용하는 것이기 때문에 기본적인 몇가지 자료구조가 우선적으로 정의되어야 한다.(언어는 python.)

# 부모자식간의 이름 정의.
parent_children_dict = {
	'기본':['a','b','c','d'], 
    'a':['o','p','q'], 
    ...
}

# '기본'으로부터 정의된 depth에 따른 자식 수의 최댓값
depth_length = [1,4,max([len(i) for i in parent_children_dict['기본']), ...]

max_leng = max(depth_length)
max_depth = len(depth_length)

# 정보가 들어갈 유사 segmenet tree.
segment_tree = [None] * (max_leng**max_depth)
# 이 경우 depth_length의 모든 원소의 곱이 최적의 길이지만 만드는 과정에서 함수를 짜기가 귀ㅊ..

카테고리가 정해져 있는 상태에서 글을 쓰거나 읽을 때 각각의 시간(혹은 index, 어찌 되었는 개별의 글이 가지고 있는 서로 다른 독립된 속성)를 업데이트 하는 방식으로 사용한다.

시간을 구분자라 정의하고 사용해보자. 즉, segment_tree에는 float가 원소로 들어갈 것이다.(예시로 time.time() 을 사용한다.)

초깃값.

초깃값은 다음과 같이 세팅해준다.

# 추후 사용하기 위한 leaf 부분의 index를 모아놓은 dictionary. 아래 함수가 실행되며 완성된다.
leaf_dict = dict()
leaf_dict['기본'] = (0,1)

# 유사 segment tree를 사용하기 위한 기초. 정보를 처음 입력하는 부모 사용자가 쓸 때 처음 한번 작동하고 
# 제 역할을 다하기 때문에 segment_tree가 사용되는 변수로써 완성된 이후 더이상의 메모리 소모를 줄이기 위해 아예 다른 모듈로써 분리해서 사용하는 것도 좋은 방법이다.
def make_segment_tree(idx, name, depth):
	# 해당 값에 어떤 것도 업데이트 되지 않은 상태이기 때문에 다른 숫자가 들어갔을 때 비교값이 될 수 있는 0을 초깃값으로 넣어준다.
	segment_tree[idx] = 0
    
    # segment tree가 아니기 때문에 사용하는 값.
    current_child = depth_length[depth]
    next_idx = current_child*idx
    
    for i in range(current_child):
    	# 추가한 정보를 사용하는 부분은 어떻게 사용하는지 설명할 때 같이 설명 예정.
        leaf_dict[name] = (next_idx+i,depth)
    	
        # else 파트의 경우 leaf node의 이름이 parent_child_dict의 key에 없기 때문이다.
        # (있게 생성할 경우 'if len(parent_children_dict[name] != 0:'으로 써줘도 무방하다.)
    	if name in parent_children_dict:
        	# try-except를 쓰는 이유는 각각의 부모에 대해 자식노드의 갯수가 모두 current_child개가 되지 않기 때문이고, 
            # 이경우 갯수를 초과한 index가 들어갈 경우 업데이트 할 것이 없기 때문에 return 한다.
        	try:
	    		make_segment_tree(next_idx+i, parent_child_dict[name][i], depth+1)
            except:
                return
		else:
			segment_tree[next_idx+i] = 0
            
	return
            
make_segment_tree(1,'기본',1)

그리고 글의 경우 결과적으로 쓰고, 읽는(업데이트 하는) 과정이 섞여 있기 때문에 두 개의 함수를 차례대로 쓸 것이다. 통신하는 세세한 과정에 대해서는 굳이 적지 않고, 어떻게 정보를 받을지에 대해서만 적는다.

사용1 : 글쓰기.

• 글을 쓸 권한을 가진 사용자만이 해당.

RESt_API : post

req = {
	category: 'string', 
    제목: 'string', 
    글쓴이: 'string', 
    last_update_time: 'float',
    ~~~
} # 해당 내용의 모든 required = True, created_time이 필요한 이유는 미지수여서 제거했다.

code.

# 글이 여러 카테고리를 가지지는 않기 때문에 유사 segment tree에서 업데이트 되는 값들은 자기자신의 index와 부모(조상들)의 index일때 뿐이다. 
# 이를 이용해서 업데이트 해주면 된다.

def update_segment_tree(category,last_update_time):
	# leaf_dict을 만든 이유1. 유사 segment tree에서 자기자신을 포함한 부모의 값을 변경하기 쉽게 만들기 위해서이다.
	idx,dep = leaf_dict[category]
    segment_tree[idx] = last_update_time
    
    while dep != 0: # 
    	dep -= 1
        idx %= depth_length[dep]
        segment_tree[idx] = last_update_time
    
    return

※ Caution. 현재 아이디어는 글 삭제에 대한 것을 생각하지는 않았다. 이 경우는 유사 segment tree에 글이 업데이트 된 적이 있다는 것을 알려줄 지표 정도로만 사용 가능할 것이다.

사용2 : 검색.

• 모든 사용자가 해당, 각 사용자는 기본 category에 대한 정보가 항시 저장되있음. (`default:'기본')

RESt_API : get

# 해당 res의 last_update_time_user은 category에 따른 마지막 글의 업데이트 시간이다.
req = {
	category: 'string', 
    제목: 'string', 
    사용자: 'string', 
    last_update_time_user: 'float',
    ~~~
} # 사용1과 마찬가지로 해당 내용의 모든 required = True

code.

# segment_tree의 index를 통해 해당 카테도리의 최신 글이 있는지를 체크해준다.

def check_and_update(last_update_time_user,category):
	idx,dep = leaf_dict[category]
    
    # category의 index가 변하지 않은 케이스. 즉, 해당 category에서 추가적인 글이 쓰여지지 않았기 때문에
    # 굳이 추가적인 정보를 보낼 필요가 없다.
    # but, 글 삭제에 대한 기능이 유사 segment tree에 적용된다면, 등호를 부등호로 바꿔서 조정해줘야 한다.
	if segment_tree[idx] == last_update_time_user:
    	return 0
    
    last_update_time = segment_tree[idx]
    return last_update_time
    
'''
return 값으로 last_update_time을 주는 이유는 DB로부터 마지막으로 업데이트된 글 이후 ~ 최신 글까지의 정보를 받아서 
response로 보내주어야 하기 때문이다. 만약 return값이 0인 경우는 res에 변한 것이 없다는 정보를 바로 전송한다.
'''

DB.

쓰다보니 생긴 욕심으로 DB에 대해서도 다뤄보고자 한다. 세세한 구조가 아닌 정말 초보?적인 Node.js와 DB간의 통신언어만 할 줄 알기 때문에(python으로는 언제 생각해보지..ㅎㅎ.. 취업하고 생각해보자.) 자세한 구조에 대해서는 어떻게 적용시키면 될지에 대한 것은 잘 모르겠다.

구조.

• DB 구조의 경우 DB서버 내 local에서는 category에 따라 하나씩의 저장소를 가진다. 또한 중앙제어서버가 존재해서 각 category의 서버를 제어한다.
• 통신 서버로부터 정보(글 및 category, etc..)를 받았을 때는 해당 category의 이름을 가진 DB에만 정보를 저장한다.
• 정보를 요청했을 경우에는 스스로를 포함한 자식노드의 category DB로부터 정보들을 받아 중앙제어서버에서 모든 정보를 병합정렬한 후 정보를 요청한 곳으로 보내준다.

추가.

• (어쩌면 완전 이상한 헛소리일지도 모른다.)

1. web 3.0등의 아이디어가 아마도 크게 기여할 수 있지 않을까? (from Nomads Coders) 본질적으로 마이크로서비스를 지향해서 설명을 했지만 DB 파트의 제어를 하는 부분에서 각각의 DB에서 작동하는 api는 저장과 출력 2가지 뿐이라 DB서버를 나누는 것이 좀 아까울 것 같다는 생각이 든다.

2. 시간종속적으로, 혹은 유저 개개인의 갯수 제한등으로 정보가 거의 완전히 필요가 없는 경우 두 개의 제어만으로 충분할 것 같은데 사용자의 서버와 DB서버에서 각각 제한을 걸어주는 것으로 충분할 것 같다는 생각이다.

- end. -