A implementação interna do dicionário de Python é usando tabelas *hash*, então tem complexidade O(1) para achar chaves, isto pode ser confirmado na [wiki oficial de Python][1] (obrigado ao AlexCiuffa). Ele é, em tese, e em quase todas as situações, mais rápida que uma árvore que tem complexidade O(log n), mas ele não pode ter as chaves naturalmente classificadas como uma árvore pode, e não pode ter chaves repetidas. Um dicionário era [não "ordenado"][2]. Segundo o jsbueno abaixo em comentário agora ele consegue ser ordenado usando uma estrutura auxiliar, então mantém o O(1) para acesso ao elemento e consegue atravessar todos elementos na ordem que foram inseridos, ao custo de ocupar mais espaço que poderia, o que para Python não é um grande problema porque já fazia isto antes. Ele ainda é não classificado e só poderia ser assim de forma eficiente com uma árvore ou algo parecido. [Coloquei no **GitHub** para referência futura][3]. [1]: https://wiki.python.org/moin/TimeComplexity [2]: https://pt.stackoverflow.com/q/168531/101 [3]: https://github.com/maniero/SOpt/blob/master/Python/Conceptual.md