Yeah. You mention ECC, and I was previously thinking some sort of integrity-checking solution modeled on parity bits could work. Problem with that, of course, is I think something needs to have complete knowledge of the data structure to make it work, plus now you have yet another thing to update over network.

I'm not sure that ZeroDB will necessarily have all the answers here prepackaged. I'm still waiting to see exactly how intelligent their client modules are. I doubt they're just delivering a bucket store, so I assume they'll have client-side code that'll encapsulate the BST handling. The question is whether it's naive or accounts for some of this. If nothing else, I assume michwill is probably taking notes!

At any rate, my hope is this ends up being an interesting enough solution to build some degree of pattern or best practice over to handle some of these aspects. These might be as simple (and limiting) as "one table, one source of truth, period," or "Use for write-seldom; read-often applications only," or some other thing like that.

Even if so, this could be quite useful for -some- subset of applications, or at the very least a useful step on the way to figuring out how to do this sort of thing.

Certainly there are other challenges here as well. Beyond integrity issues, there's still the information leakage issues. It's already been mentioned that a binary search leaks order information to begin with, but if you know what kind of tree is being used you leak a lot of order information as the rotates happen.

But again, maybe surmountable. I'm eagerly awaiting the source implementation so we can dig in.