Day : 36
Blockchain Day : 6
Merkle Patricia Trie (MPT)
: 머클 트리를 사용하는 이유는 키값을 효율적으로 관리하기 위함이다.
(머클 트리 : 하위 노드를 해시해서 상위 노드 생성)
: 기존의 머클트리를 개선(Radix Trie를 반영)하여 만든 것이 Merkle Patricia Trie
: 중간에 값이 들어와도 값을 효율적으로 추가할 수 있게 수정해서 절충안을 만들어 MPT에 적용
1. 이진트리 vs Trie vs RadixTree(Trie)
- Trie : 하나하나 값 분리(긴 그림)
- RadixTree : 묶어서 효율성있게
- 이진트리 vs Trie/RadixTree(Trie)
: Trie는 이진 트리보다 key-value쌍에 더 집중, 특화 되어있음
: path 하나하나 RLP 인코딩을 거침
( 중간중간에 특정 노드에서는 바로 value를 받을 수도 있음 )
2. Merkle Patricia Trie
prefix 는 데이터 압축하는데 도움이됨
- 익스텐션은 다음노드가 무조건 하나임
- 따라서 익스텐션 -브렌치 - 리프 순으로 주로 연결
(추가예정)
➕ 노드 : 컴퓨터 과학에서 쓰는 기초 단위 ; 최소한의 단위가 되는 정보
- 자료구조의 노드 : 트리구조에서 각각의 데이터를 담고있는 하나의 동그라미; path
- 네트워크 노드 : 통신을 담당하는 하나의 장비 ; ex) 컴퓨터
참고자료
Today I Learned