B+Trees vs. LSM Trees: How Ethereum Clients Choose Their Database TODO
Concept
A B+tree keeps sorted keys in page-sized nodes and updates them in place, so read amplification is low and range scans come naturally, but random writes turn into random page writes, driving up write amplification and page-split cost. An LSM tree buffers writes into an in-memory table and flushes them sequentially as SSTables, cleaning up with background compaction — giving high write throughput, at the cost of a single key being scattered across multiple levels (raising read amplification, mitigated with Bloom filters) and compaction causing latency spikes and space amplification. Ethereum's state sits on top of a key-value store as a Merkle Patricia Trie, which produces a random, write-skewed access pattern, since every block rewrites the whole path of nodes up to the root. That's why the Geth line has relied on LSM-based storage (LevelDB, later Pebble), while Erigon chose to restructure state around flat key layout with the B+tree-based MDBX, trading toward lower read amplification and disk usage. In the end the choice comes down to the workload's read/write ratio, access locality, and how much space amplification is tolerable.
Slow node sync or exploding disk usage is usually not an application-logic problem — it's a mismatch between the storage engine's amplification characteristics and the actual access pattern.
Code & Formula
# B+트리 vs LSM → 이더리움 클라이언트의 DB 선택 — 랜덤 쓰기 워크로드에서 두 구조의 실제 디스크 비용을 비교한다.
# B+트리는 갱신마다 랜덤 페이지 쓰기, LSM은 순차 flush + 백그라운드 컴팩션으로 대가를 뒤로 미룬다.
import math
import random
random.seed(1)
PAGE_SIZE = 4096
N_WRITES = 2000
KEY_SPACE = 500 # 키 공간이 작을수록 같은 페이지가 자주 재기록된다 (지역성 ↑)
def bplus_tree_cost(n_writes, key_space, page_size=PAGE_SIZE, keys_per_page=64):
# 단순화: 랜덤 키 쓰기마다 그 키가 속한 페이지 하나를 통째로 다시 쓴다 (in-place 갱신)
total_page_writes = 0
for _ in range(n_writes):
key = random.randint(0, key_space - 1)
_page = key // keys_per_page
total_page_writes += 1
return total_page_writes * page_size
def lsm_cost(n_writes, record_size=64, level_multiplier=4):
logical = n_writes * record_size
# flush 1회 + 레벨을 타고 내려가며 평균 level_multiplier배 정도 재기록된다고 근사
amplification = 1 + math.log(max(n_writes // 100, 1), level_multiplier)
return logical * amplification
bplus_bytes = bplus_tree_cost(N_WRITES, KEY_SPACE)
lsm_bytes = lsm_cost(N_WRITES)
print(f"랜덤 쓰기 {N_WRITES}건, 키 공간 {KEY_SPACE} (지역성 낮음)")
print(f"B+트리 예상 디스크 기록량: {bplus_bytes:,} bytes (페이지 단위 랜덤 쓰기)")
print(f"LSM 예상 디스크 기록량: {lsm_bytes:,.0f} bytes (순차 flush + 컴팩션 증폭)")
print("→ 랜덤 쓰기 편중 워크로드일수록 LSM이 유리한 이유: 쓰기를 순차화해 증폭을 뒤로 미룬다")
docs/code/algorithms/algorithms-72.py
Exercise
Run the same key-value workload — random-write-heavy vs. range-read-heavy — against both an LSM-based store and a B+tree-based store, and compare throughput, disk usage, and latency distribution.
Practical Connection
Append-heavy data with lots of time-range queries, like prediction-market event logs and execution history, favors the LSM family; random-read-heavy data, like per-account position lookups, calls for a different index structure.
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.