Quote from: 2112 on November 04, 2012, 07:33:02 PM

Again, the claim "this is not possible with BSTs" about impossibility of parallelism in b-trees is false. I wonder what is going on here?

I should've stated that differently -- it's not impossible to parallelize general BSTs, etc, but since we are dependent on the underlying structure of the BST (which is not a normal requirement of BSTs in other applications), insert order must be strictly adhered to, and thus each insert operation must be completed in order before the next can be applied. By definition, that is a serial process. Along with that, sub-branches of the BST are not independent, so it's more complicated to even have the storage space split up, since rebalance operations may shift nodes from one thread's storage space to another. It's not an impossible task, it's just an unnecessarily complex one.

And I have a tough time believing that no one in the future will ever benefit from sub-tree independence: with the BST, lite nodes can't even maintain their own little sub-trees for their addresses, because the structure of that subtree could change due to unrelated inserts nearby. Or, the subtree could induce a rebalance itself, and change the root of the subtree that has to be tracked which may include other nodes it doesn't care about.

With the trie structure, sorted first by address then by OutPoint, a lite node can maintain sub-trees of each of its own addresses, insert and delete elements in any order, and roll back its subtree on reorgs without having to care about anyone else's OutPoints. And all using simple, standard insert and delete ops, found in any textbook on the subject.

But, I have to agree that the first implementer of this stuff is likely to set this standard. I was hoping to persuade the folks who are working on it now, that the trie structure is not only the simplest, but the most flexible and robust. Apparently, I'm not succeeding. I better get back to fixing Armory so that maybe one day soon I can work on this problem, too