Is it possible to synchronize two trees with nested sets representation?

Question

I've got a tree of objects stored in the database using nested sets representation. Each tree node have its own object (only one). The tree can be modified by users in the online application. There is also a set of applications (pc, android, ios) that can work offline and modify their data as well. New leaves or branches may be added on two or more devices.

Next, all the data is synchronized (REST API, XML) between the server and the offline applications when applications get internet access. After successful synchronization the state on the server and client side must be the same.

There is no problem in data synchronizing with a flat data structure (based on modification timestamp), but I don't know if it is possible with a tree. The synchronization should be fully automatic. I don't want users' interference in the synchronization process.

Answer 1

Because nested-sets representation relies on node markup and on average a hierarchy change (insert, move, delete) involves markup update on half of the tree nodes (right half of a tree from the changing node), you can't just send the node (record) data on its own. If you apply it it will corrupt the master tree markup.

What I suggest you to do is to queue your changes on an offline device, like:

queue.append({'method': 'insert', 'parentId': 123, 'name': 'foo'})
queue.append({'method': 'delete', 'nodeId': 456})
queue.append({'method': 'move', 'nodeId': 789, 'newParentId': 234})

And then try to re-apply the queue on server-side. As you say you have no problems with synchronising flat data, you already must be having some conflict resolution policy. So when user A deletes node:123, and later user B tries to append a child node to node:123, you will need to handle the conflict somehow.