I can't wrap my head around routing tables. Is it true that every router has a table with routes to every ip address in the world? Wouldn't that make the tables huge and thus make the lookup slow?
Routers with few interfaces need only few entries - a home router with a single subnet inside and the Internet outside just requires two entries.
Routing is a distributed job, every router only needs to know the routes it's got connected somewhere. Hops more remote to the final destination might only match a very short prefix - the default route with /0, or maybe /8 or /12 specific routes. The closer a hop is to the destination, the more refined (=longer prefix) the route is likely to get, with a prefix of /24, /29 or even /32.
The more interfaces, subnets and thus choices a router has got, the longer the routing table gets. Internet core routers may have many 100,000 to more than a million routing entries (thx Ron). More powerful routers use special, content-addressable memory (TCAM) to enable single-step lookup.