Deep Storage Performance Comparison

1Regular Binary Tree (BST):
2  Node stores: value + left pointer + right pointer
3  Search: compare at each node (balanced = O(log n))
4
5Trie:
6  Node stores: children indexed by KEY CHARACTERS
7  Search: follow the key characters one by one
8  
9Example - Ethereum 16-way trie:
10  Key = "a7f3..." (hex characters 0-f)
11  Root → [a] → [7] → [f] → [3] → ... → leaf (account data)
12  Each step: pick the next nibble, follow that branch

1// User wants: account data for address 0x742d35...
2// Step 1: Hash the address
3key = keccak256(0x742d35Cc6634C0532925a3b844Bc454e4438f44e)
4    = 0xabc1234567890abc1234567890abc1234567890abc1234567890abc1234567890
5
6// Step 2: Convert to nibbles (each hex char = one nibble)
7nibbles = [a, b, c, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, a, b, c, ...]
8           ↑  ↑  ↑  ↑                            total: 64 nibbles
9
10// Step 3: Traverse the 16-way trie, one nibble at a time
11root → [a] → [b] → [c] → [1] → ... → leaf (account state)
12
13// Result: 64 steps deep, completely random order
14// No two related addresses will be "near" each other in the trie

1// User wants: Balances pallet, Account storage, for Alice
2// Step 1: Hash each part separately
3pallet_hash   = Twox128("Balances")        // = 0x26aa394eea5630e07c48ae0c9558cef7
4storage_hash  = Twox128("Account")         // = 0xb99d880ec681799c0cf30e8886371da9
5key_hash      = Blake2_128Concat(Alice)    // = 0xde1e86a9a8c739864cf3cc5ec2bea59f...
6
7// Step 2: Concatenate all parts
8final_key = pallet_hash ++ storage_hash ++ key_hash
9          = 0x26aa394e...b99d880e...de1e86a9...
10
11// Key insight: ALL accounts in Balances pallet share the same PREFIX
12// → they are physically grouped together in the database
13// → cache hits are much more likely when reading multiple accounts

1// For EVERY node (branch, extension, leaf):
2DB_key   = keccak256(RLP(node))   // 32 bytes — hash of the encoded node
3DB_value = RLP(node)               // the full encoded node data
4
5// To look up any node, you:
6// 1. Receive a 32-byte hash reference
7// 2. Do a DB lookup with that hash as key
8// 3. Get back the RLP-encoded node
9// 4. Decode the RLP to get the actual children / value
10
11// Cost per node:  1 DB read + 1 RLP decode + 1 keccak hash verification
12// For a 64-nibble path: up to 64 nodes × (DB read + decode + hash)

1// Substrate uses the Patricia Merkle Trie (different from Ethereum's MPT)
2// Node structure:
3Node {
4  partial_key: Vec<u8>,       // compressed shared path
5  children: BTreeMap<u8, NodeRef>, // DYNAMIC — only used children stored
6  value: Option<Vec<u8>>,     // value if this is a leaf-level node
7}
8
9// Key difference: only USED children are stored
10// If only 2 of 16 positions are occupied, only 2 children exist
11// No wasted space for empty slots
12
13// DB storage:
14DB_key   = hash(encoded_node)   // 32 bytes
15DB_value = scale_encoded(node)  // SCALE codec — more compact than RLP

1// RLP Encoding Example
2// Encoding the string "cat":
3// 1. String length = 3
4// 2. Length prefix = 0x83 (0x80 + 3 for short strings)
5// RLP("cat") = 0x83 0x63 0x61 0x74
6
7// Encoding a list ["cat", "dog"]:
8// 1. Encode each item: 0x83636174, 0x83646f67
9// 2. Total payload length = 8 bytes
10// 3. List prefix = 0xc8 (0xc0 + 8 for short lists)
11// RLP(["cat", "dog"]) = 0xc8 0x83 0x63 0x61 0x74 0x83 0x64 0x6f 0x67
12
13// For a branch node with 16 children:
14// EACH child reference is a 32-byte hash
15// Plus length prefix for each + list prefix
16// Total branch node size: ~600+ bytes even when mostly empty
17
18// Why this is a problem:
19// Every node read = 1 RLP decode operation
20// Deep trie = many decode operations per lookup

1// SCALE Encoding Example
2// Encoding a u32 integer (e.g. 1000000):
3// SCALE: just the 4 bytes in little-endian
4// SCALE(1000000) = 0x40 0x42 0x0f 0x00
5
6// For a vector of bytes:
7// SCALE: compact-encoded length + raw bytes
8// No nested prefix like RLP — simpler structure
9
10// Substrate node encoding:
11// - partial_key length + partial_key bytes
12// - bitmask of which children exist (2 bytes)  ← KEY OPTIMIZATION
13// - only the hashes of EXISTING children
14// - optional value
15
16// Example sparse node (2 children out of 16):
17// RLP would encode 16 slots (mostly empty = 0x80 each) → ~530 bytes
18// SCALE: bitmask (2 bytes) + 2 hashes (64 bytes) → ~70 bytes
19// SCALE is ~7.5x smaller for sparse nodes!

1// Cost analysis for ONE account read in Ethereum:
2keccak256(address)        → 1 hash operation
3convert to 64 nibbles     → trivial
4traverse ~15-20 nodes:
5  × 15 DB reads           → disk seeks (expensive!)
6  × 15 RLP decodes        → CPU work
7  × 15 hash verifications → keccak per node
8final RLP decode (value)  → 1 decode
9
10// Total: ~15 disk reads + ~30 keccak operations + ~15 RLP decodes
11// In the WORST case (cold cache, deep path): ~20+ operations

1// Writing to Ethereum state (e.g. Alice sends Bob 1 ETH):
2
3// Step 1: Update Alice's leaf node
4alice_leaf_new = RLP([nonce+1, balance-1eth, storageRoot, codeHash])
5DB[keccak256(alice_leaf_new)] = alice_leaf_new
6
7// Step 2: Alice's parent branch node now has a new child hash
8parent_branch_new = [...15_children..., NEW_alice_hash, value]
9DB[keccak256(parent_branch_new)] = parent_branch_new
10
11// Step 3: The grandparent now has a new child hash
12// ... repeats all the way to root ...
13
14// Step N: New state root
15new_state_root = keccak256(new_root_node)
16
17// COST per write:
18// depth × (1 RLP encode + 1 keccak256 + 1 DB write)
19// For depth=15: 15 encodes + 15 hashes + 15 DB writes
20
21// Plus: OLD nodes stay in DB (for history) until pruning
22// So every write = 2× DB writes (old + new node versions)