B+Tree implementation questions

i have written a small database in my spare time - in C, using B+Trees for indices. I still have a lot of features to add (multiple indices, duplicate keys, in-memory databases etc). And there's one feature, where i don't have a lot of clue, which is my question to you:

how would you implement B+Trees with variable key lengths?

my suggestion: store a prefix of the key in the index, together with a pointer to an overflow area, where the rest of the key is stored.

as soon as the key is needed, it's loaded from the overflow area, and cache it, as long as the page is cached.

in most cases, it won't be necessary to load the key, since the prefix is sufficient to compare two keys.

however, this is just an idea of mine, and i guess it's a simple way (but maybe also a naiive one) to implement it. if you have other ideas or pointers to papers, implementations etc, please answer.

regards,
chris Received on Mon Jan 09 2006 - 11:20:49 CET