b+ tree implementation question

i don't know if this is the right place to ask, maybe you can point me to a better place if i'm offtopic here...

i am implementing a B+ tree, just for fun, and so far inserting works fine, but i have problems in one special case: if i have to split an internal page.

assume i have to pages, and an order of 4 (also assume that you have a non-proportional font for my drawings):

2 4 6
|
6 7 8

now insert 9, and the second node is split, and 8 moves up in the first node:

2 4 6 8
/ \
6 7 8 9

now we have to split the first node:

---6-----

/         \
2 4           6 8

my problem is in the insert algorithm. in the first step i get the page where i insert 9. i split the page (6 7, 8 9), then get the parent page of (6 7) and insert 8 recursively in the parent page. this is easy, because every page has a pointer to the parent page. but this is also my problem: if the parent page (2 4 6 8) is split, i would have to update every child page to change their parent pointer to the correct address! and this can get very expensive, if i have some hundreds of child pages.

so finally here's my question: is there a cheap solution for my problem? or do i have to completely rewrite my tree and maybe even totally get rid of the "parent"-pointer?

thanks for any ideas!
Chris

PS: i noticed that google groups messes up my drawings, so i made a png:
http://www.crupp.de/btree.png Received on Thu Jan 20 2005 - 17:19:19 CET