위키원
스큐드 머클트리
스큐드 머클트리(skewed merkle tree)란 머클트리 중에서 최소 개수의 노드를 가지면서, 왼쪽이나 오른쪽 서브 트리만 가지고 있는 트리이다.[1] 편향트리 또는 사향트리라고도 한다.
개요
머클트리의 탐색 연산은 O(log n)의 시간 복잡도를 갖는다. 트리의 높이를 하나씩 더해갈수록 추가할 수 있는 노드의 수가 두 배씩 증가하기 때문이다. 하지만 저장 순서에 따라 계속 한쪽으로만 노드가 추가되는 경우가 발생할 수 있는데, 이러한 경우 스큐드 머클트리가 된다. 이럴 경우 성능에 영향을 미치게 되며, 탐색의 Worst Case가 되고 시간 복잡도는 0(n)이 된다. [2] 스큐드 머클트리는 왼쪽 사양 이진트리와 오른쪽 사양 이진트리로 나뉜다.
- 왼쪽 사향 이진트리 : 오른쪽 자식이 없는 노드들로만 구성된 트리
- 오른쪽 사향 이진트리 : 왼쪽 자식이 없는 노드들로만 구성된 트리
스큐드 머클트리 구조를 사용하면 과거 대부분의 데이터가 로컬 환경에 존재하지 않는 상황에서도 데이터 정당성을 검증할 수 있는 장점이 있다. 또한 스큐드 머클트리는 전 블록 루트 위에 현재 블록의 트랜잭션들을 이용해 새 트리를 만들어 지금까지 실행된 전체 트랜잭션 목록을 담는 해시를 빠르고 가볍게 생성할 수 있다. 즉, 전체 트랜잭션 목록을 점증적으로 만들 수 있고, 만드는 데 드는 시간과 메모리는 트랜잭션 수에 선형적으로만 비례한다.
리밸런싱 기법
리밸런싱(Rebalancing) 기법이란 균형을 잡기 위한 트리 구조의 재조정을 말한다. 이 기법을 구현한 트리에는 레드블랙트리(Red-Black Tree), AVL트리(AVL Tree), 비트리(B-Tree) 등이 있다.
레드블랙트리
레드블랙트리(Red-Black Tree)는 다음의 성질들을 만족하는 이진 탐색트리(BST; Binary Search Tree)이다. 이진 탐색트리이므로 삽입, 삭제, 연산 과정에서 발생할 수 있는 문제점을 해결하기 위해 만들어진 자료구조인 BST의 특징을 모두 갖는다. 레드블랙트리느 항상 밸런스 상태인데, 이는 루트노드로부터 리프노드까지의 모든 경로 중 최단 경로와 최대 경로의 크기 비율이 2보다 크지 않음을 뜻한다. 레드블랙트리는 노드의 자식이 없으면 자식을 가리키는 포인터가 NIL 값을 저장하고 이 NIL들을 리프노드로 간주한다.
- 성질
- 각 노드는 빨강(Red) 혹은 검정(Black)색을 갖는다.
- 루트노드(root node)의 색깔은 검정이다.
- 각 리프노드(leaf node)는 검정색이다.
- 어떤 노드의 색깔이 빨강이라면 두 개의 자식의 색깔은 모두 검정이다.
- 각 노드에 대해서 노드로부터 descendant leaves까지의 단순 경로는 모두 같은 수의 검정 노드들을 포함하고 있다. 이를 해당 노드의 Black-Height라고 한다. (노드 x로부터 노드 x를 포함하지 않은 리프노드까지의 단순 경로(simple path) 상에 있는 검정 노드들의 개수)
AVL트리
AVL트리(AVL Tree)는 삽입, 삭제, 탐색 등 연산을 수행할 때마다 트리 스스로 자신의 밸런스를 확인하고, 필요할 때마다 밸런스를 조정하는 트리이다. 그래서 자가 균형 트리(Self-balancing Tree)라고도 한다.[3] AVL트리는 BST이면서 동시에 균형을 유지하고 있기 때문에 이진 검색 시의 효율성을 보장한다. 이 구조에서 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하다.
- 장단점
- 검색, 삽입, 삭제 모두 O(logN)이며 항상 균형을 맞춘다.
- 프로그래밍하기가 어렵고 디버깅 또한 어렵다.
- 위 검색, 삽입, 삭제가 빠르긴 하지만 균형을 맞추는 데 시간이 든다.
- 대규모 트리를 이룬 후 검색하는 것은 데이터베이스(DB)에서 주로 발생하는데 데이터베이스는 이미 비트리 자료구조를 사용 중이다.
비트리
비트리(B-Tree)는 데이터를 정렬하여 탐색, 삽입, 삭제 및 순차 접근이 가능하도록 유지하는 트리형 자료구조로 B는 밸런스(Balanced)를 의미하며, 리프노드가 한쪽으로 쏠리는(skewed) 현상이 적다.[4] 이 구조에서 각 노드는 1/2 이상 채워져야 하며, 모든 리프노드는 같은 레벨(level)에 있다. 탐색, 추가, 삭제는 루트노드로부터 시작하고 노드 내 값은 오름차순을 유지한다. 비트리는 공백이거나 높이가 1 이상인 m-원 탐색 트리(m-way search tree)이기도 하다. 루트와 리프를 제외한 내부 노드는 최소 m/2, 최대 m개의 서브트리를 가지며, 적어도 m/2-1개의 킷값을 가진다.(적어도 반 이상이 킷값으로 채워져 있어야 한다.) 루트는 그 자체가 리프가 아닌 이상 적어도 두 개의 서브트리를 가지며 모든 리프는 같은 레벨에 있어 균형트리 중 하나이다.
- 장단점
- 노드의 삽입/삭제 후에도 균형트리 유지로 균등한 응답 속도를 보장한다.
- 시간 복잡도가 0(logN)이다.
- 삽입/삭제 시 트리의 균형을 유지하기 위해 복잡한 연산 수행이 필요하다.
활용
- 베리파이어블 프루닝(verifiable prunning) : 베리파이어블 프루닝이란 블록체인 시스템의 원장이 너무 비대해지는 문제를 해결하기 위한 기술로 이미 원장에서 지워진 데이터라고 해도 나중에 참/거짓의 증명이 가능한 데이터 구조를 가지게 함으로써 극단적인 원장 사이즈 축소를 가능케 한 기술이다. 베리파이어블 프루닝은 2019년 7월초에 로커스체인이 개발한 기술로 데이터를 삭제하는데 있어서 일반적인 프루닝과 동일하지만 모든 데이터를 삭제하지 않고 위변조 값을 증명할 수 있는 데이터는 별도로 보관한다. 즉 데이터를 삭제해도 블록체인 기능은 활용할 수 있다. 베리파이어블 프루닝을 하게되면 데이터 위변조를 검증하는데 하루에 수십만 KB를 필요로 하게된다. 베리파이어블 프루닝은 테라바이트 시대에 블록체인 업계 전체에 대한 기술적 진보이다. 스큐드 머클트리 구조를 사용하여 과거 대부분의 데이터가 로컬 환경에 존재하지 않는 상황에서도 데이터의 정당성을 검증할 수 있는 기술이다.[5]
각주
- ↑ 푸른하늘의해, 〈이진 트리(Binary Tree)〉, 《네이버 블로그》, 2012-07-08
- ↑ _lbee, 〈(DataStructure) 5. Red-Black Tree〉, 《티스토리》, 2017-03-11
- ↑ 씩이 머릿속, 〈(스위프트 : 자료구조) AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능〉, 《티스토리》, 2018-10
- ↑ 〈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지덤》
- 동그리동동닷컴, 〈[https://wondong2.tistory.com/9 5장 자료 구조의 기본〉, 《티스토리》, 2017-02-03
- Hello!! Kyle, 〈[https://maskkwon.tistory.com/219 (Data Structure)B-tree 정의 및 장/단점〉, 《티스토리》, 2015-12-02
- Seulgi Kim, 〈[https://blog.seulgi.kim/2018/06/skewed-merkle-tree.html#comment-form Skewed Merkle Tree〉, 《블로거》, 2018-06-15
같이 보기
