如何高效存储百万单词并支持前缀、包含、后缀及乱序匹配查询

百万级规模的词库根本不需要靠数据库扛性能，90%以上的同类站点都会选内存存储方案：常用英文词库算上各类变体、生僻词也就百万条量级，全量加载到内存占用不到100MB，比走数据库网络IO、查索引的速度高两个数量级，实现还更简单。

基础字符串匹配（starts_with/ends_with/contains） #

• 内存实现：
  前缀匹配直接预构建Trie（前缀树），查询时顺着树结构遍历查询串，O(k)复杂度就能拿到所有匹配词（k是查询串长度），几乎无延迟。后缀匹配更简单，预存时把每个单词反转后再建一份Trie，查后缀时把查询串反转，走和前缀查询完全一样的逻辑就行。
  多字符包含（比如同时含c和d的单词）直接预建字符倒排索引：每个字符对应一个存储单词ID的集合，查询时把多个字符对应的集合做交集就能拿到结果；子串包含如果嫌遍历慢，补个后缀数组或者滚动哈希索引就行，实现成本极低。
• PostgreSQL实现：
  前缀匹配直接给单词字段建普通B树索引，支持word LIKE 'xxx%'的快速查询；后缀匹配给单词加个反转值字段，同样建B树索引，匹配reverse(word) LIKE 'xxx%'即可；包含匹配开pg_trgm扩展建GIN索引，就能高效跑LIKE '%xxx%'，多字符包含可以把单词拆成字符数组存，用数组交集运算符配合GIN索引查询，性能完全满足线上需求。

乱序重组匹配（输入CAUDK匹配duck这类同字母异序查询） #

你提到的「单词排序后存入内存」的思路就是这类查询的最优解，只是核心不是给单词本身排序，而是给每个单词预计算字符签名：

1. 把每个单词的所有字符统一转小写后按字典序排序，保留重复字符，比如duck拆成字符是d、u、c、k，排序后得到cdku，这就是这个单词的签名；像eat/ate/tea三个词排序后签名都是aet，直接把相同签名的单词存在哈希表的同一个key下。
2. 查询时，先把用户输入的字符串做完全一样的处理：转小写、按字典序排序得到查询签名，直接拿这个签名去哈希表里查，O(1)复杂度就能拿到所有匹配的单词，连遍历都不需要。
   如果要支持「输入N个字母，匹配所有可由这些字母子集拼成的单词」（比如输入5个字母找所有3、4、5个字母的可组合词），只需要枚举输入字符所有长度≥2的子集，每个子集算签名查哈希表，最后去重就行——5个字母的有效子集也就20多个，查20多次哈希表总耗时不到1毫秒，比全量遍历快几十倍。

• PostgreSQL实现乱序查询同样简单：给单词表加个signature字段存预计算的排序签名，给字段建B树索引，查询时把用户输入排序后直接匹配signature = 'cdku'即可；子集匹配可以把签名存为字符计数数组，用数组包含运算符@>配合GIN索引就能快速查询。

百万级词库全量遍历确实能跑，单次查询大概十几到几十毫秒，对用户来说感知不强，但预构建上述索引的额外内存开销不到原词库的30%，能把所有查询的耗时压到1毫秒以内，并发能力能提升上百倍，完全没必要省这点功夫。

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