我认为一个有效的数据库将是一个修改过的trie，具有双向链接[可以从叶子到根并重建单词]，并且每个终止节点都会有额外的“值”字段。
您还需要一个多重映射[即一个映射，其中每个值都是一组地址]。
键将像树一样排列，值集将基于散列。[在jave中，应该是这样的TreeMap<Integer,HashSet<Node>>]
伪代码：[嗯，非常伪......它只是显示了每个操作的一般想法]。
Insert(key):
1. Insert a word into the trie
2. add the value `1` to the terminating node.
3. add the terminating field to the multimap [i.e. map.add(1,terminating_node_address)]
Increment(key):
1. read the word in the trie, and store the value from the terminating node as temp.
2. delete the entree (temp,terminating_node_address) from the multimap.
3. insert the entree (temp+1,terminating_node_address) to the multimap.
4. increase the value of the terminating node's address by 1.
Find(key):
1. find the terminating node for the key in the trie, return its value.
Select(part_of_key):
1. go to the last node you can reach with part_of_key.
2. from this node: do BFS and retrieve all possible words [store them in an empty set you will later return].
Max(i):
1. find the i'th biggest element key in the multimap.
2. choose an arbitrary address, and return get the relevant terminating word node.
3. build the string by following the uplinks to the root, and return it.
复杂性：
设为n字符串的数量、k最大值和S字符串的长度。
插入：O(S) [trie 插入是 O(S)]。地图中的最小元素 (1) 可以被缓存，因此可以在 O(1) 时访问。
增量：O(S+logk)：在trie中找到字符串是O(S)，找到相关键是O(logk)，从哈希集中删除元素是O(1)，找到下一个元素树也是 O(logk) [实际上可以是 O(1)，对于基于跳过列表的地图]，插入一个值是 O(1)。请注意，通过将节点链接到映射中的相关键，复杂性甚至可以提高到 O(S)，因为实际上不需要搜索。
查找：O(S)：只需在 trie 中找到并返回值。
Select: O(S*n)：在最坏的情况下，您需要检索所有元素，这会强制您迭代整个 trie 以找到所有单词。
Max: O(logk+S) : 在有序映射中找到一个键，重构这个词。
编辑：请注意，在这里，我假设 find(i) 你想要第 i 个不同的最大元素。如果不是这种情况，您将需要稍微修改集合，并使用允许重复键的多映射 [而不是将集合作为值]。这将使所有基于树的操作 O(logn) 而不是 O(logk)，在我看来仍然有效......