---

2.6 Unlimited Length Keys and Values

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.

1. Data (the easy part)

   The first byte of data is a flag.

   IF the data length < 255

   THEN

   store in bytes 1 - (length_of_data + 1)

   ELSE

   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[2357] 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[2357] and store the value in the master btree.

2. Keys (the hard part) IF key < 250 bytes

   THEN

   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.