Re: why locking a path in B-tree is not necessary

Mikito Harakiri <nospam_at_newsranger.com> wrote in message news:<KERm7.1440$%u4.1368_at_www.newsranger.com>...
> I must apologyse in advance for posting a question, the answer to which I may
> easily find, for example, in Gray/Reuter's book.
>
> Transaction isolation with locking mechanism means locking the table(s) and
> locking indexing data structures. What minimal part of the B-tree must be locked
> with exclusive lock, for example? As any of the tree node could split, it is
> easy to see that locking the path from leaf to the root would be sufficient.
> Obviously, this is not a realistic B-Tree locking implementation, since the
> write access becomes not concurrent at all: first transaction locks root node,
> and the others wait for this lock to be released. On the other hand, as we need
> to lock nodes in advance -- before navigating the tree -- how can we know that
> locking the root node, for example, is not necessary in any particular case? If
> we make our decision upon, say, the tree cardinality, stored as a counter
> somewhere, then this counter becomes a bottleneck that must be locked during any
> transaction...
>
> There is no question that [physical] denormalization like indexing, or creating
> materialized views decreases the degree of concurrency. So, even though, the
> individual query might speed up, the total throughput would suffice. The
> question is how much?

While I am no expert on locking implementation strategies, it seems to me that locking the root prevents deadlock at the cost of greatly reduced concurrency. Locking from the leaf toward the root on an as-needed basis should balance concurrency with consistency and occasionally require a little extra effort to recover from deadlock situations. It might mean that the dbms must on (rare?) occasions force the user to recover from deadlock or starvation. Received on Mon Sep 10 2001 - 06:02:00 CEST