Deadlock in Index (where index is B+ tree) Locking with Intention Locks
Date: 12 Dec 2002 09:07:19 -0800
Message-ID: <b80e4a77.0212120907.7cfb153d_at_posting.google.com>
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.
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 - 18:07:19 CET