What is the difference between SortedDictionary<TKey,TValue> and SortedList<TKey,TValue> in C#? How is each implemented, what are the costs of insert, lookup and enumeration, and how do you choose between them (and versus Dictionary)?

1. Red-black trees in brief

A red-black tree is a binary search tree with extra rules that keep it approximately balanced:

1. Every node is red or black; the root is black.
2. Red nodes can't have red children.
3. Every path from a node to its descendant leaves has the same number of black nodes.

These rules guarantee the longest path is at most twice the shortest, so height is O(log n). Inserts and deletes restore the rules with recolouring and at most a few rotations — O(log n) worst case.

.NET's implementation (SortedSet<T>, used by SortedDictionary) uses top-down insertion and deletion, splitting 4-nodes on the way down, and each node is a class:

internal sealed class Node { public T Item; public Node? Left; public Node? Right; public NodeColor Color; }

For SortedDictionary<int,int>, each entry costs a node object (~48 bytes on 64-bit including header and the KeyValuePair), and traversal follows references scattered across the heap — more cache misses than array-based structures.

2. SortedList internals

private TKey[] keys;
private TValue[] values;
private int _size;
private readonly IComparer<TKey> comparer;

• TryGetValue: Array.BinarySearch(keys, 0, _size, key, comparer) — O(log n) comparisons, and binary search over contiguous memory is cache-friendly for small-to-medium sizes.
• Add(key, value): binary search for the insertion point; if the key exists, throw; otherwise Array.Copy both arrays one slot to the right from that point, then write. Inserting at the end (keys arriving in ascending order) has nothing to shift.
• Capacity doubles when full, like List<T>.
• Keys and Values return IList<T> views supporting index access; GetKeyAtIndex(i) / GetValueAtIndex(i) / SetValueAtIndex(i, v) (.NET 7+) give direct access.

3. Comparers

Both types take an IComparer<TKey>:

• Default: Comparer<TKey>.Default, which uses IComparable<T>. For strings this is culture-sensitive — sorted order and even key equality (Compare == 0) depend on the current culture. Pass StringComparer.Ordinal (or OrdinalIgnoreCase) for identifiers.
• Equality is defined by the comparer returning 0, not by Equals. A comparer that ignores part of the key will merge distinct keys.
• Descending order: Comparer<T>.Create((a, b) => b.CompareTo(a)).

4. Performance intuition

For n = 100,000 random integer keys (rough relative numbers on a modern CPU):

Always benchmark with your key type and comparer — string comparisons with culture rules can dominate everything.

5. Alternatives worth knowing

• Sorted array + BinarySearch: smallest and fastest for read-only data; ~index gives the insertion point for range queries.
• ImmutableSortedDictionary<TKey,TValue>: AVL-tree-based persistent map for sharing snapshots across threads.
• PriorityQueue when you only need the minimum/maximum repeatedly, not full ordering.
• Database indexes: for large or persistent ordered data, let SQL Server do the sorting and range scanning.

Try it yourself

1. Benchmark inserting 100,000 random vs ascending keys into SortedList and SortedDictionary.
2. Measure memory for each with GC.GetTotalMemory or a memory profiler.
3. Implement "next key greater than X" with SortedList using binary search on Keys.
4. Create a SortedDictionary<string, int> with the default comparer under tr-TR culture and insert "I" and "ı".

// Tiered rates loaded once in ascending order: SortedList
var tiers = new SortedList<decimal, decimal>
{
    [0m] = 0.10m,
    [1_000m] = 0.08m,
    [10_000m] = 0.05m,
};

decimal RateFor(decimal amount)
{
    // floor lookup: largest key <= amount, using binary search on Keys
    IList<decimal> keys = tiers.Keys;
    int lo = 0, hi = keys.Count - 1, best = 0;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (keys[mid] <= amount) { best = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return tiers.Values[best];
}

// Frequent random inserts and removes: SortedDictionary
var orderBook = new SortedDictionary<decimal, int>(
    Comparer<decimal>.Create((a, b) => b.CompareTo(a)));   // highest price first
orderBook[101.5m] = 300;
orderBook[99.0m] = 150;
orderBook.Remove(101.5m);

foreach (var (price, qty) in orderBook)
    Console.WriteLine($"{price}: {qty}");                  // key order

// Index access only on SortedList
Console.WriteLine(tiers.Keys[^1]);                        // highest threshold
Console.WriteLine(tiers.IndexOfKey(1_000m));              // 1