How to warm a MongoDB index
I tried this on a collection with millions of documents, and hope this is going to work in a multi-billon document collection:

Create the index in the background. This can seriously hurt your .finds. We got timeouts for the duration of the index creation.
Clear the plan cache.
Create a script to scan all your data with hint to warm the index.
Delete the old index.
Clear the plan cache again.
Try to find some data with the new index, and ensure it's used with explain. You must use different keys each time to ensure explain does not cache your query.