by Jonathan Finger
Use 2 btrees which I will refer to as main and slave
notation D[123,4567] will translate into a string D \3 1 2 3 \4 4 5 6 7 where \3 is ascii 3 etc (length of following string of digits) this will result in keys sorting in numerical order.
The first byte of data is a flag.
IF the data length < 255
store in bytes 1 - (length_of_data + 1)
In slave btree increment value in key D (D for data)
As an example assume the new value is 2357 and the data is 10,000 bytes
Store the data in D[2357,0] = first 250 bytes D[2357,1] = second 250 bytes . . . D[2357,249] = last 250 bytes
When a new value is set, if it is > 254 bytes in length then you reuse the D names adding or deleting as needed. Note that it is much more efficient to overwrite existing nodes since (most) of them will be the same size and add or delete at the end. If the new value < 255 bytes delete D and store the value in the master btree.
Store in master file as usual
ELSE (key >= 250 bytes)
break up the key into chunks C0 ... CN; the first 250 bytes long and the rest 220 bytes long.
Create the entries (assume current value of key V is 243)
Master btree C0 = (flag)244 Slave btree V[244,C1] = 245 V[245,C2] = 246 . . . V[244 + N,CN] = data
A get now consistes of breaking up the key and following the chain. The put, delete, next, and prev code will get a bit messy since there will be multiple cases to consider.
I believe this scheme will give unlimited key and data length. Performance probably will not be great but may be acceptable. This should give good key compression.