머클 트리

랄프 머클이 제안한 자료구조로써 대구모 데이터셋을 안전하고 효율적으로 검증할 수 있다.

머클 트리는 이진 트리로, 입력을 먼저 리프 노드에 배치한 다음, 자식 노드 쌍의 값을 함께 해싱하여 부모 노드의 값을 구하는 방식으로 머클 트리라는 하나의 해시 값을 얻ㅇ르 때까지 부모 노드의 값을 구해나가는 트리이다.

이진트리이므로 조회 시 logN의 시간 복잡도를 가져 탐색 속도가 빠르며, 해시값을 통해 이진 트리를 구성하게 되므로 데이터 위변조 시 빠르게 알아차릴 수 있다.

또한 풀노드를 저장하는 것이 아닌, 일부 노드만을 저장하여 라이트 노드로써 데이터를 저장할 수 있기에 효율적이다.