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 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.