Лучшая структура данных для хранения объекта, индексированного 3-мя кортежами, для быстрого поиска по каждому измерению и низкому профилю памяти?

Question

Я хочу хранить объекты, проиндексированные с помощью трех кортежей (String, String, DateTime). Давайте назовем их Идентификатор, Категория, День

Любой объект в структуре данных гарантированно будет уникальным с помощью трех кортежей (без дубликатов)

Структура данных должна поддерживать быстрые ответы на такие вопросы, как:
- Каковы все уникальные идентификаторы?
- Какие категории для идентификатора "xyz"?
- В какие дни идентификатор = "xyz" и категория "mycategory"?

Удаление также возможно. Было бы здорово поддерживать низкий профиль памяти.

В качестве базовой линии я использую Dictionary >>

Теоретически это должно дать мне O (1) поиск, но я не знаком с внутренностями словаря и, как правило, у меня есть ощущение, что мое решение не оптимально.

Я знаю, что, возможно, здесь нет единственно правильного ответа, и я мог бы предоставить множество деталей об использовании, но, возможно, кто-то может просто дать мне несколько идей для игры?

Редактировать
Единственный поиск выполняется с равенством (т.е. identiifer = "xyz"). Я не использую неравенства (больше, меньше, и т. Д.)

Answer 1

Это зависит от относительного количества значений в каждом столбце, их распределения и распределения запросов, поэтому лучшего ответа нет.

Ваши словари хороши для поиска по одному измерению, но вам придется выполнять линейный поиск, если вы хотите комбинацию функций.

Если бы пространство не было проблемой, вы могли бы иметь трехуровневый индекс (либо деревья, либо хеш-таблицы), чтобы сначала получить элементы по 1 измерению, а затем использовать словарь в этом узле, чтобы найти все элементы по второму измерению со значением для измерения 1, затем используйте словарь в этом узле, чтобы найти все элементы со всеми 3 значениями.

Это также имеет значение, если вы хотите отвечать на запросы, используя неравенства. В этом случае дерево лучше словаря, потому что оно упорядочено.

Answer 2

, так как вы добавили тег .NET 4.0, я предполагаю, что вы находитесь в .NET 4.0, так почему бы не Dictionary<Tuple<T1,T2,T3>,object>