概念前缀树 / 字典树
Trie
一种树形数据结构，用于高效存储和检索字符串集合。将字符串按字符逐层分解，共享公共前缀，查询复杂度仅与前缀长度相关，常用于自动补全、拼写检查等场景。
时间轴 (近 90 天)
9月12日
将 Trie 节点按 BFS（广度优先）顺序序列化为连续字节数组，可使父子节点在物理内存上相邻，配合缓存预取提升数据局部性
待验证50%
9月12日
将子节点索引从 64 位指针压缩为 32 位偏移量既节省内存又能让同一 64 字节缓存行容纳更多索引信息
待验证50%
9月10日
Trie（前缀树）由Edward Fredkin在1960年提出
待验证50%
9月9日
Trie前缀树查询的时间复杂度为O(m)，其中m是查询字符串长度，与数据总量无关
待验证60%
9月9日
Trie由Edward Fredkin在1960年提出
待验证50%
9月9日
将Trie节点内存布局设计为数组连续存储并按访问模式对齐缓存行边界，可以将cache miss率降低50%以上
待验证50%
全部知识事实 (6)
待验证
Trie前缀树查询的时间复杂度为O(m)，其中m是查询字符串长度，与数据总量无关
60%待验证将 Trie 节点按 BFS（广度优先）顺序序列化为连续字节数组，可使父子节点在物理内存上相邻，配合缓存预取提升数据局部性
50%待验证将子节点索引从 64 位指针压缩为 32 位偏移量既节省内存又能让同一 64 字节缓存行容纳更多索引信息
50%待验证Trie（前缀树）由Edward Fredkin在1960年提出
50%待验证Trie由Edward Fredkin在1960年提出
50%待验证将Trie节点内存布局设计为数组连续存储并按访问模式对齐缓存行边界，可以将cache miss率降低50%以上
50%