Good data structure for efficient insert/querying on arbitrary properties

Question

I'm working on a project where Arrays are the default data structure for everything, and every query is a linear search in the form of:

• Need a customer with a particular name? customer.Find(x => x.Name == name)
• Need a customer with a particular unique id? customer.Find(x => x.Id == id)
• Need a customer of a particular type and age? customer.Find(x => x is PreferredCustomer && x.Age >= age)
• Need a customer of a particular name and age? customer.Find(x => x.Name == name && x.Age == age)

In almost all instances, the criteria for lookups is well-defined. For example, we only search for customers by one or more of the properties Id, Type, Name, or Age. We rarely search by anything else.

Is a good data structure to support arbitrary queries of these types with lookup better than O(n)? Any out-of-the-box implementations for .NET?

Answer 1

For in memory, you have a few options.

Most options will be O(n). That being said, Dictionary lookups can approach O(1).

One option is to store your customers in multiple Dictionaries, each with a key set to the Name, Id, and Age. If you use the same object references in the dictionaries, you can make any single lookup O(1), without a huge amount of overhead.

Granted, this becomes less practical as your criteria count rises, but with 3, it's not too bad.

If you want more flexibility, then a database is an appropriate option. Many databases have the option of working as a completely in-memory database, including SQLite, which would allow arbitrary queries at much better than O(n) speed.