Learning objectives
What you will be able to explain
- In a B+ Tree, which statement regarding path lengths is correct?
- Which of the following are characteristics of a B+ Tree? (Select all that apply)
- In a B+ Tree (as opposed to a standard B-Tree), where are the actual data pointers (or records) stored?
- State whether each statement is True or False:
- Match the node type to its primary function:
- Calculate the maximum number of keys (n) that can fit in a single B+ Tree node given:
Section 01
In a B+ Tree, which statement regarding path lengths is correct? to In a B+ Tree (as opposed to a standard B-Tree), where are the actual data pointers (or records) stored?
01
In a B+ Tree, which statement regarding path lengths is correct?
B+ Trees are height-balanced by definition, so every search reaches a leaf in the same number of steps. This guarantees predictable lookup cost and avoids insertion-order skew seen in ordinary binary search trees.
02
Which of the following are characteristics of a B+ Tree? (Select all that apply)
In a B+ Tree, internal nodes route searches while leaf nodes hold record pointers, so A is correct and B is not. Leaves are linked for fast ordered scans (C), and non-root nodes obey minimum occupancy (typically at least half full), which makes D correct.
03
In a B+ Tree (as opposed to a standard B-Tree), where are the actual data pointers (or records) stored?
A key B+ Tree property is that data pointers are stored only in leaf nodes; internal nodes store separator keys and child pointers. This increases internal fan-out and keeps the tree shallower for disk access.
Section 02
State whether each statement is True or False: to Calculate the maximum number of keys (n) that can fit in a single B+ Tree node given:
01
State whether each statement is True or False:
1) False: an internal node with n keys has n+1 child pointers. 2) True: the root has special relaxed occupancy rules. 3) True: leaf-level sibling links support range scans. 4) True: non-root internal nodes must satisfy the minimum pointer occupancy rule.
02
Match the node type to its primary function:
Root is the entry point and may be the only node in small trees, so 1-B. Internal nodes guide traversal and do not point to table records directly, so 2-A. Leaf nodes contain search keys plus record/RID pointers, so 3-C.
03
Calculate the maximum number of keys (n) that can fit in a single B+ Tree node given:
Available payload is 1024 - 16 = 1008 bytes. A node with n keys needs n key slots and n+1 pointers: 8n + 8(n+1) <= 1008 -> 16n + 8 <= 1008 -> n <= 62.5. Taking the largest integer gives 62 keys.
Guided checkpoint
- Block size: 1024 bytes
- Key size: 8 bytes
- Pointer size: 8 bytes
- Metadata (header): 16 bytes
Section 03
What does the term "Fan-out" represent in the context of B+ Trees? to In a B+ Tree of order n=10, what is the minimum number of keys an internal node (that is not the root) must contain?
01
What does the term "Fan-out" represent in the context of B+ Trees?
Fan-out is the number of children an internal node can reference (often considered max or average). Higher fan-out reduces tree height, which directly lowers disk I/O per lookup.
02
Why are B+ Trees preferred over Binary Search Trees for disk-based databases? (Select all that apply)
B+ Trees are block-oriented and have high fan-out, so they stay shallow and minimize random disk reads. That makes A, B, and C correct; memory usage versus binary trees is not the core reason for their DBMS dominance.
03
In a B+ Tree of order n=10, what is the minimum number of keys an internal node (that is not the root) must contain?
For order n=10 (max children 11), a non-root internal node must have at least ceil((n+1)/2)=ceil(11/2)=6 child pointers. Since keys = pointers - 1, the minimum is 5 keys.
Section 04
What is the unique property of the root node regarding the "50% full" rule? to Why are range queries (e.g., "Find all records where 20 < age < 30") efficient in B+ Trees?
01
What is the unique property of the root node regarding the "50% full" rule?
The root is exempt from the standard minimum-fill rule that applies to other nodes. It may have very few entries (e.g., one key and two pointers) and still remain valid.
02
A B+ Tree stores 1,000,000 records. Each leaf can hold 100 records. If the average fan-out of internal nodes is 100, how many levels (height) will the tree have?
Leaves needed are 1,000,000 / 100 = 10,000. One internal level above leaves needs 10,000 / 100 = 100 nodes, and one more level gives the single root (100 / 100 = 1). So the tree has 3 levels total.
03
Why are range queries (e.g., "Find all records where 20 < age < 30") efficient in B+ Trees?
Range scans in B+ Trees are efficient because once the first matching leaf is found, the engine can continue through linked leaves in key order. It avoids repeated root-to-leaf traversals for nearby keys.
Section 05
When a leaf node is full and a new key is inserted, what happens? (Select all that apply) to Identify the difference:
01
When a leaf node is full and a new key is inserted, what happens? (Select all that apply)
A full leaf split creates two leaves (A), inserts/promotes a separator key to the parent (B), and can propagate upward. If that propagation splits the root, tree height increases (D). Overflow pages are not the normal B+ Tree strategy.
02
When an internal node splits, what happens to the median key?
On internal-node split, the median separator is promoted to the parent and removed from the lower node level. This preserves search partition boundaries and node occupancy constraints.
03
Identify the difference:
Classic B-Trees may store data pointers in internal and leaf nodes, while B+ Trees keep data pointers only at leaves. That separation is a key structural difference and why the mapping is 1-A, 2-B.
Section 06
State whether each statement is True or False: to In a B+ Tree with height H=4 (Root at level 1), how many nodes must be accessed to find a single record?
01
State whether each statement is True or False:
1) True: deletion can trigger underflow. 2) False: systems try redistribution first when siblings have spare entries. 3) True: borrowing usually costs less than merging. 4) False: repeated merges can reach the root and reduce tree height.
02
What is the primary goal of a B* Tree?
B* Trees aim for higher node utilization (about two-thirds full) than standard B+ Trees (about half full). Better occupancy improves space usage and often reduces height for the same data volume.
03
In a B+ Tree with height H=4 (Root at level 1), how many nodes must be accessed to find a single record?
A point lookup follows exactly one path from root to leaf. With height H=4 (root included), one node is visited per level, so 4 node accesses are required.
Section 07
What is the advantage of a Prefix B+ Tree (or Trie-based B+ Tree)? to According to the slides, what are common use cases for B+ Trees? (Select all that apply)
01
What is the advantage of a Prefix B+ Tree (or Trie-based B+ Tree)?
Prefix/trie-style B+ variants compress internal keys by storing only distinguishing prefixes. That reduces internal-node storage and can increase fan-out, improving lookup performance.
02
Why is "Bulk Loading" more efficient than inserting records one-by-one?
Bulk loading uses presorted input to fill leaves and build parent levels bottom-up. It avoids repeated root-to-leaf inserts and many split operations, making construction far cheaper than incremental insertion.
03
According to the slides, what are common use cases for B+ Trees? (Select all that apply)
B+ Trees are widely used for unique indexes/constraints, index nested-loop join lookups, and both point and range retrieval. They are indexing structures, not a format for large media-object storage.
Section 08
A B+ Tree node of order n=4 is considered legal if it contains how many keys (assuming it is not the root)? to What is the purpose of the additional "right-link" pointers in B-Link-Trees?
01
A B+ Tree node of order n=4 is considered legal if it contains how many keys (assuming it is not the root)?
For order n=4, max children are n+1=5. A non-root internal node must have at least ceil(5/2)=3 children, which corresponds to at least 2 keys, and up to 4 keys at maximum. So 2 to 4 is legal.
02
If we bulk load 13 data entries into a B+ Tree of order N=4, what is the primary benefit mentioned in the example?
With sorted input, bulk loading writes leaves and upper levels sequentially with minimal rewrites. The key practical benefit in this example is that each block is produced once instead of repeatedly modified by splits.
03
What is the purpose of the additional "right-link" pointers in B-Link-Trees?
B-Link-Tree right-links allow concurrent readers/writers to tolerate in-progress splits. If a search lands on an older node image, it can follow the right-link to find the correct new sibling.
Section 09
Rank the complexity of B+ Tree operations (N = total elements, F = fan-out): to What characterizes a Cache-Sensitive B+ Tree?
01
Rank the complexity of B+ Tree operations (N = total elements, F = fan-out):
Search and insert each traverse root-to-leaf paths, giving O(log_F N) behavior where F is fan-out. Space grows linearly with data volume and index entries, so overall space is O(N).
02
The link from one leaf to the next allows the DBMS to avoid:
Leaf-to-leaf links let sequential/range scans continue directly at leaf level. Without those links, scans would repeatedly climb and descend through internal nodes.
03
What characterizes a Cache-Sensitive B+ Tree?
Cache-sensitive B+ Trees optimize CPU locality by arranging child nodes contiguously and sizing node layouts to cache-line boundaries. They are not limited to residing only in L1 cache.
Section 10
What problem does the B+ Tree solve that static multi-level indexes (like ISAM) struggle with? to How many records can a 2-level B+ Tree (Root + Leaves) hold if: Root fan-out: 100 pointers. Each leaf can hold 20 records.
01
What problem does the B+ Tree solve that static multi-level indexes (like ISAM) struggle with?
Unlike static structures such as ISAM, B+ Trees adapt online to inserts and deletes through split/merge/redistribution while preserving balance. This keeps lookup performance stable as data changes.
02
State whether each statement is True or False:
1) True: internal pointers reference child B+ Tree pages. 2) True: leaf entries point to records or RIDs. 3) False: internal nodes generally have one more pointer than keys. 4) True: height grows or shrinks as the table size changes.
03
How many records can a 2-level B+ Tree (Root + Leaves) hold if: Root fan-out: 100 pointers. Each leaf can hold 20 records.
A 2-level tree has one root whose fan-out determines the number of leaves. With 100 leaf pointers and 20 records per leaf, total capacity is 100 x 20 = 2,000 records.
Knowledge check
Turn understanding into recall.
The quiz now follows the same concepts in scored form. You can return to this lesson from the quiz whenever a gap appears.