I need a data structure with O(log n) retrieval and O(1) lookup by index. So SortedList is the obvious choice.

Now I want to know the best way to make its methods thread-safe? Here is a partial implementation using lock, but I am wondering if there is a more efficient way? For example, if there were an immutable SortedList I could use that, but I can only see SortedDictionary offered as immutable.

public class ConcurrentSortedList<TKey, TValue>
{
    private object _locker = new object();
    private SortedList<TKey, TValue> _list = new SortedList<TKey, TValue>();

    public void Add(TKey key, TValue value)
    {
        lock(_locker)
        {
            _list.Add(key, value);
        }
    }

    public TValue GetByIndex(int index)
    {
        lock(_locker)
        {
            return _list.Values[index];
        }
    }
}

Edit. As pointed out below by @Theodor, getting by index seems useless in a multi-threaded environment, and I agree then that there is no point in trying to make SortedList tread-safe.