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

In article <cd3b3cf.0109092001.399a8fb1_at_posting.google.com>, Bob Badour says...
>
>Mikito Harakiri <nospam_at_newsranger.com> wrote in message news:<KERm7.1440$%u4.1368_at_www.newsranger.com>...
>> 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...
>>

>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.

Hmm... The first question is what locking policy am I considering. Is it traditional read/write or something like oracle's serialization with write locks only and reading the past. Assuming the former, I agree that we can place a write lock onto the nodes that need splitting/merging only. The read locks, however, seems have to be placed upon the whole path (including root), as we navigate down the tree and want to preserve a consistent picture.

I see that I need to play more with B-tree applets on the web:-) and/or read the book...

>It might mean that the dbms must on (rare?) occasions
>force the user to recover from deadlock or starvation.

As this topic is at least 20 years old, there must be deadlock-free concurrency policies on B-trees;-) Received on Mon Sep 10 2001 - 09:12:44 CEST