There are other fun ideas to explore e.g. if your external id is a hash you can rebuild, it might be an option to scavenge the full hash but keep the first few bytes of it, indexed. That increases lookup costs if the hash does not exist or has been scavenged but lowers storage.

In fact if your external ids are evenly distributed you can do that anyway, only index the few leading / trailing bytes of the id. That will increase lookup costs a bit but significantly decrease storage.