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:
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)
T2 - IX(root) IX(B) IX(D) IX(H) X(O) X(H) X(D) X(B) U(O) U(H) U(D)
T3 - IX(root) IX(B) IX(D) IX(G) X(N) X(G) X(D) X(B) U(N) U(G) U(D)
There is no permutation I could find of the above that would result in
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,