중복된 번호 예외처리를 위한 nested dict 탐색 속도 관련 질문

저는 Update, Delete 메뉴를 실행 시, 입력된 전화번호가 중복되는지 예외처리를 구현해봤습니다.

def find_duplicate_number(phonebook, new_number):
    is_duplicate = False
    for pid, address in phonebook.items():
        if int(address.get('Phone')) == new_number:
            is_duplicate = True
    return is_duplicate

그런데 dict 의 모든 value 를 선형탐색 하는 것이 비효율적인것 같아서 질문드립니다.

Nested dict 형태라서 어쩔 수 없는것인지, 혹은 다른 방법이 있을까요?