2.1.10 Other tree organizations
There are other possibilities for tree layouts. It is possible that
some of these may simplify operations that in the current layout are
complex, such as the insert-screw-case. Other possible choices include:
- split key at start rather than the end of the block;
- reversing the order of (key,value) pairs in the blocks;
- not using the split key
- using TWO split keys (one at each end of the block);
- running the chains backward rather than forward;
My (RJZ’s) favorite alternate assumption is allowing multiple versions
of blocks to exist, as in [SAGIV]. This would mean:
- processes would be allowed to maintain STATE in a block, such as current
position, such as for successive NEXTs; on the other hand, NEXT would
have to check for NEXT(X)<X and skip forward accordingly.
- Write/Read interlock overhead should be greatly reduced (as WRITEs do
not have to wait for reads);
- the need for NAME locking is greatly reduced, since we no longer would
be trying to count the processes that "know" about each block;
- reclaiming deleted blocks is harder;
- other issues to be evaluated: effect on rebalance, PREV, and the
deferred-operation protocol we’ve developed.
Perhaps we can explore the interrelationships in some methodical way
someday …