How to index collection by using composite key

Question

I have this class

public class Item
{
    public int UniqueKey;
    public int Key1;
    public int Key2;
    public int Key3;
    public int Key4;
    public string Value;
}

and the collection IEnumerable<Item>

I want to create indexes on items of this collection by Key1, or by Key2, or composite one (Key1 and Key4). The number of items in collection is about 10 000 or more. The main goal is performance. Multiple callers can have many read / one write access. Returned collections should be guarded (protected from external modification). Could somebody explain any solution, pattern, what collection classes I have to use to implement.

I have rejected the variant of using database table's indexes, because of some reasons (performance and so on).

Answer 1

You can use LINQ to return a collection indexed by a property:

var key1 = from i in Items 
           group i by i.Key1 into g
           select g;

var key2 = from i in Items
           group i by i.Key2 into g
           select g;
...

Since you have a small, deterministic list of keys, you could implement a class that exposes the groups for read as IEnumerable or List properties. Add a single method for adding items to the collection (no need for separate methods since they'll get grouped for reading based on their value.) Use the lock keyword in your Add method to protect the item collections while adding.

Answer 2

You could group the items using an anonymous type and create a dictionary with the groups:

var grouped = items.GroupBy(item => new { item.Key1, item.Key4 })
                   .ToDictionary(g => g.Key, g => g.ToList());

However, anonymous types can only be used for local variables (or generic method parameters), so if you're going to store the dictionary for later reuse, you will need a non-anonymous type. So you can either create types for each possible key combination, or use the Tuple class :

Dictionary<Tuple<int, int>, Item> grouped =
              items.GroupBy(item => Tuple.Create(item.Key1, item.Key2))
                   .ToDictionary(g => g.Key, g => g.ToList());

Answer 3

You can use two mappings: one for the store and one as a lookup table to the primary key. As all updates use the primary key which should be fixed, you can use lock stripping to allow concurrent writes. In this form a writer must acquire a lock (primaryKey mod # locks) so that an updates/removes do not race for an entry. And, of course, reads don't need locking if the backing dictionaries are concurrent.

You can see a Java version of this idea which was hidden behind a caching facade to provide a nice API.