- No duplicate key
- Leaf-oriented k-ST
- Each leaf has zero children and at most k - 1 keys
- Each internal node has exactly k children and k − 1 keys (in increasing order)
Non-blocking k-ary Search Trees需要平衡，tree的深度和每个internal node进行search和update时的work总量。
k = 4的时候，在高contention和低contention的情况下，性能都是最好的。
- Insert: the BST’s insertion -> sprouting insertion
- Delete: the BST’s deletion -> pruning deletion
- Coordination: extended from BST
Each leaf has zero children and at most k − 1 keys (zero keys is permitted). Each internal node has exactly k children and k − 1 keys. Inside each node, keys are maintained in increasing order.
Dummy nodes are used in BST to avoid special cases when there is no parent or grandparent to flag and mark. The following pruning deletion operation will meet similar problem. When perform pruning deletion, the leaf may won’t have a parent or grandparent. To avoid dealing with that, dummy nodes and empty leaves used again when initializing the tree.
- Dummy nodes: each have k − 1 keys valued $\infty$.
- Empty leaves: 2k - 1 empty keys in total.
Search for the key first.
If the leaf is full, replaces the leaf by a newly created subtree.
The newly created subtree:
- The k - 1 greatest keys among the original k - 1 keys and the new key.
- The children are k (the original k - 1 keys and the new key) new nodes.
If the leaf is full, replaces the leaf by a newly leaf with k keys (the original k - 1 keys and the new key).
First search for the key.
If the leaf has one key and the parent of leaf has exactly two non-empty children, replace the parent with the sibling of leaf.
If the leaf has more than one key or the parent of leaf has more than two non-empty children, replace the leaf by a new leaf with key removed.
Interleaved execution between concurrent updates in some particular order may cause problems (of cause).
The Coordination is similar to BST, but here the scheme is extended.
Mark) objects is just like lock.
For both types of insertion and simple deletion.
For pruning deletion.
Before an internal node is to disappear from the tree, it must ﬁrst be marked. Once a internal node is marked, its child pointer will never be changed.
Initial stat of the
pending filed in internal node.
If an operation is unexpectedly delayed while holding access to a ﬂagged or marked node, the progress cannot be guaranteed. So helping mechanism is necessary. The method taken here is similar to the one in BST.
But the helping should not be abused. To avoid many duplicate operation, the helping is used in limited cases.
Just for clear the thought.
The following picture isn’t presented in the paper. Because the idea in the paper is similar to BST. So it easy to imitate the original one in BST.
ReplaceFlag is used in simple insertion, sprouting insertion and simple deletion. So the original notations,
dchild ..., etc won’t apply.
There two types of deletion in k-ary Search Trees. And a particular interleave of insertion and deletion would result in key lost.
Suppose there are some nodes in k-ary search tree (see above figure) and two threads concurrently perform update.
- Thread ti: insert d at b (the order doesn’t mater)
- Thread td: delete b
The following operation sequence is executed (direction of child isn’t mentioned, but it should be fairly easy to see),
from now on, the p won’t be marked by td until ti finished.
- ti: Finish insertion and
- td: Mark p
- td: Change the pointer in gp to s
Consequence: Insertion of key, d is lost. :(
The problem is that pruning deletion changes the child of gp to the child of p without knowing the modification in the another child of p.
Above problem won’t happen in BST’s deletion, since the new node (internal node or leaf) is always built from scratch.
pending of p must be read before
PruneFlag set at gp and checked when performing mark cas. If any insertion occurred, the
pending of p will be bound to changed and deletion will perform backtracking cas and restart.
BTY: In BST and k-ary search tree, the
pending of p is already read by the end of search and the above prerequisites in implementation is already done. But it has special purpose and meaning here.
In k-ary search trees, CASet (compare-and-set) is used to implement CAS.But the prerequisites is the algorithm doesn’t suffer from the ABA problem.
The reason why these algorithms doesn’t suffer from ABA problem is quite clear for me. But what does the prerequisites (doesn’t suffer from the ABA) for?
- Non-blocking k-ary Search Trees, Trevor Brown, Joanna Helga
- Non-blocking Binary Search Trees, Faith Ellen, Panagiota Fatourou, Eric Ruppert, Franck van Breugel