Scribd
Upload
26 views4 pages

B+ Tree Operations in File Systems

B+ Trees are self-balancing tree structures used in databases and file systems for efficient data management, with all keys stored in leaf nodes and internal nodes guiding searches. They maintain properties such as a maximum of 'n' children per node and perfect balance, allowing for efficient search, insertion, and deletion operations. The document illustrates B+ Tree operations through examples of inserting and deleting keys, demonstrating their dynamic nature and efficiency in data retrieval.

Uploaded by

Bhargav Ramakoti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
26 views4 pages

B+ Tree Operations in File Systems

B+ Trees are self-balancing tree structures used in databases and file systems for efficient data management, with all keys stored in leaf nodes and internal nodes guiding searches. They maintain properties such as a maximum of 'n' children per node and perfect balance, allowing for efficient search, insertion, and deletion operations. The document illustrates B+ Tree operations through examples of inserting and deleting keys, demonstrating their dynamic nature and efficiency in data retrieval.

Uploaded by

Bhargav Ramakoti
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

B+ Trees

 A B+ Tree is a type of self-balancing tree structure commonly used in databases


and file systems to maintain sorted data in a way that allows for efficient insertion,
deletion, and search operations.
 B+ Trees are an extension of B-Trees but differ mainly in the way they handle leaf
nodes, which contain all the key values and point to the actual records.

B+ Tree of order `n` has the following properties:

 Every node has a maximum of `n` children.


 Every node (except the root) has a minimum of `n/2` children.
 The tree is perfectly balanced, meaning that all leaf nodes are at the same level.
 All keys are stored in the leaf nodes, and the internal nodes act as 'guides' to locate
the leaf nodes faster.

Operations on B+ Trees:

Search: Starts at the root and traverses down the tree, guided by the key values in each
node, until it reaches the appropriate leaf node.

Insert: Inserts a new key-value pair and then reorganizes the tree as needed to maintain
its properties.

Delete: Removes a key-value pair and then reorganizes the tree, again to maintain its
properties.

Example of B+ Tree Operations

Let's say we have a B+ Tree of order 4, and we want to insert the keys `[10, 20, 5, 6, 12,
30, 7, 17]` into an initially empty tree.

-------------------

|| || || ||

-------------------

Insertion
1. Insert 10:

- The tree is empty, so 10 becomes the root.

[10]

2. Insert 20:

- There's room in the leaf node for 20.

[10, 20]

3. Insert 5:

- Still room in the leaf node for 5.

[5, 10, 20]

4. Insert 6:

- The leaf node is full; split it and promote the smallest key in the right node to be the
new root.

[10]

/ \

[5, 6] [10, 20]

5. Insert 12:

- Insert into the appropriate leaf node.


[10, , ]

/ \

[5, 6] [10, 12, 20]

6. Insert 30:

- Need to split the right leaf node, promote 20.

[10 , 20 ,]

/ | \

[5, 6] [10, 12] [20, 30]

7. Insert 7:

- Insert into the appropriate leaf node.

[10 , 20 , ]

/ | \

[5, 6, 7] [10, 12] [20, 30]

8. Insert 17:

- Insert into the appropriate leaf node and split.

[10 , 20 , ]

/ | \

[5, 6, 7] [10, 12] [17, 20, 30]

- Here, the middle internal node gets split, and 17 is promoted.

[10 , 17 , 20 ]

/ | | \

[5, 6, 7] [10, 12] [17] [20, 30]

Search (for 12):

- Start at the root, go down the second child because 12 > 10 and 12 < 17, and find 12 in
the corresponding leaf node.
Deletion (of 10):

1. Remove 10 from the leaf node.

[10 , 17 , 20 ]

/ | | \

[5, 6, 7] [12] [17] [20, 30]

2. Since the key 10 is also present in the internal node, we replace it with its in-order
predecessor (or successor based on design), which is 7.

[7 , 17 , 20 ]

/ | | \

[5, 6] [7, 12] [17] [20, 30]

And that's how B+ Trees work for search, insert, and delete operations. B+ Trees are
dynamic, adapting efficiently as keys are added or removed, which makes them quite
useful for databases where high-speed data retrieval is crucial.

You might also like