¿Cuál es la diferencia entre SortedList y SortedDictionary?

Aquí está una vista tabular si ayuda...

A partir de un rendimiento de perspectiva:

+------------------+---------+----------+--------+----------+----------+---------+
| Collection       | Indexed | Keyed    | Value  | Addition |  Removal | Memory  |
|                  | lookup  | lookup   | lookup |          |          |         |
+------------------+---------+----------+--------+----------+----------+---------+
| SortedList       | O(1)    | O(log n) | O(n)   | O(n)*    | O(n)     | Lesser  |
| SortedDictionary | n/a     | O(log n) | O(n)   | O(log n) | O(log n) | Greater |
+------------------+---------+----------+--------+----------+----------+---------+

* Insertion is O(1) for data that are already in sort order, so that each 
  element is added to the end of the list (assuming no resize is required).

A partir de la aplicación de la perspectiva:

+------------+---------------+----------+------------+------------+------------------+
| Underlying | Lookup        | Ordering | Contiguous | Data       | Exposes Key &    |
| structure  | strategy      |          | storage    | access     | Value collection |
+------------+---------------+----------+------------+------------+------------------+
| 2 arrays   | Binary search | Sorted   | Yes        | Key, Index | Yes              |
| BST        | Binary search | Sorted   | No         | Key        | Yes              |
+------------+---------------+----------+------------+------------+------------------+

A aproximadamente paráfrasis, si usted requiere de rendimiento bruto SortedDictionary podría ser una mejor opción. Si usted requiere menor sobrecarga de la memoria y la recuperación indizada SortedList encaja mejor. Ver esta cuestión para obtener más información sobre cuándo utilizar.

Usted puede leer más aquí, aquí, aquí, aquí y aquí.

Me partió el Reflector a echar un vistazo a este como parece haber un poco de confusión acerca de SortedList. En realidad no se trata de un árbol de búsqueda binario, es una ordenados (clave) de la matriz de pares clave-valor. También hay un TKey[] keys variable que se ordena en la sincronización con los pares clave-valor y se utiliza para búsqueda binaria.

Aquí hay algunas de origen (de la orientación .NET 4.5) para copia de seguridad de mis reclamaciones.

Los miembros privados

// Fields
private const int _defaultCapacity = 4;
private int _size;
[NonSerialized]
private object _syncRoot;
private IComparer<TKey> comparer;
private static TKey[] emptyKeys;
private static TValue[] emptyValues;
private KeyList<TKey, TValue> keyList;
private TKey[] keys;
private const int MaxArrayLength = 0x7fefffff;
private ValueList<TKey, TValue> valueList;
private TValue[] values;
private int version;

SortedList.cto r(IDictionary, IComparer)

public SortedList(IDictionary<TKey, TValue> dictionary, IComparer<TKey> comparer) : this((dictionary != null) ? dictionary.Count : 0, comparer)
{
    if (dictionary == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.dictionary);
    }
    dictionary.Keys.CopyTo(this.keys, 0);
    dictionary.Values.CopyTo(this.values, 0);
    Array.Sort<TKey, TValue>(this.keys, this.values, comparer);
    this._size = dictionary.Count;
}

SortedList.Agregar(TKey, TValue) : void

public void Add(TKey key, TValue value)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    int num = Array.BinarySearch<TKey>(this.keys, 0, this._size, key, this.comparer);
    if (num >= 0)
    {
        ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
    }
    this.Insert(~num, key, value);
}

SortedList.RemoveAt(int) : void

public void RemoveAt(int index)
{
    if ((index < 0) || (index >= this._size))
    {
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index);
    }
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this.keys, index + 1, this.keys, index, this._size - index);
        Array.Copy(this.values, index + 1, this.values, index, this._size - index);
    }
    this.keys[this._size] = default(TKey);
    this.values[this._size] = default(TValue);
    this.version++;
}

Echa un vistazo a la página de MSDN para SortedList:

Desde la sección de Observaciones:

La SortedList<(Of <(TKey, TValue>)>) clase genérica es un árbol de búsqueda binario con O(log n) de recuperación, donde n es el número de elementos en el diccionario. En esto, es similar a la SortedDictionary<(Of <(TKey, TValue>)>) clase genérica. Las dos clases similares modelos de objetos, y ambos tienen O(log n) de recuperación. Donde las dos clases que se diferencian es en el uso de la memoria y la velocidad de inserción y eliminación:

• SortedList<(Of <(TKey, TValue>)>) utiliza menos memoria que SortedDictionary<(Of <(TKey, TValue>)>).

• SortedDictionary<(Of <(TKey, TValue>)>) tiene más rápido de inserción y las operaciones de extracción de datos sin ordenar, O(log n) frente a O(n) para SortedList<(Of <(TKey, TValue>)>).

• Si la lista se rellena de una vez por todas de datos ordenados, SortedList<(Of <(TKey, TValue>)>) es más rápido que SortedDictionary<(Of <(TKey, TValue>)>).

Esta es la representación visual de cómo las actuaciones comparar el uno al otro.