The download size of the app is around 50MB. When you first download the app, you will need to select the language you want to use for text and voice search. English (UK) and Spanish (Latin American) will not involve any additional download size. You can download any of our other languages for around 6MB per language, and use that language in the map via text or voice search (the only languages we don't currently support for voice are Mongolian, Swahili, isiXhosa, isiZulu, Afrikaans, and Bahasa Indonesia. We hope to add these languages for voice search at some point).
The technology is based on an algorithm rather than a massive database, which is why it can fit on your phone. A database of 57 trillion addresses would be many many terabytes in each language!