Previous: , Up: Theory   [Contents][Index]

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.