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