It isn't just storage - lookup in those tables needs to be usefully fast.

That was said in my comment. The routing devices need to both be able to store the full table, and also to switch packets by looking up entries within it.