텍스트 기반 검색을 공부하다 보면 유독 Trie라는 자료구조를 자주 만나게 된다. 특히 문자열 검색, 자동완성, 사전 검색 같은 기능에서 Trie는 빠지지 않는다.
RedisSearch나 ElasticSearch 같은 대형 검색 엔진에서도 term lookup, prefix matching 최적화에 Trie를 활용하고 있다고 한다.
| 서비스/엔진 | Trie 활용 방식 |
| Redis Stack / RediSearch | autocomplete suggestion을 trie 기반 자료구조에 저장. prefix 입력에 대한 추천어 검색에 사용 |
| Elasticsearch / Apache Lucene | 전문 검색은 기본적으로 inverted index 기반이지만, term dictionary나 prefix 탐색에 FST 같은 Trie 계열 압축 구조를 사용 |
| Solr / Apache Lucene | Lucene 기반이라 Elasticsearch와 비슷하게 term lookup, prefix 검색 등에 FST/term dictionary 구조 활용 |
| 검색 자동완성 시스템 | 검색어 추천, command completion, prefix matching에 Trie 또는 compressed Trie 활용 |
| 라우팅/네트워크 시스템 | IP prefix matching에 Patricia Trie/Radix Tree 계열 활용 |
뿐만 아니라 블록체인, 이더리움에서도 Merkle Patricia Trie라는 자료구조가 핵심적으로 사용된다.
텍스트 검색부터 블록체인 주소 검색까지 대용량의 데이터를 빠르게 접근하는 Trie 구조와 이를 기반으로 한 Patricia Trie, Merkle Tree, Merkle Patricia Trie에 대해 알아보자.
1. Trie란 무엇인가?
Trie는 문자열을 저장하기 위한 트리 기반 자료구조다. 핵심 아이디어는 간단하다.
여러 문자열이 공통으로 가지는 접두사(prefix)를 한 번만 저장한다.
예를 들어 다음과 같은 단어들이 있다고 하자.
car
cat
can
dog
일반적인 방식으로 저장하면 각 문자열을 따로 저장한다.
car
cat
can
dog
이 경우 car, cat, can은 모두 앞의 ca를 공유하지만, 각각의 문자열 안에 c, a가 반복해서 저장된다.
Trie는 이를 다음과 같이 저장한다.
(root)
├─ c
│ └─ a
│ ├─ r → car
│ ├─ t → cat
│ └─ n → can
└─ d
└─ o
└─ g → dog
car, cat, can이 공유하는 c → a 경로를 한 번만 저장하고, 이후 달라지는 문자부터 가지를 나눈다.
즉, Trie의 핵심은 다음과 같다.
공통 접두사는 공유하고, 달라지는 부분부터 분기한다.
2. Trie가 효율적인 이유
Trie의 장점은 크게 두 가지다.
첫째, 공통 접두사를 공유하기 때문에 중복 저장을 줄일 수 있다. 특히 비슷한 접두사를 가진 문자열이 많을수록 효과가 크다.
둘째, 검색 시간이 문자열의 개수보다 검색하려는 문자열의 길이에 비례한다.
예를 들어 cat을 찾는다고 하면, Trie에서는 다음 경로만 따라가면 된다.
c → a → t
단어가 10개 있든 100만 개 있든, cat을 검색할 때 확인하는 문자는 3개다. 따라서 검색 시간복잡도는 보통 O(L) 같이 표현된다. 여기서 L은 검색하려는 문자열의 길이다.
이러한 특성 때문에 Trie는 자동완성 기능에 적합하다. 예를 들어 ca로 시작하는 단어를 찾고 싶다면, 먼저 c → a 노드까지 이동한 뒤 그 아래에 있는 단어들을 모두 탐색하면 된다.
ca
├─ r → car
├─ t → cat
└─ n → can
따라서 prefix 검색을 빠르게 수행할 수 있다.
3. Trie의 단점
Trie가 항상 메모리 효율적인 것은 아니다. 일반 Trie는 문자 하나마다 노드를 만든다. 그래서 문자열들이 공통 접두사를 많이 공유하지 않거나, 각 노드가 많은 포인터 또는 map 구조를 가진다면 오히려 메모리 사용량이 커질 수 있다.
예를 들어 다음과 같은 단어들이 있다고 해보자.
apple
banana
coffee
dragon
이 단어들은 앞부분이 거의 겹치지 않는다. 이 경우 Trie의 접두사 공유 이점은 줄어든다.
또한 일반 Trie에서는 중간에 갈림길이 없는 경로도 문자 단위로 노드를 계속 만든다.
i → n → t → e → r → n → a → l
만약 중간에 분기점이 없다면, 굳이 문자 하나마다 노드를 둘 필요가 있을까? 이런 문제의식에서 Patricia Trie가 등장한다.
4. Patricia Trie란 무엇인가?
Patricia Trie는 일반 Trie를 압축한 구조다. 보통 압축 Trie 또는 Radix Tree 계열로 설명된다. 핵심 아이디어는 다음과 같다.
자식이 하나뿐인 연속 경로를 하나로 압축한다.
예를 들어 다음 단어들이 있다고 하자.
bear
bell
bid
bull
buy
일반 Trie에서는 문자 하나마다 노드를 만든다.
(root)
└─ b
├─ e
│ ├─ a
│ │ └─ r
│ └─ l
│ └─ l
├─ i
│ └─ d
└─ u
├─ l
│ └─ l
└─ y
그런데 a → r, l → l, i → d처럼 중간에 갈림길이 없는 경로들이 있다. Patricia Trie는 이런 부분을 압축한다.
(root)
└─ b
├─ e
│ ├─ ar → bear
│ └─ ll → bell
├─ id → bid
└─ u
├─ ll → bull
└─ y → buy
즉, 일반 Trie가 문자 단위로 노드를 만든다면, Patricia Trie는 분기가 없는 문자열 구간을 하나의 간선 또는 노드로 저장한다.
정리하면 다음과 같다.
일반 Trie:
문자 하나마다 노드를 만든다.
Patricia Trie:
갈림길이 없는 연속 경로를 압축한다.
5. Patricia Trie의 장단점
Patricia Trie의 가장 큰 장점은 노드 수를 줄일 수 있다는 점이다.
예를 들어 다음 문자열들이 있다고 하자.
international
internet
internal
이 단어들은 inter라는 공통 prefix를 가진다. Patricia Trie에서는 다음과 같이 압축해서 표현할 수 있다.
(root)
└─ inter
├─ national
├─ net
└─ nal
이렇게 하면 일반 Trie보다 불필요한 중간 노드를 줄일 수 있고, 메모리 사용량도 줄일 수 있다.
하지만 단점도 있다. 구현이 일반 Trie보다 복잡하다. 일반 Trie는 문자 하나씩 따라가면 되지만, Patricia Trie는 압축된 문자열 조각을 비교해야 한다. 또한 삽입 과정에서 기존 경로와 새 문자열이 중간에서 갈라지면 노드를 쪼개야 한다.
예를 들어 기존에 internet이 있고 새로 internal을 삽입한다고 하자.
internet
internal
두 단어는 inter까지 같고, 그 뒤부터 net, nal로 갈라진다. Patricia Trie는 이 공통 지점을 찾아 노드를 분리해야 한다.
따라서 Patricia Trie는 메모리 효율성은 좋아지지만, 삽입과 삭제 구현은 더 복잡해진다.
6. Merkle Tree란 무엇인가?
Merkle Patricia Trie를 이해하려면 Merkle Tree도 알아야 한다.
Merkle Tree는 각 노드가 해시값을 가지는 트리 구조다. 리프 노드는 데이터의 해시를 가지고, 부모 노드는 자식 노드들의 해시를 다시 해시해서 만든다.
Root Hash
/ \
Hash A Hash B
/ \ / \
data1 data2 data3 data4
Merkle Tree의 핵심은 다음과 같다.
전체 데이터를 직접 비교하지 않아도, 루트 해시만 비교하면 데이터가 변경되었는지 확인할 수 있다.
예를 들어 data3이 바뀌면 Hash B가 바뀌고, 결국 Root Hash도 바뀐다. 즉, Merkle Tree는 데이터 무결성을 검증하는 데 유용하다.
또한 특정 데이터가 트리에 포함되어 있다는 것을 증명할 때도 전체 데이터를 다 제공할 필요가 없다. 해당 데이터에서 루트까지 올라가는 경로에 필요한 해시들만 제공하면 된다. 이를 Merkle Proof라고 한다.
7. Merkle Patricia Trie란 무엇인가?
Merkle Patricia Trie는 이름 그대로 Merkle Tree와 Patricia Trie의 특징을 결합한 자료구조다. 간단히 말하면 다음과 같다.
Patricia Trie:
key를 prefix 기반으로 효율적으로 저장하고 검색한다.
Merkle Tree:
각 노드에 해시를 붙여 데이터 무결성을 검증한다.
Merkle Patricia Trie:
key-value 데이터를 효율적으로 저장하면서,
각 노드의 해시를 통해 전체 상태의 무결성과 포함 여부를 검증한다.
즉, Merkle Patricia Trie는 단순한 검색 자료구조가 아니라, 검색과 검증을 동시에 지원하는 자료구조다.
예를 들어 다음과 같은 key-value가 있다고 하자.
do → verb
dog → puppy
doge → coin
Patricia Trie처럼 공통 prefix를 공유한다.
do
├─ 끝 → verb
└─ g
├─ 끝 → puppy
└─ e → coin
여기에 Merkle Tree처럼 각 노드에 해시를 붙인다.
Hash(root)
└─ Hash(do)
├─ Hash(value: verb)
└─ Hash(g)
├─ Hash(value: puppy)
└─ Hash(e → coin)
이제 doge → coin 값이 바뀌면, 그 값이 포함된 경로의 해시들이 바뀌고 최종적으로 root hash도 바뀐다.
따라서 루트 해시 하나로 전체 상태가 바뀌었는지 확인할 수 있다.
8. 이더리움에서 Merkle Patricia Trie를 사용하는 이유
이더리움에는 수많은 계정 상태가 존재한다.
예를 들어 다음과 같은 데이터들이 있다.
주소 A → 잔액 10 ETH
주소 B → 잔액 3 ETH
주소 C → nonce 5
주소 D → 스마트 컨트랙트 코드 정보
블록체인에서는 이 상태 데이터를 단순히 저장하는 것만으로는 부족하다. 중요한 것은 다음이다.
이 상태가 정말 블록에 기록된 상태와 일치하는지 검증할 수 있어야 한다.
이더리움은 전체 계정 상태를 Merkle Patricia Trie에 저장하고, 그 루트 해시를 블록 헤더에 기록한다.
Block Header
└─ stateRoot
이 stateRoot는 현재 이더리움 전체 상태를 대표하는 해시값이다.
계정 하나의 잔액이 바뀌어도 관련된 노드의 해시가 바뀌고, 최종적으로 stateRoot도 바뀐다. 따라서 블록 헤더의 stateRoot를 통해 해당 블록 시점의 전체 상태를 검증할 수 있다.
9. 이더리움 State Trie의 key와 value
이더리움의 State Trie는 대략 다음과 같이 이해할 수 있다.
key = 계정 주소
value = 해당 주소의 계정 상태
다만 정확히는 주소 자체를 그대로 key로 쓰기보다는, 주소를 해시한 값을 Trie의 key로 사용한다고 보면 된다.
각 계정의 상태는 단순히 잔액만 의미하지 않는다. 이더리움의 account state에는 다음 정보들이 포함된다.
Account State
├─ nonce
├─ balance
├─ storageRoot
└─ codeHash
각 항목의 의미는 다음과 같다.
nonce:
해당 계정이 보낸 트랜잭션 수 또는 컨트랙트 생성 횟수와 관련된 값
balance:
계정의 ETH 잔액
storageRoot:
스마트 컨트랙트의 내부 저장소를 가리키는 Storage Trie의 루트 해시
codeHash:
스마트 컨트랙트 코드의 해시
즉, 이더리움의 State Trie는 다음과 같은 형태로 볼 수 있다.
address A → account state A
address B → account state B
address C → account state C
그리고 어떤 주소가 스마트 컨트랙트 계정이라면, 그 계정의 내부 저장소는 storageRoot를 통해 별도의 Storage Trie로 연결된다.
10. 스마트 컨트랙트의 세부 저장소는 어디에 저장될까?
스마트 컨트랙트는 상태 변수를 가질 수 있다.
예를 들어 Solidity 코드에서 다음과 같은 변수가 있다고 하자.
uint256 totalSupply;
mapping(address => uint256) balances;
이 값들은 컨트랙트 코드 내부에 직접 저장되는 것이 아니다. 컨트랙트 작성자가 별도로 어딘가에 저장하는 것도 아니다. 컨트랙트별 세부 저장소는 해당 컨트랙트 계정의 storageRoot가 가리키는 별도의 Storage Trie에 저장된다. 그리고 이 데이터는 이더리움 노드들이 자신의 상태 데이터베이스에 저장한다.
구조를 단순화하면 다음과 같다.
Ethereum Node
└─ State Database
└─ State Trie
└─ key: contract address
value: Account State
├─ nonce
├─ balance
├─ storageRoot ──→ Storage Trie
└─ codeHash
그리고 Storage Trie는 다음과 같은 형태다.
Storage Trie of Contract A
├─ key: storage slot 0 → value
├─ key: storage slot 1 → value
├─ key: storage slot 2 → value
└─ ...
즉, 컨트랙트 A의 상태 변수들은 컨트랙트 A의 Storage Trie에 저장된다.
11. 컨트랙트 storage가 변경되면 어떤 일이 일어날까?
예를 들어 다음 코드가 실행된다고 하자.
balances[msg.sender] = 100;
이 코드는 EVM에서 실행되며, storage 값을 변경하는 명령으로 이어진다. 이때 이더리움 노드는 실행 결과에 따라 해당 컨트랙트의 Storage Trie를 갱신한다.
흐름은 다음과 같다.
1. EVM이 balances[msg.sender]가 저장될 storage slot을 계산한다.
2. 해당 컨트랙트의 Storage Trie에서 그 slot 값을 100으로 변경한다.
3. Storage Trie의 root hash가 변경된다.
4. Account State의 storageRoot가 변경된다.
5. State Trie의 root hash, 즉 stateRoot가 변경된다.
6. 변경된 stateRoot가 블록 헤더에 기록된다.
이 구조 덕분에 이더리움은 스마트 컨트랙트의 세부 상태 변경까지 최종적으로 하나의 stateRoot에 반영할 수 있다.
12. 전체 구조 정리
이더리움의 상태 저장 구조를 한 번에 정리하면 다음과 같다.
Block Header
└─ stateRoot
└─ State Trie
├─ address A → Account State
│ ├─ nonce
│ ├─ balance
│ ├─ storageRoot
│ └─ codeHash
│
└─ contract address B → Account State
├─ nonce
├─ balance
├─ storageRoot ──→ Storage Trie
│ ├─ slot 0 → value
│ ├─ slot 1 → value
│ └─ ...
└─ codeHash
핵심은 다음이다.
주소를 key로 해서 계정 상태를 찾는다.
계정 상태에는 balance, nonce, storageRoot, codeHash가 들어 있다.
컨트랙트의 내부 저장소는 storageRoot가 가리키는 별도 Storage Trie에 저장된다.
모든 변경은 최종적으로 stateRoot에 반영된다.
13. 결론
Trie는 문자열이나 key를 prefix 기반으로 효율적으로 저장하고 검색하기 위한 자료구조다. 일반 Trie는 문자 하나마다 노드를 만들지만, Patricia Trie는 갈림길이 없는 경로를 압축하여 노드 수를 줄인다.
Merkle Tree는 각 노드에 해시를 붙여 데이터의 무결성을 검증할 수 있게 한다. Merkle Patricia Trie는 이 둘을 결합하여, key-value 데이터를 효율적으로 저장하면서도 전체 데이터의 변경 여부와 특정 데이터의 포함 여부를 검증할 수 있게 한다.
이더리움은 이러한 Merkle Patricia Trie를 사용하여 전체 계정 상태를 관리한다. 주소를 key로 사용해 account state를 찾고, account state 안의 storageRoot를 통해 스마트 컨트랙트별 세부 저장소를 다시 찾는다. 그리고 이 모든 상태 변화는 최종적으로 블록 헤더의 stateRoot에 반영된다.
따라서 Merkle Patricia Trie는 이더리움에서 단순한 저장 자료구조가 아니라, 상태 저장, 검색, 무결성 검증, 포함 증명을 동시에 가능하게 하는 핵심 자료구조라고 볼 수 있다.