Good data structure for efficient insertion / query on arbitrary properties

Question

I am working on a project in which Arrays is the default data structure for everything, and each query is a linear search in the form:

• Do you need a client with a specific name? customer.Find(x => x.Name == name)
• Do I need a client with a unique identifier? customer.Find(x => x.Id == id)
• Do you need a client of a certain type and age? customer.Find(x => x is PreferredCustomer && x.Age >= age)
• Do you need a client of a certain name and age? customer.Find(x => x.Name == name && x.Age == age)

In almost all cases, the search criteria are well defined. For example, we are only looking for customers by one or more of the properties Id, Type, Name or Age. We rarely look for anything else.

Good data structure to support arbitrary queries of these types with better search than O (n)? Any ready-made versions of .NET?

Answer 1

In memory you have several options.

Most options will have O (n). In this case, dictionary search queries can approach O (1).

One option is to store your customers in several dictionaries, each with a key set to name, identifier and age. If you use the same object references in dictionaries, you can do any O (1) search without a huge amount of overhead.

Of course, this becomes less practical as the number of your criteria increases, but with 3, this is not so bad.

If you need more flexibility, then a database is an option. Many databases have the ability to work as a fully integrated database, including SQLite, which allows arbitrary queries much better than O (n).

Answer 2

Why can't you put your data in multiple dictionaries? One dictionary matches the name with the data, another age of the map, etc.

Answer 3

I assume all arrays have an IEnumerable value?

How to use LINQ for objects?

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

You can then write a query similar to LINQ syntax to get results from your arrays.