B+ Tree File Organization in DBMS

Similar to ISAM file organization, B+ file organization also works with key & index value of the records. It stores the records in a tree like structure, that is why it is also known as B+ Tree file organization. In B+ file organization, the leaf nodes store the records and intermediate nodes only contain the pointer to the leaf nodes, these intermediate nodes do not store any record.

Root node and intermediate nodes contain key field and index field. The key field is a primary key of record which can be used to distinctly identify a record, the index field contains the pointer (address) to the leaf node where the actual record is stored.

B+ Tree Representation:

Let’s say we are storing the records of employees of an organization. These employee records contain fields such as Employee_id, Employee_name, Employee_address etc. If we consider Employee_id as primary key and the values of Employee_id ranges from 1001 to 1009 then the B+ tree representation can be as follows.

• The important point to note here is that the records are only stored at the leaf nodes, other records contains the key and index value (pointer to leaf node).
• Leaf Node 1001 means that it stores the complete record of the employee where employee id is “1001”. Similarly nodes 1002 stores the record of employee with employee id “1002” and so on.
• The main advantage of B+ file organization is that searching a record is faster. This is because all the leaf nodes (where the actual record is stored) are at the same distance from the root node and can be accessed faster.
• Since intermediate nodes do not contain the records and only contains the pointer to the leaf nodes, the height of the B+ tree is shorter that makes the traversing easier and faster.

Advantages of B+ Tree File Organization

1. Searching is faster: As we discussed earlier, since all the leaf nodes are at minimal distance from the root node, searching a record is faster in B+ tree file organization.
2. Flexible: Adding new records and removing old records can be easily done in a B+ tree as the B+ tree is flexible in terms of size, it can grow and shrink based on the records that needs to be stored. It has no restriction on the amount of the records that can be stored.
3. Allows range retrieval: It allows range retrieval. For example, if there is a requirement to fetch all the records from a certain range, then it can be easily done using this file organization method.
4. Allows partial searches: Similar to ISAM, this also allows partial searches. For example, we can search all the employees where id starts with “10“.
5. Better performance: This file organization method gives better performance than other file organization methods for insert, update, delete operations.
6. Re-organization of records is not necessary to maintain performance.

Disadvantages of B+ Tree file Organization

1. Extra insertion and deletion cause space overhead.
2. This method is not suitable for static tables as it is not efficient for static tables compared to other file organization methods.