티스토리 뷰

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


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


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


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


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



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



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


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


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


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


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



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



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




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


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


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


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


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

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

17번째는 값을 저장합니다




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


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


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


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


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



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


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


좀 더 공부해서


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


2) 전체적인 동작과정


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



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


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









댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
more
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함