ISAM B+trees
ISAM B+trees
ISAM B+trees
B+ Trees
in DBMS
ISAM-Indexed
Sequential Access
Method
The main disadvantage is that it takes a lot of space for storing index
values; hence when the records increase in number the number of
indexes also increases.
• When the new records are inserted, then these files have to be
reconstructed to maintain the sequence.
• When the record is deleted, then the space used by it needs to be
released. Otherwise, the performance of the database will slow down.
B+ Tree
• A B+ Tree is a more advanced self-balancing tree.
• All the values are present at the leaf level.
• B+ Tree in the data structure is a B Tree enhancement that enables
faster insertion, deletion, and search operations.
B+ tree
• It is a balanced binary search tree.
• It follows a multi-level index format.
• In the B+ tree, leaf nodes denote actual data pointers.
• B+ tree ensures that all leaf nodes remain at the same height.
• In the B+ tree, the leaf nodes are linked using a link list.
• Therefore, a B+ tree can support random access as well as sequential
access.
Structure of B+ Tree • In the B+ tree, every leaf node is at equal distance from the
root node. The B+ tree is of the order n where n is fixed for
every B+ tree.
• It contains an internal node and leaf node.
B+ Tree
Internal node
• An internal node of the B+ tree can contain at least n/2 record pointers
except the root node.
• At most, an internal node of the tree contains n pointers.
Leaf node
• The leaf node of the B+ tree can contain at least n/2 record pointers and
n/2 key values.
• At most, a leaf node contains n record pointer and n key values.
• Every leaf node of the B+ tree contains one block pointer P to point to
next leaf node.
• Suppose we have to search 55 in the above B+ tree structure.
Searching a First, we will fetch for the intermediary node which will direct
to the leaf node that can contain a record for 55.
record in B+ Tree • So, in the intermediary node, we will find a branch between 50
and 75 nodes. Then at the end, we will be redirected to the third
leaf node. Here DBMS will perform a sequential search to find
55.
• Suppose we want to insert a record 60 in the below structure. It will go to
the 3rd leaf node after 55. It is a balanced tree, and a leaf node of this
B+ Tree tree is already full, so we cannot insert 60 there.
• In this case, we have to split the leaf node, so that it can be inserted into
Insertion tree without affecting the fill factor, balance and order.
B+ Tree Insertion
• The 3rd leaf node has the values (50, 55, 60, 65, 70) and its current root node is
50. We will split the leaf node of the tree in the middle so that its balance is not
altered. So we can group (50, 55) and (60, 65, 70) into 2 leaf nodes.
• If these two has to be leaf nodes, the intermediate node cannot branch from 50.
It should have 60 added to it, and then we can have pointers to a new leaf node.
• Suppose we want to delete 60 from the above example. In this
B+ Tree case, we have to remove 60 from the intermediate node as well
as from the 4th leaf node too. If we remove it from the
Deletion intermediate node, then the tree will not satisfy the rule of the
B+ tree. So we need to modify it to have a balanced tree.
• After deleting node 60 from above B+ tree and re-arranging the
nodes