> I was thinking of potential issues if you rebalance the tree as an example. > > I’m not certain what issues could arise as I’ve never considered a > concurrent data structure that lacks some kind of synchronisation for both > read and writes unless it’s immutable copy-on-write or similar. > > Do you happen to have references available for further research? > > You do have to be careful when rebalancing. The goal is to make the rebalancing appear atomic to other reads as they go down the tree. IIRC a technique to do this involves recreating the nodes involved in the rebalance and completing the rebalance by updating a single edge at once. That sounds a lot to me like copy-on-write but IIRC it doesn't require copying the entire subtree.
You might also be interested in some of the below references, although they're all on lock-free and wait-free options. Disclaimer: They're all from my Ph.D advisor. I was working in his lab when most of this work was being done. Most of what I've posted here is based on my memory of their approach. https://dl.acm.org/doi/10.1145/3391438 https://dl.acm.org/doi/10.1145/3016078.2851173 https://dl.acm.org/doi/10.1145/2688500.2688551 -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CALJzkY9qb8Y%2BXT6iG7M8UUYjfx3_eU1qRVH1mrsLE85KKTFeLg%40mail.gmail.com.
