Storage system for large quantities of unique key value pairs optimized for insert
B-trees and their various modified versions are the standard way to index arbitrary data while keeping insert times within a reasonable frame. Insertion happens in O(logn) time, which I believe cannot be improved, unless your key range is limited enough to make a bitmap usable.

That said, there a few things that can make B-trees and their variations faster:


Watch your keys. Non-random keys can cause pathological situations. You are using a hash, so key-dependent pathological situations are rather improbable.
Benchmark the application. Find out if the B-tree implementation achieves that O(logn) time for large datasets. Note: for large datasets. Only compare datasets for which the B-tree size significantly exceeds the size of your physical memory. Smaller datasets will have minimal disk seeks due to the OS cache and will seem lightning-fast. E.g. if you have 4GB of RAM, try comparing an 8GB, a 16GB, a 32GB and a 64GB index. If you do not see an O(logn) time curve, you may have a problem in your specific implementation.
Profile the application. Find out where the bottleneck is. Is it the CPU (not very probable)? Disk seeks (here's my money)? What part of the code produces the bottleneck?
Measure your B-tree index alone without the backing file. Does the application speed-up significantly without the backing file seeks? Would it make sense to store some data (e.g. the hit count) in the B-tree nodes themselves, to avoid the extra seeks? Storing some common data in the B-tree nodes should provide a major performance increase.
Use a shorter and faster intermediate hash. It does not have to be cryptography-level, just sufficiently random. I have used MurmurHash3 with pretty good results. Use that hash as the key in the B-tree, and an external mechanism (e.g. linked lists) to handle collisions. Using shorter keys will speed up your B-tree significantly, because each node can fit more ranges.
Optimise for less I/O and fewer disk seeks. In your case it's quite probable that the performance killer lies in your disk. Try using larger B-tree nodes.