Tenho uma grande coleção de strings (até 1 milhão) em ordem alfabética. Eu experimentei consultas LINQ nessa coleção usando HashSet, SortedDictionary e Dictionary. Estou armazenando em cache estático a coleção, ela tem até 50 MB de tamanho e estou sempre chamando a consulta LINQ na coleção em cache. Meu problema é o seguinte:

Independentemente do tipo de coleção, o desempenho é muito menor que o SQL (até 200ms). Ao fazer uma consulta semelhante nas tabelas SQL subjacentes, o desempenho é muito mais rápido (5 a 10 ms). Eu implementei minhas consultas LINQ da seguinte maneira:

public static string ReturnSomething(string query, int limit)
{
  StringBuilder sb = new StringBuilder();
  foreach (var stringitem in MyCollection.Where(
      x => x.StartsWith(query) && x.Length > q.Length).Take(limit))
  {
      sb.Append(stringitem);
  }

  return sb.ToString();
}

Entendo que o HashSet, Dictionary etc. implementam pesquisas usando a pesquisa em árvore binária em vez da enumeração padrão. Quais são minhas opções para consultas LINQ de alto desempenho nos tipos avançados de coleção?