> "[H]ow is the crawling ever completed before
> it needs to be re-indexed again?"
Crawls essentially never finish and indexes are never 'done'. If you're building a modern search engine you crawl and index continuously and you use the ranking signals you have developed to steer the crawler to promising new pages.
The reality is that there are roughly between 5 to 15 billion pages that are nominally "not spam" and not duplicates. Literally 99.9% of the internet is crap. So finding web pages as long since switched from 'crawling every page that is accessible from the web' to 'only surfacing those pages that have something of value on them.' That was the fundamental thesis for the founding of Blekko and it is still true today.
That said, a cluster of ~100,000 threads and a couple of petabytes of storage attached with sufficient bandwidth to keep the threads busy can deal with what is out there. If you can create a hash space for strings that is sufficiently uniform you evenly spread the load of crawling every URI you discover across the cluster.
As you crawl you take new pages you discover and apply your ranking algorithm to them where they will score a value between 0 (never index) and 1 (always index).
At which point you can dial the 'rankable' value from 0 (index everything) to 1 (rank only must rank pages) to set the size of the index you can tolerate.