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)
B+ Tree Non-Leaf Node Structure
In a B+ Tree, non-leaf nodes are designed to store search keys and pointers to child nodes (sub-trees). A non-leaf node contains entries composed of a search key field and a node pointer. If a non-leaf node holds $P$ node pointers, it must accommodate $P-1$ search keys.
Calculating Maximum Node Pointers
The objective is to find the maximum number of Node Pointers ($P$) that can fit within a single non-leaf node, considering the specified node size and the sizes of its components.
Given parameters:
- Node Size = 4096 bytes
- Node Pointer Size = 10 bytes
- Search Key Field Size = 11 bytes
The constraint is that the total space consumed by the pointers and keys must not exceed the total Node Size.
The total size equation for a non-leaf node is:
$ P \times \text{Node Pointer Size} + (P-1) \times \text{Search Key Field Size} \le \text{Node Size} $
Substitute the provided values into the equation:
$ P \times 10 + (P-1) \times 11 \le 4096 $
Simplify and solve the inequality for $P$:
$ 10P + 11P - 11 \le 4096 $
$ 21P - 11 \le 4096 $
Add 11 to both sides:
$ 21P \le 4096 + 11 $
$ 21P \le 4107 $
Divide by 21:
$ P \le \frac{4107}{21} $
$ P \le 195.57... $
Since the number of pointers must be a whole number (integer), we take the floor of the result.
Result
The maximum number of Node Pointers that can be present in a non-leaf node is 195.
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)
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?
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?
