sql - Improving scalability of the modified preorder tree traversal algorithm -
I was thinking about algorithm for storing trees within a flat table (like SQL).
I dislike about a standard property that you need to touch the nodes (average) N / 2 (everything above the left or right point of the point) to insert the node.
The deployment I have seen relies on sequentially numbered values. It leaves no room for updates.
It is bad for concurrency and scaling. Imagine that you have a root in the world in which there are user groups for each account in a large system, it is huge, at this point you will have to store tree subsets on different servers. To add one node to the lower part of the tree, half of all nodes are bad.
Here is the idea that I was thinking. Actually leave the room for inserts and split on each level.
Here is an example with N maximum = 64 (this will usually be MAX_INT of your DB)
0:64 ________. Here, a node has been added to the left half of the tree, here ________ / 1:31 32:63 / \ / 2:14 15-30 33:47 48:62
0:64 ________ | ________ / 1:31 32:63 / | \ / 2:11 11:20 21:30 33:47 48:62 For the process of inserting and removing allocyths, the left / right indexes should be extended for the recurring number. The subtitle is complicated after inquiries for immediate children of a node, I think it also makes sense to store the parent ID in the table. The algorithm can then select sub-tree (using left> P. left and right & lt; p.right), then to work through the list, node.ID and node. Use, indexed sub-split
It is more complicated to increase the space (or decrease it to deletion) to place all the indexes, but it has the ability to affect very few nodes (insert / delete) Only the Dictensants of the Guardian of the Node)
My question is basically:
-
Has this idea been formally implemented or implemented?
-
Is it similar to nested intervals?
I have heard of people
Note that by doing so you lose some of the algorithms in small benefits
- Normally, you can tell the number of descendants of a node ((right - left + 1) div 2 ) This can sometimes be useful, if the example will show a count in a tree view, which should include the number of children in the trees and below.
- It is easy to select the nodes of all the leaves, flowing above - WHERE (right = left + 1).
These are minor advantages and may not be useful to you anyway, although they are clearly easy for some usage patterns.
He said, as suggested above, this can prove to be useful to you as the physical route is possible