概念Prefix Tree / Trie

前缀树

一种树形数据结构，将缓存的 KV 按 token 序列组织，支持任意长度公共前缀的命中与复用，用于提升多用户多模板场景下的缓存命中率

时间轴 (近 90 天)

10月12日

前缀树（Trie）将缓存的 KV 按 token 序列组织成树形，多个请求只要共享任意长度的公共前缀就能命中并复用 KV，不要求整段前缀完全一致。

待验证50%

9月9日

Trie前缀树查询的时间复杂度为O(m)，其中m是查询字符串长度，与数据总量无关

待验证60%

Trie前缀树查询的时间复杂度为O(m)，其中m是查询字符串长度，与数据总量无关

前缀树（Trie）将缓存的 KV 按 token 序列组织成树形，多个请求只要共享任意长度的公共前缀就能命中并复用 KV，不要求整段前缀完全一致。