One way to speed access to a large table is to partition the data. Oracle has partitioning and now so does SQL Server. I've worked with Oracle's version for a while, but this is my first foray into the SQL Server variation.
I'm going to try to keep this as brief as possible, so I'm going to leave out much theory and background and leave that as an exercise for the reader and his friend Google.