B+ Trees

I need to know how to maintain the linked list of the leaves in a B+ Tree. I have a file structure where I store each B+ Tree node in a new record. I can reach the left most node simply by following left pointers in the file, until I reach a leaf node. After that, I was thinking maybe I could have an extra field in each node that points to the next leaf node. So I search to go down to the left most node, and then by reading that field I can go to the next leaf node, until I reach the last (rightmost) node and then I am done (I have traversed all the leafs).

But updating such a field, as new keys are added into the B+ Tree file, is almost impossible (at least seems to me). Because each time new record(s) is/are created, I may need to update (it appears) a random number of such fields in different records.

Any ideas? Received on Tue Nov 27 2001 - 17:27:54 CST