Vlad Vaintroub, one of developers on Falcon, has proposed an alternative
to the multi-key index scheme common to Interbase, Firebird, and Falcon
that is significant denser than the current schema. In a nutshell, a
multi-segment key is constructed using the following rules:

1. Index key segments are separated with a 0x00 byte.
2. Occurrences of 0x00 in an index key are replaced with the sequence
0x01, 0x00
3. Occurrences of 0x01 in an index key are replaced with the sequence
0x01, 0x01

It is clear that a string that compares naturally also compares
naturally after the application of rules #2 and #3. It should also be
clear that the key separator 0x00 is compares low to any possible value
in another key segment.

Character strings never contain 0x00, so this scheme always as short or
shorter than the grouping scheme currently in use. The violated doubles
may require a fudge byte or two, but it is rare that the number of fudge
bytes will compare unfavorably with the current rounding to byte
groups. The most common number (< 24 bits of significance) will be
shorter than the current scheme.

I've never been wild about the byte grouping scheme, but it worked.
This scheme, I believe, is better. (Nimbus doesn't use btrees, so none
of this applies there.)

--
Jim Starkey
President, NimbusDB, Inc.
978 526-1376



[Non-text portions of this message have been removed]