머클패트리샤트리(Merkle patricia tree)에 대해 알아보자

이번 시간에는 “머클패트리샤 트리”에 대하여 알아보겠습니다

머클패트리샤 트리는 머클트리 + 패트리샤 트리 입니다

여기서 패트리샤트리는 “트라이”라고 생각하시면 됩니다!

자료구조 / 알고리즘을 공부하신 분들 중에 트라이를 알고 계신다면

공부할 때 이해가 더 쉬우실 것 입니다!

그럼 먼저 트라이에 대해 잠시 살펴보면

이런식으로 루트부터 시작하여

노드마다 한글자씩 담당해 단어를 만들어가는 형태의 트리 입니다

그림을 보시면 이해가 쉽습니다!

우선 이렇게 저장하면 중복되는 것을 효율적으로 줄일 수 있고

단어를 찾을 때 최대단어길이 만큼 시간이 들게 됩니다

머클패트리샤 트리에서는 radix 트라이인 radix트리를 사용합니다

이런식으로 공간을 더 효율적으로 사용하게 됩니다

그리고 트리의 성능 향상을 위해 노드가 4가지 타입을 갖게 됩니다

1) 공백노드 : 말 그대로 비어있는 노드 입니다

2) 리프노드 : [RLP 인코딩된 경로, 값]을 가집니다

3) 확장노드 : [RLP 인코딩된 경ㄹ, 키]의 목록을 가집니다

4) 브랜치 노드 : [0…f,값]을 가지고 17개의 항목으로 구성됩니다

그 중 앞에 16개는 다음 노드를 가리키는 키 역할을 하고

17번째는 값을 저장합니다

위와같이 그림으로 나타낸다면 각 노드의 역할을 쉽게 이해할 수 있습니다

그림 오른쪽 상단의 나와있는 값들과 트라이를 타고 들어가면 나오는

값들을 비교하시면 똑같다는 것을 확인하실 수 있습니다!

노드마다 앞에 있는 prefix는 선행구분자 방식의 인코딩으로

왼쪽 아래에 나와있는 그림을 보시면 각 숫자의 뜻을 알 수 있습니다

오늘은 간단하게 이더리움에서 쓰이는 머클패트리샤 트리를 보았는데

제가 깊게 이해를 못해서 너무 기본적인 내용만 있습니다…ㅠㅠ

좀 더 공부해서

1) 이더리움에서는 왜 이것을 써야만 했는지

2) 전체적인 동작과정

등을 추가하도록 하겠습니다!

저도 공부해서 올리는 내용이라 틀린 내용이 있을 수 있습니다

틀린내용은 댓글로 알려주시면 감사하겠습니다!

Originally published at sejinik.tistory.com on October 8, 2018.