Good data structure for efficient insert/querying on arbitrary properties

I'm wor开发者_开发百科king 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?

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.

Why can't you put your data into several dictionaries? One dictionary maps name to the data, another maps age, etc.

I assume all the arrays are of IEnumerable?

How about using LINQ to objects?

http://www.beansoftware.com/ASP.NET-Tutorials/Linq-Objects-Collections-Arrays.aspx

Then you can write query like LINQ syntax to get results from your arrays.