Doubts about Top-Down Splitting

[cesarghali]

There is something wired about it every time I think about it. We are splitting nodes while going down the tree. We might split a node in level 1 and then when we go down the lower layer node, in level 2, might not need splitting, this will leave a page pointer in the node at level 1 with nothing to point at. Is that right?

[diedthreetimes]

No, when you split a node at level 1, the pointers all still point to real data that is at least half full. At least that is what I thought...

I could draw a picture :P

[cesarghali]

Here's what I was thinking. Assume you have one full node at level 1 with pointers to 5 half-full nodes at level 2 (leveling starts from the root). If you split the node at level 1 into two, then you will end up with 6 pointers but you only have 5 pages at level 2 which none of them need splitting.

I would need a picture because I don't know why I am not able to imagine it :P

[ekinoguz]

Sky and I discussed this: When we split a full node, we can remove the median key and end up with same number of pointers

[cesarghali]

Wouldn't this change the structure of the non-leaf node? I think I need to discuss this in person when we meet.

Btw, there's something else that we missed, the + part of the B+ Tree :) which is having all leaf nodes linked in a list.

[diedthreetimes]

I use the linked list bit but insert isn't finished. Linking comes into
play when nodes start splitting.
On May 19, 2013 11:09 AM, "Cesar Ghali" notifications@github.com wrote:

Wouldn't this change the structure of the non-leaf node? I think I need to
discuss this in person when we meet.

Btw, there's something else that we missed, the + part of the B+ Tree :)
which is having all leaf nodes linked in a list.

—
Reply to this email directly or view it on GitHubhttps://github.com//issues/13#issuecomment-18121990
.