Identificar el titular del teléfono desde el cual recibo una llamada

Se quiere enriquecer el teléfono celular para que muestre información de la persona que esta llamando cuando el mismo no se encuentra en la agenda de contactos. Para esto, cuando el teléfono suena, se debe obtener inmediatamente la información del abonado a partir de su número telefónico.

Supongamos que la lista de abonados contiene 800.000 abonados. 

 ¿Es importante el tiempo en el que se accede a un dato que se está buscando?

En este caso de uso puede verse claramente la importancia de obtener los datos en el menor tiempo posible. Esto no sería posible utilizando un árbol binario de búsqueda, ya que en el peor de los casos, será necesario recorrer los N abonados, es decir, los 800.000 abonados para obtener la información. Si utilizamos un árbol AVL será necesario recorrer a lo sumo log2 (N), es decir, 20 abonados.