B+ Tree File Organization

PRASHANT SINGH
Last Updated: May 13, 2022

Introduction  

Before we start learning about B+ tree file organization, refer to the Introduction to file organization blog to know more about types of file organization.

A File is a collection of records stored in binary format. File organization is a logical relationship between various records. File organization defines how file records are mapped onto disk blocks.

There are various types of file organization. These methods have their pros and cons accordingly. These methods may be efficient for certain types of selection. Meanwhile, they will be inefficient for other selection.

So, the developer or the programmer decides the best-suited file organization method depending on his requirement according to the situation. Some of the file organizations are as follows:

  • Sequential File Organization
  • Indexed Sequential Access Method(ISAM)
  • Heap File Organization
  • Hash File Organization
  • B+ Tree File Organization
  • Cluster File Organization

To know about these file organizations, you can refer to this blog.

Now, we will learn about B+ tree file organization in detail.

B+ Tree File Organization:

As the name suggests, it uses a tree-like structure to store the records in files.

It uses the concept of key-index. In this, the primary key is used to sort the records. For each primary key, the indexed value is generated and mapped with the record.

In B+ tree file organization, all the records are stored at the leaf node. Intermediate nodes in the tree act as a pointer to the leaf nodes and do not contain any records.

B+ tree:

B+ tree is similar to binary search tree, and the only difference is that the B+ tree can have more than two children while BST(binary search tree) can only have two children. The leaf nodes of a B+ tree are linked together in the form of a singly linked list so that searching the data is more efficient and quick.

Advantages of using B+ trees

Some of the advantages of using B+ trees are

  • Records can be fetched in an equal number of disk accesses.
  • We can also access the records stored in a B+ tree sequentially and directly.
  • Keys are used for indexing in B+ trees.
  • Since the data is stored in leaf nodes only, searching the queries is faster.

Example to understand the B+ tree :

In the above example:

  • There is only one root node of the tree ,i.e., 30.
  • An intermediary layer of nodes acts as a pointer to leaf nodes. These nodes do not store the actual records.
  • The nodes to the left of the root node contain the prior value of the root ,i.e., 20 and 40, respectively.
  • There is only one leaf node that has values, i.e, 10,15,22,25,27,32,35.
  • Searching any record is easier as all the leaf nodes are already balanced.

Pros of B+ tree file organization

  • Searching is very efficient as all the records are stored only in leaf nodes, in a sequential linked list (in a sorted manner).
  • Traversing the tree is easier and faster.
  • The size of the B+ tree has no restrictions, which means it can grow or shrink dynamically according to increase or decrease in the number of records.
  • It is a balanced tree structure, which means any insert, update, or delete operation does not affect the performance of the tree.

Cons of B+ tree file organization

The main drawback of B+ tree file organization is that it is not efficient for static tables.

Frequently Asked Questions

  1. What is sequential file organization?

Each file records contain a data attribute that uniquely identifies the record. Records are placed in the file in sequential order based on the unique key field or search key. But, practically, it is impossible to store all the records sequentially in physical form. This method is efficient for the massive amount of data, and it is simple in design.

 2. What is Hash file organization, and what are its advantages?

In Hash file organization, a hash function is used to calculate the addresses of the memory blocks used to store the records. The hash function can be any mathematical function that is either simple or complex. The hash function is applied to some attributes or columns (key or non-key columns) to get the address of the block. That's why it is also known as Direct file organization. Hash file organizations work on the principle of hashing.

  Advantages of Hash file organization are:

  • In this, records do not need to be sorted sequentially after every transaction; hence it becomes more efficient(since the effort of sorting is reduced).
  • The address of the block is known by the hash function, which makes it significantly faster to access or search the record in the memory.
  • Since accessing the record is quick, deleting and updating will be very quick.
  • This method is suitable for online transactions systems like online banking, ticket booking systems, etc.
     

3. What is a BST(Binary Search Tree)?

A BST is a type of tree in which the values at the left node of the parent must be smaller than the parent node, and the value of the right node must be greater than the parent node. This rule is applied recursively to both the left and right subtrees of the tree's root.

Key Takeaways

In this blog, we start by introducing files and file organization in DBMS. Later we learn some  major types of file organization and then we study B+ tree file organization.

Then we learn about B+ trees and their advantages. We also learn about the pros and cons of using B+ tree file organization.

Visit here for the top 100 SQL problems asked in various product and service-based companies like Google, Microsoft, Infosys, IBM, etc.

Click here to learn more about different topics related to database management systems.

Also, try CodeStudio to practice programming problems for your complete interview preparation.

Was this article helpful ?
1 upvote

Comments

No comments yet

Be the first to share what you think