Como fazer isso - python dictionary atravessar e pesquisar

Eu aninhei dicionários:

{'key0': {'attrs': {'entity': 'p', 'hash': '34nj3h43b4n3', 'id': '4130'},
          u'key1': {'attrs': {'entity': 'r',
                              'hash': '34njasd3h43b4n3',
                              'id': '4130-1'},
                    u'key2': {'attrs': {'entity': 'c',
                                        'hash': '34njasd3h43bdsfsd4n3',
                                        'id': '4130-1-1'}}},
          u'key3': {'attrs': {'entity': 'r',
                              'hash': '34njasasasd3h43b4n3',
                              'id': '4130-2'},
                    u'key4': {'attrs': {'entity': 'c',
                                        'hash': '34njawersd3h43bdsfsd4n3',
                                        'id': '4130-2-1'}},
                    u'key5': {'attrs': {'entity': 'c',
                                        'hash': '34njawersd3h43bdsfsd4n3',
                                        'id': '4130-2-2'}}}},
 'someohterthing': 'someothervalue',
 'something': 'somevalue'}

dado umid - um de todosids gostar4130 para4130-2-2.
Qual é a maneira mais fácil de navegar para o dicionário correto?

Como se o dadoid é4130-2-1 então deve chegar ao dicionário comkey=key5

abordagens não xml, por favor.

Editar (1): O aninhamento é entre1 para4 níveis, mas eu sei o aninhamento antes de analisar.

Editar (2): Corrigido o código.

** Edit (3): ** Corrigido código novamente para valores de string deids. Por favor, desculpe pela confusão criada. Este é final, espero :)