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

Improve this question
3
  • 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.
    – user1822
    Commented Mar 27, 2020 at 7:14
  • 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
    Commented Mar 28, 2020 at 13:37
  • 1
    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.
    – user1822
    Commented Mar 28, 2020 at 13:53

1 Answer 1

Reset to default
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 ?

Improve this answer
2
  • 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
    Commented Mar 26, 2020 at 13:23
  • In that case, I don't know how all insert, delete, and get can be O(1) at the same time. If you also need deletes, that means slots/keys can be reused. So, an insert operation should search for the next available free slot. Its O(logn) in general.
    – sunil
    Commented Mar 29, 2020 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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