Tuesday, July 28, 2020

B+ Tree File Indexing

B+ Tree File Indexing

The concept of B+ Tree is used to store records in secondary memory. If records are stored using this concept, those files are called B+ tree index files. Since this tree is balanced and sorted, all nodes will be equally spaced and only the leaf node has an actual value, B+ Tree makes finding any records in index files easy and quick. Even insertion / deletion in the B+ Tree does not take long. Therefore B+ Tree creates an efficient method for storing records.

Searching, inserting, and deleting records is done in the same way as we have seen above. Since it is a balanced tree, it searches for the position of the record in the file, and then it inserts / deletes the record. If it is found that the tree will become unbalanced due to insert / delete / update, then it rearranges the nodes properly so that the definition of the B+ Tree does not change.

Below is a simple example of how student descriptions are stored in B+ Tree index files.

Suppose we have a new student, Brian. Where will it fit in the file? It will fit into 1 leaf node. Since this leaf node is not complete, we can easily add it to the node.

But what if we want to add another student Ben to this file? Some re-arrangement is required for nodes to maintain file balance.

The same thing happens when we also delete.


1) Automatically recognize itself with small local changes in the face of insertion and deletion.
2) B+ Trees are used extensively


1) Performance degrades as the file grows.
2) Extra insertion and deletion overhead space overhead.

No comments:

Post a Comment