---
title: SlimTrie 适合静态数据索引，不适合高频状态更新
date: '2019-03-15 18:28:23'
draft: false
summary: SlimTrie 省内存的前提，是把 Trie 建在静态数据之上；一旦回到需要增量更新的状态场景，这个优势就很难直接继承。
slug: slimtrie-for-static-state-index
syndication:
- platform: Weibo
  url: https://weibo.com/1648815335/Hl3fniwpL
tags:
- trie
- data-structure
- blockchain
- ethereum
topics:
- blockchain
type: post
---

得空看了下 `@drdrxp` 那天发的 `SlimTrie`。它的结构和以太坊实现的 `Patricia Trie` 挺像，都是为了压缩 `Trie` 的深度，选择用 `4 bit` 的 `word` 做分支单位。

这里的取舍其实很直觉：

- 如果只用 `1 bit`，每层只有两个分支，树会很深。
- 如果直接用 `1 byte`，每层会有 `256` 个分支，节点又太稀。
- `4 bit` 其实是在深度和分支数之间取了个折中。

但 `SlimTrie` 真正省内存的原因，不只是分支设计，而是它的使用前提：它假设数据是静态的，不需要频繁动态修改。

所以它放弃了通过指针来组织 `Trie`，改成压缩数组。因为数据不变，节点可以先整体编号，再按 `id` 顺序存到数组里。这样做，内存布局会更紧凑，也更容易压缩。

问题是，这种优势是有代价的。

如果要往 `SlimTrie` 里增加数据，就不能像普通 `Trie` 那样做局部增量更新。你得先恢复出原始 `Trie`，插入新数据，然后重新排序、重新压缩。新增节点会导致大量节点顺序变化，所以它并不适合那种持续变化的在线状态。

这也是我看到它之后第一个想到的限制：它更适合给归档后的历史数据建立查询索引，而不是直接拿来承载持续变化的区块链全局状态。

比如，如果想把它直接拿来压缩以太坊的 `Global State Trie`，问题就来了：以太坊每个区块都可能更新状态树。你要是每个区块之后都全量重压一次，成本会很高。我现在还没想到一个特别自然的办法，把这套结构平滑地用到这种高频更新场景里。

另外，它的节点数还有上限，最多支持 `2**16` 个节点。要存更多数据，就得在 `Trie` 外面再套一层 `Trie`，不够就继续套。

所以我对 `SlimTrie` 的判断是：它很有意思，但它解决的是“如何给静态数据建立紧凑索引”的问题，而不是“如何维护一个可高频更新的状态树”的问题。这两个场景看起来相近，约束其实差得很远。