B+ trees for indexing in Data Structures Theory - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding the structure of B+ trees

Which statement correctly describes a key structural property of B+ trees used for indexing?

A All keys are stored only in the leaf nodes, and internal nodes store only keys to guide the search.

B Keys are stored in both internal and leaf nodes, with duplicates allowed in internal nodes.

C Only the root node stores keys, and all other nodes store data pointers without keys.

D Leaf nodes store only pointers to data, and internal nodes store both keys and data.

💡 Hint

Think about where the actual data entries are stored in a B+ tree.

In B+ trees, all actual data records are stored in the leaf nodes. Internal nodes only contain keys to direct the search path, not the data itself.

📋 Factual

intermediate

Order and node capacity in B+ trees

For a B+ tree of order m, what is the maximum number of children an internal node can have?

A m - 1

B 2m

C m + 1

D m

💡 Hint

Recall the definition of order in B+ trees related to children count.

In a B+ tree of order m, each internal node can have at most m children and at least ⌈m/2⌉ children (except root).

🔍 Analysis

advanced

Effect of node splitting on B+ tree height

When inserting a new key causes a leaf node to split in a B+ tree, what is the immediate effect on the tree's height?

A The height decreases because nodes are redistributed.

B The height always increases by one.

C The height remains the same unless the root node splits.

D The height doubles due to node splitting.

💡 Hint

Consider when the root node splits during insertion.

Splitting a leaf node adds a new node at the same level. The tree height only increases if the root node splits, creating a new root.

❓ Comparison

advanced

Difference between B and B+ trees in indexing

Which of the following best distinguishes a B+ tree from a B tree in the context of database indexing?

A B+ trees store all data pointers in leaf nodes only, while B trees store data pointers in all nodes.

B B trees have linked leaf nodes, but B+ trees do not.

C B+ trees allow duplicate keys in internal nodes, B trees do not.

D B trees use binary search internally, B+ trees use linear search.

💡 Hint

Think about where the actual data records are stored in each tree type.

B+ trees store all data pointers in leaf nodes and link these leaves for efficient range queries. B trees store data pointers in all nodes, not just leaves.

❓ Reasoning

expert

Range query efficiency in B+ trees

Why are B+ trees particularly efficient for range queries compared to other tree structures?

A Because B+ trees use hashing internally for quick lookups.

B Because leaf nodes are linked sequentially, allowing fast traversal of consecutive keys.

C Because internal nodes store all data, reducing the need to visit leaves.

D Because B+ trees store keys in a random order to balance search paths.

💡 Hint

Consider how leaf nodes are connected in B+ trees.

B+ trees link their leaf nodes in a linked list, enabling efficient sequential access to keys in order, which makes range queries fast.