For work in a similar vein, Mikeal Rogers has recently been working on IPSQL[0] based on peer-to-peer prdered search indexes[1] built on IPFS, which shares the content-addressed nature of BitTorrent.
Hell yeah! Hyperbee is very cool. I'm still trying to get an intuition for the "embedded indexing", and how it compares to a standard b-tree. I did some cursory looking around and couldn't find much on it.
I haven't read the code, and have only read a few-sentence description of embedded indexing. Presuming the writer knows about B-trees and B+trees and isn't just clarifying that they're not using B+trees, embedded indexing sounds similar to Fractal Tree Indexes[0].
For a tree built on an immutable log, it makes sense to buffer some writes at each level of the tree. When you write a new record, you make a copy of the root node with your latest key-value pair appended to the root node's buffer. If this fills up the cache space in the root node, then you determine which child node corresponds to the most buffered key-value, and flush those corresponding key-value pairs down to that child node, recursively until none of the buffers in nodes are over-full. This means that often only a small number of nodes near the root need to be updated, instead of having to write lots of updated intermediate nodes like you'd need with a normal B-tree. The worst-case behavior is all of the caches being full, resulting in O(log N) nodes being written. Also, frequently written keys remain near the root, so if your read pattern resembles your write pattern, frequently read keys will remain near the root node. For TokuDB Fractal Index Trees, my understanding is that these buffered records can also represent schema changes, so that schema changes can be incrementally and lazily applied.
Of course, if one cached write being flushed down the tree catches up to an older cached write for the same key, the older value is just discarded. Presumably, there's also a periodic incremental operation to save space by removing older cached values. Even for something like a blockchain where you want to keep infinite history, you'd probably still want incremental compaction so that clients wanting to download the entire current state don't need to download the entire history.
With respect to IPFS and Merkle Search Trees, can anyone "in the know" comment on how they're materially different than Probabilistic B-Trees as defined by Noms[1] and Dolt[2]? I've been playing a lot with the Noms variant (Prolly Trees) lately and have often wondered where they differ from IPFS-ish Merkle Search Trees. If at all.
Whereas Noms Prolly-Trees are like B+Trees, since all values are stored in the leaves.
Merkel Search Trees use the prefix of the hash of inserted keyvalues (number of leading zeros) to determine which layer will contain that keyvalue. This provides a deterministic tree structure for any given set of keyvalues, when you arrange them by key order.
Noms Prolly-Trees use a rolling hash across the sequence of keyvalues to determine split points, similarly when the number of leading zeros exceeds a threshold. Then those leaves are assigned as children to keyvalues on the next highest layer, which is again split in the same way, until a single root node is left.
Excellent description, thank you! While i'm mulling on what you described, are there any use cases that jump out for Merkel over Noms?
Given that i've been using Prolly-Trees for a content addressed store, a lot of the descriptions of Merkel sound similar in properties to how Prolly-Trees behave. I struggle to think of a use case where Prolly would excel over Merkel, or where Merkel would excel over Prolly.
https://hypercore-protocol.org/guides/modules/hyperbee/