Home

jblinktree

Easy to use b-link tree implementations. B-link tree is thread safe map. Implementations is based on "Efficient Locking for Concurrent Operations on B-Trees" written by Philip L. Lehman and S. Bing Yao at 1981.

Original algorithm problems

original Lehman and Yao algorithm doesn't solve some problems:

1. how to split root node, when is full and new value should be inserted
2. what to do with leaf nodes without key, value pairs
3. insert operation record node path to leaf node where value should be placed in stack. Stack could be incorrect in case of parallel root node split.

1) root node splitting

Root node is split like any other nodes. Only is necessary to make sure that only one thread splitting root node.

2) empty nodes

Leaf and non-leaf nodes are left in tree. When some vale is removed from leaf-node this leaf node is not deleted. It's because algorithm is based on same order of locking of nodes. From left to right. In case of deleting node link pointer from previous should be changed. This can't be done without locking it and this node is on right side from empty one.

3) invalid stack

Easies approach is to split last node in stack and than finish operation. Both parts of node will be reachable. One only by link pointer. Tree will remain consistent.

Node data structure

data structure proposed in original L&Y paper is not sufficient. Node should persist it's state in array. First cell of contains some special value when it's leaf node when it's non-leaf node than it contains pointer to child node. When non-leaf node is empty there should be null. It's cause some problem when primitives are used.