db implementation #4
Description
For the implementation, right now LevelDB is targeted and seems the best option Although Rocksdb has a quite better benchmark on some operations, LDB seems more stable and supported on the Python side.
LevelDB (and RocksDB, afaik) is a strict key: value storage, with no fancy structures as Redis would provide, like sets and lists. The following operations are available: READ, WRITE, DEL, ITER.
The business logic of the utxo DB, however, would need some sort of bucket in which data can go in and out, under the same key (to index multiple unspents under the same script key, to query "the unspents of the address X"), and LevelDB does not natively support a structure which can help to do this search.
However, the same result seems that can be achieved by organizing the DB keys in a way that the ITER operation would work as a cursor for a list of values.
The data storage would be the following:
outpoint -> script, block, amount
Regarding the indexes, something similar seems that can be iterated:
script.outpoint -> placeholder_byte (not null)
shard.outpoint -> placeholder_byte
This way the DB can be queried by outpoint to return an entry, and by script to return multiple entries (in case of address reusing, for example) or by shard, returning multiple entries as well (as keys).
It is not an efficient implementation on the disk usage side but seems that every access can be flat (with no adds to the LevelDB default complexity level).