jielouis341
jielouis341

Reputation: 1

B+ Trees internal nodes

I was working through a textbook and got stuck on this question:

"Consider a B+ Tree where each leaf block can contain a maximum of 3 records, each internal block can contain a maximum of 3 keys, all record blocks in the tree are fully occupied with 3 records each and the records have key values: 5,10,15,..., and there are 4 record blocks in the file"

Question: "Draw this tree in a single diagram"

So far I've added all the records in the leaf level, there's 4 blocks with 3 keys so 12 values total, so my leaf level has all multiples of 5 from 5 to 60. I'm now stuck on what to add on the level above it (internal block).

Upvotes: 0

Views: 599

Answers (1)

trincot
trincot

Reputation: 350137

You have already done the right thing for the leaf level. There is only one internal block needed, which will have 4 pointers to those leaf blocks, and 3 keys. Those 3 keys are keys that typically are copies from the least keys in the blocks below that block. No key of the first block is repeated in that internal block, only of the other blocks.

One way of illustrating this structure, is like this:

enter image description here

Often the leaf blocks are linked together, in a singly or doubly linked list, although this is not a strict requirement for B+ trees. I have not depicted this above.

Upvotes: 1

Related Questions