B-tree implementation for variable size keys

Question

I'm looking to implement a B-tree (in Java) for a "one use" index where a few million keys are inserted, and queries are then made a handful of times for each key. The keys are <= 40 byte ascii strings, and the associated data always takes up 6 bytes. The B-tree structure has been chosen because my memory budget does not allow me to keep the entire temporary index in memory.

My issue is about the practical details in choosing a branching factor and storing nodes on disk. It seems to me that there are two approaches:

• One node always fit within one block. Achieved by choosing a branching factor k so that even for the worst case key-length the storage requirement for keys, data and control structures are <= the system block size. k is likely to be low, and nodes will in most cases have a lot of empty room.
• One node can be stored on multiple blocks. Branching factor is chosen independent of key size. Loading a single node may require that multiple blocks are loaded.

The questions are then:

• Is the second approach what is usually used for variable-length keys? or is there some completely different approach I have missed?
• Given my use case, would you recommend a different overall solution?

I should in closing mention that I'm aware of the jdbm3 project, and is considering using it. Will attempt to implement my own in any case, both as a learning exercise and to see if case specific optimization can yield better performance.

Edit: Reading about SB-Trees at the moment:

• S(b)-Trees
• Algorithms and Data Structures for External Memory

Answer 1

I'm missing option C here:

• At least two tuples always fit into one block, the block size is chosen accordingly. Blocks are filled up with as many key/value pairs as possible, which means the branching factor is variable. If the blocksize is much greater than average size of a (key, value) tuple, the wasted space would be very low. Since the optimal IO size for discs is usually 4k or greater and you have a maximum tuple size of 46, this is automatically true in your case.

And for all options you have some variants: B* or B+ Trees (see Wikipedia).