Concurrent SortedList or O(log n) concurrent collection

Question

I need to cache a lot of data from database in ASP.NET MVC application and would like to use SortedList. I know .NET 4.0 added concurrent collections but there is no sorted collection. I was thinking to use SynchronizedCollection, but it is intensively using locks even for reads (if I am not mistaken), so I am looking for other options. Basically I need a concurrent collection with O(log n) access complexity.

EDIT - Code based on Greg's answer

void WrappedAdd(TKey k, TValue v)
{
  var copy = new SortedList<TKey, TValue>(_sortedList);
  copy.Add(k, v);
  _sortedList = copy;
}

Answer 1

Your requirements are pretty vague, so I don't really know what you want. Is the collection supposed to have indexing? Key-value semantics?

I'm not sure if this fits with what you want, but you could use the new Microsoft immutable collections library. It's currently available on NuGet as a preview. It contains sorted collections (sorted sets and dictionaries), among other things.

These collections aren't concurrent themselves (in fact, concurrency is a non-issue; they can't be modified). However, you can use them in a concurrent setting by wrapping them, and using a lock during a write. Reading is thread-safe because the only mutation is assigning a reference, which is an atomic operation, so you're guaranteed to get the most up to date results you possibly could.

They're tree-based so most operations are log n.

public class ConcurrentWrapper<TKey, T> {
    ImmutableSortedDictionary<TKey, T> _inner;

    public void Add(TKey key, T item) {
        lock (_inner) {
            _inner = _inner.Add(key, item);
        }
    }

    public T Get(TKey key) {
        return _inner[key];
    }
}