I'm currently using levelDb, which is a key->value store database. The only data being inserted are small binary blobs (that represent nodes for a large merkle tree). When I put a value in the db, I don't really care what the key is, just that I have some key to use as a reference (from its parent nodes which are written later).
As you can see the key->value store does the job but since I don't need control over key creation, I believe it is unnecessarily slow. In order for a key->value database to lookup a key, it probably uses a b-tree. That means that finding a single value is doing O(log n) disk reads.
For my use case it should be possible to get closer to O(1) reads/writes where I put new data elements to the database and it returns something like a direct address. I can use this address as my reference.
(This can already be done in the filesystem by calculating offsets, but I need a "real" transactional ACID database)
Does such a thing exist? I have tried searching but don't know what to call it other than "pointer based database".
I do not mean to imply that I don't require a delete feature. However, this should also be possible using the same address pointer reference. I can also adhere to the additional constraint that each data item be of the same size (I do not know the fundamentals of how db deallocation is handled, but it seems like having fixed length items might help so that new items can rewrite over deleted items in a compact way).
Best Answer
Most RDBMS (with transaction support) are general purpose and picks a tradeoff between reads, writes, deletes operations and storage (memory/disk) requirements. Your requirement is very specific to your use-case. I don't think you will find any database optimized for it.
Basically you are looking for some kind of array lookup. Otherwise it will not be O(1). Do you really have only a put and a get operation. No deletes ?