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

Languages in DBMS

Languages in DBMS Structured Query Language(SQL) as we all know is the database language by the use of which we can perform certain operations on the existing database and also we can use this language to create a database. SQL uses certain commands like Create, Drop, Insert, etc. to carry out the required tasks. These SQL commands are mainly categorized into five categories as: DDL – Data Definition Language DQL – Data Query Language DML – Data Manipulation Language DCL – Data Control Language TCL – Transaction Control Language Now, we will see all of these in detail. DDL (Data Definition Language): DDL or Data Definition Language actually consists of the SQL commands that can be used to define the database schema. It simply deals with descriptions of the database schema and is used to create and modify the structure of database objects in the database. DDL is a set of SQL commands used to create, modify, and delete database structures but not data. These commands are normally ...
Post a Comment
Read more

Indexing in DBMS

Indexing in DBMS Indexing is used to optimize the performance of a database by minimizing the number of disk accesses required when a query is processed.  The index is a type of data structure. It is used to locate and access the data in a database table quickly. Index structure: Indexes can be created using some database columns. The first column of the database is the search key that contains a copy of the primary key or candidate key of the table. The values of the primary key are stored in sorted order so that the corresponding data can be accessed easily.  The second column of the database is the data reference. It contains a set of pointers holding the address of the disk block where the value of the particular key can be found. Indexing Methods Ordered indices The indices are usually sorted to make searching faster. The indices which are sorted are known as ordered indices. Example: Suppose we have an employee table with thousands of record and each of which is 10 byte...
Post a Comment
Read more

SQL Injection

SQL Injection The SQL Injection is a code penetration technique that might cause loss to our database. It is one of the most practiced web hacking techniques to place malicious code in SQL statements, via webpage input. SQL injection can be used to manipulate the application's web server by malicious users. SQL injection generally occurs when we ask a user to input their username/userID. Instead of a name or ID, the user gives us an SQL statement that we will unknowingly run on our database. For Example - we create a SELECT statement by adding a variable "demoUserID" to select a string. The variable will be fetched from user input (getRequestString). demoUserI = getrequestString("UserId"); demoSQL = "SELECT * FROM users WHERE UserId =" +demoUserId; Types of SQL injection attacks SQL injections can do more harm other than passing the login algorithms. Some of the SQL injection attacks include: Updating, deleting, and inserting the data: An attack can mo...
Post a Comment
Read more