Subject Re: [Firebird-Architect] Bi-directional indexes
Author Ann W. Harrison
Claudio Valderrama C. wrote:
> Can I think in double linked lists for a moment?

Sure, that's exactly what we're dealing with.

> Nodes with forward (FW) and
> backward (BW) pointers. Let's assume I'm going backwards and currently I
> have a lock on nod2.
> nod1 has a FW pointer pointing to nod2
> nod2 has a BW pointer pointing to nod1
> nod1 is split and nodnew is created.
> nod1's FW changes to nodnew
> nodnew's BW is set to nod1
> nodnew's FW should point to nod2. Ok.
> But,
> nod2's BW should point to nodnew. Didn't we start from the condition that I
> hold a lock on nod2?

In order to request a lock on nod1, you must be prepared to
release your lock on nod2. As soon as you do, it gets changed so
its left pointer is newnod. But you've still got your old value of
the back pointer.

> How are you going to wait for the release of my lock on
> nod2 to update it without risking a deadlock?

It's not a deadlock until you're waiting for me AND I'm waiting for you.
When the thread that's splitting the page needs to update the back
pointer on nod2, it requests the lock, then backward walking thread is
signaled, it releases its lock, and its whole context disappears.