CODEWITHSUNDEEP
databaseblink
injoy
injoy

Reputation: 4373

How Blink-tree cope with such situation?

When doing an insertion in Blink tree, it will store the path from the root node to the leaf node. And when the child node split, it will propagate such changes to the parent nodes. Assume that when the propagation research the root node in thread A, and the current insertion checks the stack (used to store the path) and finds out that the bottom node on the stack is the "root". And the "root" need splitting also. It will create a new root.

So, what if the "root" is already split by another thread and the "root" is not the real root now. So, creating the new root done by thread A is not correct.

How Blink-tree cope with such situation?

Upvotes: 1

Views: 307

Answers (1)

DrC
DrC

Reputation: 7698

I'm not sure how the authors intended to handle that issue (and I do think it is real). One possibility is to add a header block containing the tree height (depth) and the address of the first block for each height above the leaves. If you ever run off the end of the stack, you need to lock this block and read it to determine a new root (or, more accurately, the first block at the height above the tree heights in your stack). If it is there, unlock the header block and add the block to your stack before continuing. If the new root doesn't exist, you can create it and add it to the header block before writing the index block back (after writing the new root). In theory, this could occur more than once if the root got split multiple times between the up and down phases. By locking the header block before checking it and before adding the new root, I think you can maintain the ordering invariants for deadlock avoidance.

Upvotes: 1

Related Questions