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
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?
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?
