우선 trie에서 사용되는 node들을 살펴보자
trie 패키지에의 node는 interface 타입이다.
type node interface {
cache() (hashNode, bool)
encode(w rlp.EncoderBuffer)
fstring(string) string
}구현은 다음과 같이 네 종류가 존재한다.
type (
fullNode struct {
Children [17]node // Actual trie node data to encode/decode (needs custom encoder)
flags nodeFlag
}
shortNode struct {
Key []byte
Val node
flags nodeFlag
}
hashNode []byte
valueNode []byte
)
- shortNode는 key/val 형식이다.
- Val에는 fullNode나 hashnode,valuenode가 들어갈 수 있다.
- fullNode는 branch 노드이다. 0~15까지의 분기가 존재하고, 16은 value를 저장한다.
어떻게 작동할까?
func TestInsert() {
trie := NewEmpty(NewDatabase(rawdb.NewMemoryDatabase()))
updateString(trie, "doe", "reindeer")
updateString(trie, "dog", "puppy")
updateString(trie, "dogglesworth", "cat")
}
func updateString(trie *Trie, k, v string) {
trie.Update([]byte(k), []byte(v))
}
- Update는 tryUpdate(key, value []byte)를 호출한다.
// tryUpdate expects an RLP-encoded value and performs the core function
// for TryUpdate and TryUpdateAccount.
func (t *Trie) tryUpdate(key, value []byte) error {
t.unhashed++
k := keybytesToHex(key)
// ...
_, n, err := t.insert(t.root, nil, k, valueNode(value))
// ...
t.root = n
// ...
return nil
}- insert는 내부에서 재귀적으로 호출된다.
- 여기서 key/value를 insert 할 때마다 구조가 trie 구조가 변경될 수 있다.(새로운 branch 생성)
func (t *Trie) insert(n node, prefix, key []byte, value node) (bool, node, error) {
// ...
switch n := n.(type) {
case *shortNode:
// key와 n.key가 완전히 같지 않다면 fullNode(branch)가 필요하다는 의미이다.
matchlen := prefixLen(key, n.Key)
// If the whole key matches, keep this short node as is
// and only update the value.
if matchlen == len(n.Key) {
dirty, nn, err := t.insert(n.Val, append(prefix, key[:matchlen]...), key[matchlen:], value)
if !dirty || err != nil {
return false, n, err
}
return true, &shortNode{n.Key, nn, t.newFlag()}, nil
}
// Otherwise branch out at the index where they differ.
branch := &fullNode{flags: t.newFlag()}
var err error
// 우선 기존의 root를 branch.Children에 재귀적으로 insert.
_, branch.Children[n.Key[matchlen]], err = t.insert(nil, append(prefix, n.Key[:matchlen+1]...), n.Key[matchlen+1:], n.Val)
if err != nil {
return false, nil, err
}
// 사용자가 입력한 key/value를 branch에 insert
_, branch.Children[key[matchlen]], err = t.insert(nil, append(prefix, key[:matchlen+1]...), key[matchlen+1:], value)
if err != nil {
return false, nil, err
}
// Replace this shortNode with the branch if it occurs at index 0.
if matchlen == 0 {
return true, branch, nil
}
// ...
// Replace it with a short node leading up to the branch.
return true, &shortNode{key[:matchlen], branch, t.newFlag()}, nil
case *fullNode:
dirty, nn, err := t.insert(n.Children[key[0]], append(prefix, key[0]), key[1:], value)
if !dirty || err != nil {
return false, n, err
}
n = n.copy()
n.flags = t.newFlag()
n.Children[key[0]] = nn
return true, n, nil
case nil:
// ...
return true, &shortNode{key, value, t.newFlag()}, nil
// ...
}
}-
이제 다시 테스트 코드의 코드를 한 줄씩 살펴보자
-
updateString(trie, "doe", "reindeer")
처음 호출에서 root는 nil이기 때문에 insert 메서드에서 case nil 실행된다.
)
-
updateString(trie, "dog", "puppy")
- 두 번째 호출에서 root는 shortNode 타입이다. 그리고 기존의 key와 현재 key는 prefix가 2개 일치한다.
- 새로운 shortNode가 할당되고 key는 prefix로 갖는다
- shortNode의 value로 fullNode가 할당된다.
- "e", "g" 는 fullNode의 Children노드로 할당된다.
- 두 번째 호출에서 root는 shortNode 타입이다. 그리고 기존의 key와 현재 key는 prefix가 2개 일치한다.
-
updateString(trie, "dogglesworth", "gglesworth")
-
기존의 root key인 len(key) 현재 "dogglesworth"의 prefix의 길이인 mathlen이 같다
-
따라서 insert 메서드의 다음 부분이 실행된다
-
-
t.insert를 호출하는 param를 살펴보자
- n.Val 은 fulNode가 된다.
- 기존의 prefix nil이기 때문에 현재는 key의 일치하는 부분만 prefix로 취한다. ("do")
- key는 key[matchlen:] 이므로 "gglesworth"가 된다.
- value는 그대로 가져간다
-
다음 t.insert를 호출하면 node가 fullNode 타입이므로 다음 부분이 실행된다.
-
- t.insert를 호출하는 param를 살펴보자
- n.val 은 shortNode이다. ("dog"/"puppy")
- prefix는 "do" + "g" 이다
- key는 "glesworth"이다
- value는 그대로 가져간다.
-
다음 t.insert를 호출하면 shortNode부분이 실행된다.
- prefix는 "dog" 이고 key는 "glesworth" 이므로 matchlen은 0
- 따라서 새로운 fullNode를 생성한다.
- 여기서 fullNode.Children[16]은 valueNode로 "puppy"가 된다.
- fullNode.Children에 shortNode를 할당한다. ("glesworth"/"cat")
-
-
-
-
결과물
-
Hi