Subject Re: [Firebird-Architect] Bi-directional indexes
Author Vlad Horsun
> Hi Ann,
> > 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.
> But with an lock on page 125, page 345 can't update 125 with the new
left-sibling page? So it will
> wait untill the page is unlocked?

Seems we get deadlock here.

> The descing index is only interesting for the navigation through the records
and not for
> index-lookup.


> Another proposal:
> - Remember left-sibling page and current-page, key, recordnumber
> - <time expired>
> - Next record asked which is before the buffered exploded page.
> - Fetch left-sibling page and check if next-page is current-page
> - if found ---------------------------------------------------------|
> - not found, lookup key, recordnumber from index-root-page |
> - Find key, recordnumber <--------------------------------------|

What if <key, recnum> is garbage collected at this time ?
And how about unique indices in which duplicate chains are not sorted
by recnum and new recnums added at the end of the chain ?

> - Fetch previous record

I like it. If we solve issues above and cost of repositioning in
the b-tree is not too high we can go this way.