B+ tree

Question

In B+ tree deletion,

1) What would happen, if a node to be deleted is a right child? (Since, many books are considering deletion on left node only)

2) How redistribution would happen, if there is a tree with order p = 7, and there are 2 children of root node where

• left child has 3 entries and right child has 7 entries, and 1 entry of left child is to be deleted?
• left child has 7 entries and right child has 3 entries, and 1 entry of right child is to be deleted?

3) Any good reference to study B+ tree & B tree?

Answer 1

B-trees are  commonly used in databases and file systems. 

A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves. B+ tree is a data structure often used in the implementation of database indexes.

1) B+ tree deletion :  https://web.eecs.umich.edu/~akamil/teaching/su02/080802.pdf

2) http://cs.stackexchange.com/questions/50384/how-the-deletion-takes-place-in-b-tree 

https://www.cs.princeton.edu/courses/archive/fall08/cos597A/Notes/BplusInsertDelete.pdf

3) B+ tree :  http://sketchingdream.com/blog/b-plus-tree-tutorial/

B tree : http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/ 

Comments

Thank u Sir