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
Primary index in sequential order file organisation is also known as ______.
A B-tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then maximum number of nodes that could be newly created in the process is
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)
- 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?
