如何优化C#中基于Dictionary实现的Trie字典树的内存占用？

1. 替换高开销的Dictionary子节点存储 #

C# 原生Dictionary<int, TrieNode>的内存开销极高：每个实例自带对象头、哈希表数组、条目结构体等额外开销，空Dictionary在64位运行时就占至少48字节，有效数据存储占比极低。
优化方式：

• 将Children替换为List<KeyValuePair<int, TrieNode>>，插入时保持key有序，查询时用二分查找匹配键。当单节点子节点数量小于20个时，二分查找的性能甚至高于哈希查找，内存开销可降低70%以上。
• 若部分节点子节点数量确实很大，可以做自适应存储：子节点数小于阈值用列表，大于阈值自动切换为Dictionary。

2. 移除冗余存储，精简TrieNode结构 #

• 不要将结束标记endSymbol存在Children字典中，给TrieNode单独加一个bool IsEnd字段，仅占1字节，同时减少了每个结束节点的1条字典条目开销。
• 如果全局字符串映射后的唯一值总数少于65536，可将映射的int类型替换为ushort，key的存储占用直接减半。

3. 避免冗余路径存储 #

当前你实现的类名为SuffixTrie，但你的使用场景是整行完全匹配，不需要存储所有后缀路径。确认你插入节点时仅插入完整行的完整路径，不要重复插入同一行的多个后缀，否则会产生数倍的冗余节点。

4. 用结构化索引替代Trie结构（适配你的通配符场景） #

你的通配符是单位置匹配任意值，完全可以用位图索引方案大幅降低内存：

• 为每一列的每个唯一值生成一个位图，每一位对应一条规则行，该位为1表示对应规则行的当前列取值等于这个唯一值。
• 额外为每一列生成一个通配符位图，对应所有该位置为*的规则行。
• 校验待匹配行时，取每一列对应值的位图和通配符位图做OR操作，再将所有列的结果做AND操作，最终位图中若存在1位为1则匹配成功。
  100万条规则的单张位图仅占约122KB，就算15列、每列有1000个唯一值，总内存占用也不会超过200MB，远低于当前3-4GB的开销，且5000行校验的性能完全达标。

5. 值类型化节点减少对象开销 #

如果要继续使用Trie结构，可以将所有节点存储在一个预分配的TrieNode[]大数组中，Children存储的是数组下标（int类型，4字节）而非TrieNode的引用（64位系统占8字节），既消除了大量引用类型对象的对象头开销，也降低了GC压力，内存可再省30%左右。

内容的提问来源于stack exchange，提问作者SamuraiJack