0

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

New contributor
ZMitton is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • 1
    "That means that finding a single value is doing O(log n) disk reads" - that's not true. B-Trees in relational databases are quite efficient and even for really large tables, looking up a row by a primary key is pretty much constant in time. – a_horse_with_no_name yesterday
  • Thank you for the insight. How is that possible though? What does "pretty much" constant time mean? I first assumed/hoped primary key (id) may be implemented as a an address + (id * offset), but cursory research has determined that to be false. – ZMitton 8 hours ago
  • A modern database will typically need around 4 I/O operations to find the row for a given PK value regardless of the size of the table. – a_horse_with_no_name 7 hours ago
1

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 ?

  • I did 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). – ZMitton 2 days ago

Your Answer

ZMitton is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.