Why does this B+ tree have repeated elements?

In this B+ tree 5 开发者_运维百科appears twice.

B+ tree

From Wikipedia:

In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.

Each of the keys in a non-leaf node has to be repeated in one of the children and so on down until they reach a leaf because that's where the data is stored. In a B-tree the data can be stored in non-leaf nodes so there is no need to repeat a key lower down the tree.

If you notice, the key 3 is also repeated in the diagram of the B+ tree for the same reason - the data cannot be stored in the root node. It must be stored in the child, which is a leaf node.

A B+ tree is distinguished from a B-tree by the fact that all records appear in the leaf nodes. That is why the 5 appears in the bottom row.

In a B+ tree (like a B-tree) the keys appear in nodes above the leaves so that the records may be found. That is why the 5 appears in the second-to-bottom row.

So 5 appears twice. Once to find the record, and once for the record itself.

From Wikipedia:

It is a dynamic, multilevel index, with maximum and minimum bounds on the number of keys in each index segment (usually called a "block" or "node"). In a B+ tree, in contrast to a B-tree, all records are stored at the leaf level of the tree; only keys are stored in interior nodes.

The 3 and 5 in the top are index keys, pointing out the maximum key in each block.