Storage system for large quantities of unique key value pairs optimized for insert Background

I'm in the process of attempting to improve part of our data storage and analysis architecture. Without getting into a lot of details, at a certain part of our data analysis process we have a need to store large quantities (~100s of millions) of small pieces of unique data. The data looks like this: 

ID, 20 bytes (immutable)
Hits, unsigned 64bit int (mutable)
Value1, arbitrary length byte array (immutable)
Value2, arbitrary length byte array (immutable)


I currently have this data stored in two parts, a B+Tree index which maps the keys to unsigned 64bit integer values. Those values are file offsets in a data file which contains a structure like:

[Hits] UInt64
[LengthOfValue1] UInt32
[Value1DataBlob] N-bytes
[LengthOfValue2] UInt32
[Value2DataBlob] N-bytes


As new values are posted to this data store, the code performs a lookup in the B+Tree. If the tree contains the value, the hit count is incremented in the data file. If the value is not there, a new entry is appended to the end of the data file, it's start offset the inserted into the B+Tree.

Later, after this process is complete, we will enumerate the data performing more processing on it. What is important here though is that, if the key is already in our system, we are incrementing the hits on that key. This is essentially a cache, which is tracking hits on each piece of data as it's encountered. 

What we are finding is that as the B+Tree grows larger, insert times become VERY slow. Lookup remains very fast (as you might expect). 

Question

So -- Does anyone know of another way to do this, where unique checks are lightening fast, and so are inserts? We really don't care about later search performance, because once we go through the initial build of this dataset, all we will use it for is to enumerate the results. We're not going to be doing random searches against the dataset, in a long term manner. 

Please do not suggest any kind of off-the-shelve database system. We've tried a lot of them, and this custom solution is faster than any of them, with a smaller data storage footprint. 

We're just trying to improve our custom solution, and have hit a wall with our collective CS knowledge. Maybe this is the fastest way to do this, or maybe a different structure would perform better than the B+Tree for inserts at this scale?
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.