Previous: To Be Done, Up: Theory


2.8 Miscellany

"Largest keys" (End-of-chain marker strings).
Because we've reserved keys with a first byte of FF for split keys, these keys are unavailable to the user.
NULL keys
WB supports use of the null string as a key (Sliced Bread treats the key specially).
Searching on minimum and maximum keys
Given that the null string may be used as a key, there needs to be a way to specify a "least" key such that NEXT(least) yields the first key, even if it is NULL. The special key strings with length s of -2 and -1 are provided to represent the minimum and maximum key values, respectively. These keys are only useful with NEXT, PREV, REM*, and SCAN; data cannot be associated with these keys.
Need to document TSCAN, TSTATS.

2.8.1 Bibliography

A comprehensive B-tree bibliography can be found at: http://www.informatik.uni-trier.de/~ley/db/access/btree.html

[BM72]
R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173-189, 1972.
[SAGIV]
Yehoshua Sagiv. Concurrent Operations on B*-trees with Overtaking. JCSS 33(2): 275-296 (1986)
[WANG]
W.E. Weihl and P. Wang. Multi-version memory: Software cache management for concurrent B-trees. In Proc. 2nd IEEE Symp. Parallel and Distributed Processing, 650-655, 1990.