用10MB的FST替换3GB的SQLite数据库：一个意外发现的性能优化实战

一位开发者Andrew Quinn在自己的博客上分享了一个有趣的发现：他用一个仅10MB的FST（有限状态转换器）二进制文件，替换了原本占用3GB的SQLite词典数据库，查询速度反而更快了。这个故事在Hacker News上引发了关于”古老数据结构在现代场景下的价值”的热烈讨论。

背景：3GB的SQLite词典

Andrew Quinn在开发一个词典查询应用时，最初使用SQLite存储数据。随着词典数据量增长，数据库文件膨胀到了3GB。对于一个只需要”查词”功能的应用来说，这个体积实在太大了。

他的数据本质上是一个”键→值”的映射关系：给定一个单词，返回其释义。这类数据有一个特点——一旦构建完成就很少修改，属于典型的”读多写少”场景。

发现FST

FST（Finite State Transducer，有限状态转换器）是一种经典的数据结构，最早由Douglas McIlroy在2001年描述。它可以将一组有序的键值对压缩编码为一个紧凑的二进制文件，同时支持极快的精确查找和前缀查询。

Andrew偶然发现了这个方案，经过简单尝试后惊讶地发现：

• 体积：从3GB压缩到约10MB（压缩比超过300倍）
• 速度：查询速度与SQLite相当甚至更快，因为整个数据结构可以完全加载到内存中
• 简单性：一个二进制文件，无需数据库引擎

技术原理简述

FST的核心思想是将所有键共享的前缀和后缀合并存储，形成一个有向无环图（DAG）。对于词典这种天然具有大量公共前缀的数据，压缩效果尤为显著。

Hacker News上有评论指出，这种数据结构在Lucene搜索引擎中已经被使用了近20年。Lucene的倒排索引的term dictionary正是用FST实现的，这也是为什么Lucene能够在海量文本上实现毫秒级搜索的原因之一。

适用场景

FST特别适合以下场景：

• 静态或准静态数据：数据构建后很少修改，如词典、邮编映射、URL路由表
• 键值查找：需要快速精确匹配或前缀匹配
• 嵌入式或边缘场景：资源有限，不想引入完整的数据库引擎
• 搜索索引：Lucene/Elasticsearch的底层核心组件

实际尝试

如果你的数据是”读多写少”的键值对，可以考虑用FST替代SQLite。主流语言的实现：

• Rust：fst crate，由BurntSushi（Andrew Gallant）维护，是目前最成熟的实现
• Go：github.com/blevesearch/vellum
• Java：Lucene内置的FST实现
• Python：python-fst等绑定

Andrew Quinn在文末也提到，这次”偶然发现”之所以可行，是因为9个月前他选择了按字母顺序存储数据——这个当时看起来无关紧要的决定，为后来的优化埋下了伏笔。

本文参考来源：Andrew Quinn: Replacing a 3 GB SQLite db with a 10 MB FST | Hacker News讨论