Deadlock in Index (where index is B+ tree) Locking with Intention Locks

In class I was told that any locking protocol can result in deadlock when there is concurrency.

Also in class, the professor gave us a simple example of deadlock occurring in the tree, if bi-directional traversal (traversing both up and down the tree) is allowed. This is very easy to understand how deadlock can occur in this case.

But I can't come up with an example of deadlock occuring in a tree based structure when you don't allow this bi-directional traversal.

For example, in the following tree:
http://www.cs.queensu.ca/~cassidy/media/images/tree.jpg

let's say that there are two transactions: T1 and T2

And they all want to delete database objects - you'll notice in some cases that an X (exclusive lock) is obtained on the inner nodes of the tree and not in others. This is because in some cases the B+ tree's index will change if one of it's node's order falls beneath its predefined number and this change could perculate up the tree.

And let's imagine the following scenario: T1 - IX(root) IX(B) IX(D) IX(H) X(P) X(H) X(D) X(B) U(P) U(H) U(D) U(B) U(root)
T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D) U(B) U(root)
T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D) U(B) U(root)

There is no permutation I could find of the above that would result in deadlock.

If you can think of a more simple set of transactions that would result in deadlock I would also be interested in that.

Thanks for any suggestions,
Tim Received on Thu Dec 12 2002 - 11:07:19 CST