The salt can be stored directly in front of the hash in the same string in the DB (a lot of crypto hash functions will output this). It can be plaintext since the goal is to add a random component so rainbow tables wouldn't be possible since there's always more to the string being hashed. That's where it becomes a time problem.

Yeah, you could rebuild a rainbow table yourself u til you find the collision, but you have to search every bit of the potential hash space.