Alex, just a couple things from an old-timer for you to consider.
First, if you are serious about that number of rows, you need to fix that. What are you doing, documenting the stars in the Milky Way? In my active years as a DBA I was always advocating for archiving data. You need to consider how old the history is and how often you need to access it, versus the time and cost to store it online, back it up, etc.
At least be sure it is NOT in a database with transactional data, preferably on a different server. Better, move anything more than the last year or so to something like a dis-mountable NAS drive and put it 'in the basement'. Break the data up into unique tables such as by year, get it organized and indexed and ready to access. Create summary data which might even suffice for lots of demands. On the rare occasion you need to access it, you can plug it in and query it at will with simple SQL code, instead of spending the time doing complex stuff just to look at it. In the old days of removable 'disk packs', we had archive disks that we could drop in and fire up as needed. Today I use a NAS device with internal drives that idle down when not active, and I'm thinking about getting a second one. I can archive my data to that, and it's great for backups too so they're not taking space on my active server.
It very easy for companies to get carried away with demands for accessible data, and it's up us to figure out how it gets done. Those of us who have been around for decades had to learn all the tricks because budgets were lots smaller then, both for hardware and personnel. Even back when we had to use 1/2 inch magnetic tape, we did weekly tape-to-tape merges of detail into archived data and only kept summary data online.
We even traded storage with other companies close by where we kept copies of our data archives for security and protection from disasters. Was that the original version of 'the cloud'? Before that, several of us would actually carry home backups and archives for off-site storage.
I have applications that use historical data that is as old as 35 years, with a small quantity of data going all the way back to 1944 but I only keep the most recent 5 or 6 years on my SQL Server, and the rest is on a RAID NAS device that I can access if and when I need to.
So, instead of indexing, consider summarizing and archiving.
One of the best days of my IT career was the day I told my boss if the problem was so simple he should go fix it himself.