Full width home advertisement

Welcome Home


Post Page Advertisement [Top]


What is B+ Tree in DBMS?
                                                       
A B+ tree is an equilibrated binary search tree that follows a multi-level index format. The leaf nodes of a B+ tree stand for actual data pointers. B+ tree makes sure that all leaf nodes remain at the same height, therefore balanced. 

Structure of B+ Tree in DBMS

Every leaf node is at equal distance from the root node. A B+ tree is of the order n where n is fixed for every B+ tree.

1. Internal nodes:
a. Internal (non-leaf) nodes include at least ⌈n/2⌉ pointers, except the root node.
b. At most, an internal node can have n pointers.]
                                                 
2. Leaf nodes:
a. Leaf nodes have at least ⌈n/2⌉ record pointers and ⌈n/2⌉ key values.
b. At most, a leaf node can include n record pointers and n key values.
c. Every leaf node has one block pointer P to point to next leaf node and forms a linked list.

B+ Tree Insertion

1. B+ trees are filled from bottom and each entry is made at the leaf node.

2. If a leaf node overflows:
a. Divide node into two parts.
b. Partition at i = ⌊(m+1)/2⌋.
c. First i entries are saved in one node.
d. Rest of the entries (i+1 onwards) are moved to a new node.
e. The key is duplicated at the parent of the leaf.

3. If a non-leaf node overflows:
a. Divide node into two parts.
b. Partition the node at i = ⌈(m+1)/2⌉.
c. Entries up to i are kept in one node.
d. Rest of the entries are moved to a new node.

B+ Tree Deletion

1. B+ tree entries are deleted at the leaf nodes.

2. The target entry is searched and deleted.
a. If it is an internal node, delete and replace with the entry from the left position.

3. After deletion, underflow is tested,
a. If underflow occurs, distribute the entries from the nodes left to it.

4. If distribution is not possible from left, then
a. Distribute the entries from the nodes right to it.

5. If distribution is not possible from left or from right, then

a. Merge the node with left and right to it.

No comments:

Post a Comment

Bottom Ad [Post Page]