위키원
스큐드 머클트리
스큐드 머클트리(skewed merkle tree)란 머클트리 중에서 최소 개수의 노드를 가지면서, 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리이다.[1] 머클트리는 해시트리(Hash Tree), 이진트리(Binary Tree)라고 불리기도 하며, 스큐드 머클트리는 편향트리, 사향트리라고도 불리기도 한다.
개요
이진 탐색트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다. [2]스큐드 머클트리 구조를 사용하면 과거 대부분의 데이터가 로컬 환경에 존재하지 않는 상황에서도 데이터 정당성을 검증할 수 있다.
다른 종류
- 포화 이진트리(full binary tree) : 포화 이진트리란 모든 노드가 2개의 자식 노드를 가지며 모든 레벨이 꽉 찬 트리이다.
- 완전 이진트리(complete binary tree) : 완전 이진트리는 포화 이진트리같이 모든 레벨이 꽉 찬 트리는 아니지만 모든 노드가 2개의 자식 노드를 가지는 트리이다.
- 루트 이진트리(rooted binary tree) 루트 이진트리는 모든 노드의 자식이 최대 2개인 루트를 가진 트리이다.
리밸런싱 기법
리밸런싱(Rebalancing) 기법이란 균형을 잡기 위한 트리 구조의 재조정을 말한다. 이 기법을 구현한 트리에는 AVL Tree, Red-Black Tree, B-tree 등이 있다.
Red-Black Tree
Red-Black Tree는 다음의 성질들을 만족하는 이진 탐색트리(BST; Binary Search Tree)이다.
- 각 노드는 'Red' or 'Black'이라는 색깔을 갖는다.
- 루트노드(root node)의 색깔은 'Black'이다.
- 각 리프노드(leaf node)는 'Black'이다.
- 어떤 노드의 색깔이 'red'라면 두 개의 자식의 색깔은 모두 Black이다.
- 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 black nodes들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. (노드 x로부터 노드 x를 포함하지 않은 리프노드까지의 simple path 상에 있는 black nodes들의 개수)
- 특징
- 이진 탐색트리이므로 BST의 특징을 모두 갖는다.
- 루트노드로부터 리프노드까지의 모든 경로 중 최단 경로와 최대 경로의 크기 비율은 2보다 크지 않다. 이러한 상태를 밸런스 상태라고 한다.
- 노드의 자식이 없으면 자식을 가리키는 포인터는 NIL 값을 저장한다. 이러한 NIL들을 리프노드로 간주한다.
RBT는 BST의 삽입, 삭제 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료 구조이다.
AVL트리
AVL트리는 삽입, 삭제, 탐색 등 연산을 수행할 때마다 트리 스스로 자신의 밸런스를 확인하고, 필요할 때마다 밸런스를 조정하는 트리이다. 그래서 자가 균형 트리(Self-balancing Tree)라고도 한다.
- 특징
- AVL트리는 BST이면서 동시에 균형을 유지하고 있다.
- 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.
- 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장한다.
- 장단점
- 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춘다.
- 프로그래밍하기가 어렵고 디버깅 또한 어렵다.
- 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는 데 시간이 든다.
- 대규모 트리를 이룬 후 검색하는 것은 데이터베이스(DB;database)에서 주로 발생하는데 데이터베이스는 이미 B-Tree 자료구조를 사용 중이다.
B-Tree
B-Tree는 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조로 B는 밸런스(Balanced)를 의미하며, 리프노드(leaf node)가 한쪽으로 쏠리는(skewed) 현상이 적다.*[3]
- 특징
- 각 노드는 1/2 이상 채워져야 하며, 모든 리프노드는 같은 레벨(level)에 있다.
- 탐색, 추가, 삭제는 루트노드(root node)로부터 시작한다.
- 노드 내 값은 오름차순을 유지한다.
- 공백이거나 높이가 1 이상인 m-원 탐색 트리(m-way search tree)
- 루트와 리프를 제외한 내부 노드는 최소 m/2, 최대 m개의 서브트리를 가지며, 적어도 m/2-1개의 킷값을 가진다. (적어도 반 이상이 킷값으로 채워져 있어야 한다.)
- 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가진다.
- 모든 리프는 같은 레벨에 있다. (균형트리)
활용
- 베리파이어블 프루닝(verifiable prunning) : 베리파이어블 프루닝 기술이란 블록체인 시스템의 원장이 너무 비대해지는 문제를 해결하기 위한 기술로 이미 원장에서 지워진 데이터라고 해도 나중에 참/거짓의 증명이 가능한 데이터 구조를 가지게 함으로써 극단적인 원장 사이즈 축소를 가능케 한 기술이다. 베리파이어블 프루닝은 2019년 7월초에 로커스체인이 개발한 기술로 데이터를 삭제하는데 있어서 일반적인 프루닝과 동일하지만 모든 데이터를 삭제하지않고 위변조 값을 증명할 수 있는 데이터는 별도로 보관한다. 즉 데이터를 삭제해도 블록체인 기능은 활용할 수 있다. 베리파이어블 프루닝을 하게되면 데이터 위변조를 검증하는데 하루에 수십KB만을 필요로 하게된다. 베리파이어블 프루닝은 테라바이트 시대에 블록체인 업계 전체에 대한 기술적 진보이다. 스큐드 머클트리 구조를 사용하여 과거 대부분의 데이터가 로컬 환경에 존재하지 않는 상황에서도 데이터의 정당성을 검증할 수 있는 기술이다.[4]
각주
- ↑ 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- ↑ _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
- ↑ 〈B-Tree〉, 《ILIFO지덤》
- ↑ 〈베리파이어블 프루닝〉, 《해시넷》
참고자료
- 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
- 씩이 머릿속, 〈[스위프트 : 자료구조 AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능]〉, 《티스토리》, 2018-10-01
- 불곰, 〈AVL Tree〉, 《티스토리》, 2018-08-17
- 〈베리파이어블 프루닝〉, 《해시넷》
- 〈B-Tree〉, 《ILIFO지덤》
