m_theologos wrote:

>>> The problem with reverse navigation in Firebird indexes currently
>> is not their structure, but with the necessity of avoiding internal
>> deadlocks while permitting the recombination of nearly empty nodes.
>>
>
> Thank you very much! I looked a little to the index structure I
> didn't see any impediment, as you confirmed now. But perhaps, then,
> can you do a simple lock manager in order to avoid this?

We do use the lock manager to handle locks (aka latches) on index
pages. The problem is that a reader reading backward will cause a
deadlock against a writer who's combining two pages. That's an
internal deadlock and we don't do internal deadlocks. A transaction
gets a deadlock error if and only if it has a record level conflict
on an update or delete with a concurrent transaction updating or
deleting the same record. (Except, of course, for no_rec_version,
no_wait, read_committed - a combination I have already deplored.)

>
> Anyway, what do you think, implementing the siblings won't do the
> navigation to go faster? You know, at 65,535 items we already have a
> tree with 16 levels... (...but is true that at 1,048,576 items we
> have only 20 levels) which means in worst case (depending of
> implementation) 16/32 comparisions and jumps to go to next node.

No, I think our current indexes which generally keep to three levels
are better. I don't see how you would handle key compression or balance
the indexes you proposed. Have you read these?

http://www.ibphoenix.com/main.nfs?a=ibphoenix&l=;PAGES;NAME='ibp_expert1'
http://www.ibphoenix.com/main.nfs?a=ibphoenix&page=ibp_expert3

Regards,


Ann