Оптимальная структура данных для специального словаря

Какая структура данных лучше всего с точки зрения вычислительной сложности для реализации словаря элементов (key, val), который должен поддерживать только следующие команды:

1. Insert (key) - добавляет элемент (key, val) с val = 1
2. Increment (key) - увеличивает значение val существующего (key, val)
3. Find (key) - возвращает значение (key, val)
4. Select (part_of_key) - возвращает список всех элементов (key, val), если strstr (key, part_of_key)! = NULL в форме нового словаря того же типа (по возможности без выделения новой памяти); например, если словарь {(красный, 3), (синий, 4), (зеленый, 1)}, то Select (re) = {(красный, 3), (зеленый, 1)}
5. Макс (i ) - возвращает элемент, имеющий i-е максимальное значение среди всех элементов; например, если словарь {(красный, 3), (синий, 4), (зеленый, 1)}, то Макс (1) = синий, Макс (2) = красный, Макс (3) = зеленый

ключи - это строки, а значения - положительные целые числа. Ожидается, что количество элементов в словаре будет очень большим.

Я думаю, это должен быть синтез двух разных структур данных. Но должна ли это быть хеш-таблица + двоичное дерево или trie + отсортированный массив или что-то еще?