Next: , Previous: Longer Value Fields, Up: Theory


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.