Skip to main content

B+ Tree

B+ Tree

  • The B+ tree 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 an 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 a leaf node.



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 the next leaf node.

Searching a record in B+ Tree

Suppose we have to search 55 in the below B+ tree structure. First, we will fetch for the intermediary node which will direct to the leaf node that can contain a record for 55.

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.


B+ Tree Insertion

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 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 the tree without affecting the fill factor, balance, and order.


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 have 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.

This is how we can insert an entry when there is an overflow. In a normal scenario, it is very easy to find the node where it fits and then place it in that leaf node.


B+ Tree Deletion

Suppose we want to delete 60 from the above example. In this 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 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 the above B+ tree and re-arranging the nodes, it will show as follows:


Labels:

Comments

Post a Comment

Please do not enter any spam link in the comment box.

Popular posts from this blog

DBMS Keys

DBMS Keys KEYS in DBMS is an attribute or set of attributes which helps you to identify a row (tuple) uniquely in a relation(table). They allow you to find the relation between two tables. Keys help you uniquely identify a row in a table by a combination of one or more columns in that table. Key is also helpful for finding unique record or row from the table. Database key is also helpful for finding unique record or row from the table. Example: Employee ID FirstName LastName 11 Andrew Johnson 22 Tom Wood 33 Alex Hale In the above-given example, employee ID is a primary key because it uniquely identifies an employee record. In this table, no other employee can have the same employee ID. Here are some reasons for using sql key in the DBMS system. Keys help you to identify any row of data in a table. In a real-world application, a table could contain thousands of records. Moreover, the records could be duplicated. Keys in RDBMS ensure that you can uniquely identify a table record despite ...
Post a Comment
Read more

Colors in CSS

Ways to declare Colors in CSS (Image by - Sharma Guides | Subham232330) 1. Color Name 2. Hex Value 3. RGB() and RGBA() 4. HSL() and HSLA() 5. HWB() * Color Name:- background-color:red; * HEX Value:- background-color:#001122; * RGB():- background-color:rgb(25,31,52); * RGBA():- background-color:rgba(0,0,0,1.5);          |           Transparency The hexadecimal system uses values from 0 to 255 but in RGB we can use 0% to 100% as well.
Post a Comment
Read more

Computer Short Questions

Computer Short Questions & Answers: 1. What is any part of the computer that you can physically touch? – Hardware 2. Which generation of computers is still under development? – Fifth 3. What is the most common storage device for the personal computer? – Hard Disk Drive 4. Which key is used in combination with another key to perform a specific task? – Control 5. What is the pattern of printed lines on most products? – Barcodes 6. To make the number pad act as a directional arrow, we press which key? – Shift 7. Which devices let the computer communicate with you? – Input 8. What is the most frequently used piece of hardware for inputting data? – Hardware 9. What is the place where the computer stores programs and data? – Storage unit 10. What is the process of dividing the disk into tracks and sectors? – Formatting 11. What is the space in your computer that loads’ and works with data? – RAM memory 12. What is the storage which stores or retains data after power off? – Non-volatile s...
Post a Comment
Read more