O Redis é para casos de uso em que você precisa acessar e atualizar dados com frequência muito alta e se beneficia do uso de estruturas de dados (hashes, conjuntos, listas, strings ou conjuntos classificados). Ele é feito para preencher casos de uso muito específicos. Se você tiver um caso de uso geral, como pesquisa muito flexível, será muito melhor servido por algo criado para esse propósito, como pesquisa elástica ou SOLR.
Dito isso, se você precisar fazer isso no Redis, veja como eu faria (supondo que os usuários possam compartilhar nomes e números de telefone):
name:some_name -> set([id1, id2, etc...])
name:some_other_name -> set([id3, id4, etc...])
phone:some_phone -> set([id1, id3, etc...])
phone:some_other_phone -> set([id2, id4, etc...])
id1 -> {'name' : 'bob', 'phone' : '123-456-7891', etc...}
id2 -> {'name' : 'alice', 'phone' : '987-456-7891', etc...}
Nesse caso, estamos criando uma nova chave para cada nome (com prefixo "name:") e cada número de telefone (com prefixo "phone:"). Cada chave aponta para um conjunto de IDs que contém todas as informações que você deseja para um usuário. Ao pesquisar um telefone, por exemplo, você fará:
HGETALL 'phone:123-456-7891'
e, em seguida, percorrer os resultados e retornar qualquer informação sobre cada (nome em nosso exemplo) em seu idioma de escolha (você pode fazer tudo isso em Lua do lado do servidor na caixa Redis para ir ainda mais rápido e evitar o back-and-rede da rede adiante, se quiser):
for id in results:
HGET id 'name'
Seu custo aqui será
O(m) onde m é o número de usuários com o número de telefone fornecido, e esta será uma operação muito rápida no Redis devido à sua otimização para velocidade. Será um exagero no seu caso, porque você provavelmente não precisa que as coisas sejam tão rápidas e preferiria ter uma pesquisa flexível, mas é assim que você faria. 
