Hualiang's Blog

目前实现的 Succinct Trie 结构，对于长字符串（UUID）场景查询性能较差，仅有 FSA 的一半。因此这次我将介绍一种自己琢磨出来的优化思路，关于 Succinct Trie 是如何实现“路径压缩”来加速搜索的。

最近在学习 ElasticSearch 的 FST 索引结构发现，它的底层实现结构依然有对象头和指针的开销，如果能把这部分开销去掉，压缩率还能再上一层楼。于是经过调研发现一类叫“简洁数据结构”的结构，实现了占用极小且查询高效。遂深入探索，于是就有了这篇文章。