CODEWITHSUNDEEP
b-tree
Aditya Sharma
Aditya Sharma

Reputation: 389

Structure of B+ trees

According to the properties of B+ trees,every node except the root has to be atleast half filled. But suppose we have a B+ tree with a node capable of holding maximum of 3 KEYS.Then how much minimum number of entries(not pointers) should be there in a node of a B+ tree.Is it 2 or 1?. According to http://www.cburch.com/cs/340/reading/btree/index.html in the first figure it has only 1 entry(16) in the right child of the root.

.

Upvotes: 2

Views: 375

Answers (1)

JJoao
JJoao

Reputation: 5357

Then how much minimum number of entries(not pointers) should be there in a node of a B+ tree.Is it 2 or 1?.

1 ("Every non-leaf, non-root node has at least floor(d / 2) children.") => 2 children => 1 key

This is not in fact the real picture. B+ trees are design to work on disk (to be stored in a file), so each tree node will use a disk block or multiple of disk block size. In normal cases B+ trees have nodes of for example 100 keys. (but it is much easier to explain the algorithms with small size trees).

Thank you for the excelente B+ Tree reference.

Upvotes: 2

Related Questions