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 (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". 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.