Consider a B+ Tree where the maximum number of key values in each leaf node is 2 and the maximum number of pointers in each non-leaf node is 3. Let the content of the B+ Tree be as shown in the figure.
Which of the following options denotes the key value(s) stored in the root node after inserting a key value 3 in the given B+ Tree?
To understand how the B+ Tree changes after inserting the key value 3, let's go through the steps:
Current Structure:
1. The root node currently has keys 5 and 8, with three pointers to leaf nodes. Each leaf node can have a maximum of 2 key values, and each non-leaf node can have a maximum of 3 pointers.
2. Before the insertion, the leaf nodes contain:
- Leaf Node 1: Keys 1, 5
- Leaf Node 2: Keys 7, 8
- Leaf Node 3: Keys 9, 12
3. We want to insert the key 3. The appropriate place for 3 is in Leaf Node 1 as it should be in sorted order and 3 is between 1 and 5.
Insertion and Splitting:
- Insert 3 into Leaf Node 1: This would make it contain [1, 3, 5], which exceeds the maximum of 2 keys per leaf node.
- Split Leaf Node 1:
- The left split will contain [1, 3].
- The new leaf (a right split) will contain [5].
- After splitting, promote the smallest key of the right split to the parent. Here, the new key promoted is 5.
Updated Structure:
After the insertion and necessary splitting, the structure of the B+ Tree becomes:
- Root contains the key 5. The existing 8 remains as it is, since no new key surpasses it.
- The tree structure will thus appear as:
The root node now only holds the key 5. Since 5 and 8 will need to be evaluated together if other nodes need adjustment, it still logically remains as one of the root keys.
Conclusion: Therefore, the root node stores the key value 5 after inserting the key value 3.
Important Questions from Indexing
- In a relational database, a B+ Tree Index is to be constructed for a relation on a key field. In a B+ Tree, a Node Pointer points to a sub-tree and a Data Record Pointer points to a block of database records.
Let, Node size = 4096 bytes, Node Pointer size = 10 bytes, Search Key Field size = 11 bytes and Data Record Pointer size = 12 bytes.
The maximum number of Node Pointers that can be present in a non-leaf node of the B+ Tree is ________ . (Answer in integer) An OTT company is maintaining a large disk-based relational database of different movies with the following schema:
Movie(ID, CustomerRating)
Genre(ID, Name)
Movie_Genre(MovieID, GenreID)
Consider the following SQL query on the relation database above:
SELECT *
FROM Movie, Genre, Movie_Genre
WHERE
Movie.CustomerRating > 3.4 AND
Genre.Name = “Comedy” AND
Movie_Genre.MovieID = Movie.ID AND
Movie_Genre.GenreID = Genre.ID;
This SQL query can be sped up using which of the following indexing options?
Primary index in sequential order file organisation is also known as ______.
The total cost of retrieving records in sorted order using an unclustered B+ tree is
(P-Average number of records per data page
N-Data pages
F-Ratio of the size of a data entry to the size of a data record)
- Consider $B^+$ tree in which the maximum number of keys in a node is 5. What is the minimum number of keys in any non-root node?
