I see. Note that the amount of lookups for the hash table only holds if there is no collision, but that may be a fair assumption. Given that the data are strings, a specialized datastructure such as a Trie or suffix array might work well, especially if it is possible to exploit redundancy in the data (i.e., repeated substrings). There are specialized datastructures used in full-text search which will probably be useful. In any case dealing with this amount of data might mean that using an off-the-shelf database might be a good idea.
The benefits of B-trees over hash tables don't matter in this application, as I don't care about adjacent keys after lookup, and the input order of my keys is not going to be sorted in any way so once I find a leaf it's not going to help me with subsequent lookups.
In this setting it seems that any B-tree access is going to require traversing several new nodes in addition to the first node, and those internal nodes are extremely likely to be both cache-cold and TLB cold. Whereas with a hash table I only have a single cold memory lookup to check the hash bucket, then a single cold memory lookup to validate the key at the bucket matches; this cold memory lookup for the validation is also likely to warm the cache for the subsequent matching work, and this small amount of subsequent matching work would likely be required by a B-Tree as well. Any thoughts?