B+ tree memory management


How is B+ tree used to manage Primary and Secondary memory?


We run program in the main memory which fetches data from the secondary memory.

Now, we need to look at how is data stored in the disk. The disk is logically divided into tracks (along the radius) and sectors (along the circumference). The intersection of each tracks and sectors are called blocks. So, in order to fetch a data, we need to go to a particular address of a particular block.

The time consumed to search the necessary block linearly is considerably large. Hence, we consider B+ tree indexing. In a B+ tree all the records are maintained at the leaf nodes and only the leaf nodes are provided with record pointer. Leaf nodes are linked together in the form of a singly linked lists to make the search queries more efficient… As the number of records grow over a specified value, the leaf nodes split to produce a mother node with a key and links to its child nodes. Here we need to remember the key in the mother node is actually a copy of record from one of its child node. While a node is already full and if a new data is to be added, the node splits and a key is promoted to its mother node. This continues till there is available capacity in the mother node, which in subsequent times, on further addition of record, splits to give rise to a new level. This is how multilevel indexing is established with a root maintaining the fixed relation that, a child with lower value be at a particular side to its mother while value higher be at the other side. Thus while searching for/ reading/ writing on a particular record, we will fetch for the intermediary node which will direct to the leaf node that can contain record like it’s performing as a binary search and is more time efficient. The performance remains the same because all the records are maintained at leaf node and all the nodes are at equi-distance from root. If there is any overflow, it automatically re-organizes the structure.

This is how B+ tree is used to manage primary and secondary memory.