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 situações, mais rápida que uma árvore que tem complexidade O(logN), 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.


  [1]: https://wiki.python.org/moin/TimeComplexity
  [2]: https://pt.stackoverflow.com/q/168531/101