Subject Re: [Firebird-Architect] Bi-directional indexes
Author Arno Brinkman
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?

> So why does compression alter all this? If while page 124 was
> splitting, page 125 was compressed and released from the index, the
> backward walker can walk forward all day and will never find its
> starting point. Or, page 125 could have been released from one part of
> the index, then reused somewhere else in the same index. That's all
> very bad. If, however, a page once in the index will never be removed
> from the index, nor change it's position relative to other pages in the
> index, all is well. By changing relative position, I mean that page 124
> will always follow 123 and precede 125. Other pages may appear in
> between, but you will never find smaller key values in 124 than in 123.
> Does this make any sense? Does it seem like a good idea?

If i understand your proposal then index-pages shouldn't be collected together anymore when they get
under a certain threshold. Empty index pages aren't possible at the moment and this will certainly
lead to weird behaviour (empty keys with pagenumbers in non-leaf pages somewhere in the middle?).

The descing index is only interesting for the navigation through the records and not for

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 <--------------------------------------|
- Fetch previous record

Arno Brinkman

Firebird open source database (based on IB-OE) with many SQL-99 features :

Support list for Interbase and Firebird users :

Nederlandse firebird nieuwsgroep :