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).
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?