Subject RE: [Firebird-Architect] Bi-directional indexes
Author Claudio Valderrama C.
Ann Harrison wrote:
> Consider a case... index pages 123, 124, 125. I'm reading backward
> and have a read lock on 125. As long as I have that lock, nobody can
> change that page. My left hand pointer says I read page 124 next.
> OK. But, at the same time, another transaction tries to add an entry
> to page 124, finds the page full, and splits it, putting half the
> contents into page 345. Now the correct order of the pages is 123,
> 124, 345, 125. Half then entries that had been in 124 are now on page
> 345 and will be missed if the backward walker doesn't read that page.

Can I think in double linked lists for a moment? 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.

nod2's BW should point to nodnew. Didn't we start from the condition that I
hold a lock on nod2? How are you going to wait for the release of my lock on
nod2 to update it without risking a deadlock?