Next: , Previous: , Up: B-tree Structure and Access   [Contents][Index]

2.1.8 Prev


SCREW CASE FIX UNDERSTOOD BUT NOT YET IMPLEMENTED: if down-pointers are missing to blocks immediately after the first block of a level, PREV will miss those blocks. The problem occurs when a PREV-BLOCK of block B at level N occurs, causing a PREV at level N+1. If down-pointers are missing, the block B’ associated with B’s split key may be some predecessor of B rather than B itself. In this case PREVing at level N+1 is wasteful but correct; it would require fewer block accesses to chain from B’ than from PREV of that entry. However, if the B’ entry is the FIRST at level N+1, PREV will erroneously conclude that it is at the start of the chain. It either has to (a) always look at B’s entry at level N+1 to check that the current block’s ptr is really up-to-date, or (b) just check when it hits the START-OF-CHAIN.