Database structure over the dag

[leni536]

Hi!

I'm playing with the thought that i might be not completely idiotic to introduce a dumb database structure on the merkledag. Of course you can host any single file database as a unixfs file already, but to effectively query them one has to download pretty much the whole file. Also if someone introduces a new version of the same database with minor changes, it's not evident that it can be updated effectively in terms of bandwidth.

So my idea is to introduce a database format over the dag. For easy query it could have a btree index structure straight mapped to the dag. The data can be stored in a unixfs file, I think raw insertions, deletions, updates can be optimized to only touch minimal number of blocks. Maybe there could be a journal to not to touch too many blocks on a database update.

For implementation I think using the leveldb interface could be handy.

One use case: software package distributions signing and updating package databases (through ipns) while the users can query and update it efficiently. Of course then the row data can be ipfs links to metadata, which again links through ipfs to the package itself.

Maybe it's totally dumb, and can't be implemented efficiently though.

[whyrusleeping]

I like this idea, i'd be interested to see this worked on a bit :)
We have a 'set' implemented on top of a merkledag here: https://github.com/ipfs/go-ipfs/blob/dev0.4.0/pin/set.go

[jbenet]

@leni536 this is a very good idea in general. We've had some discussions about storing database indices on IPFS, but no concrete work toward it yet. I would recommend achieving:

• first a key-value store - with arbitrary keys (easy)
• making a storage backend for SQLite (harder)

So yeah, starting with leveldb (or even https://github.com/jbenet/go-datastore/ ) would be nice :)