B+ tree index structure in DBMS Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a B+ tree in database indexing?

A B+ tree is a balanced tree data structure used in databases to store indexes. It keeps data sorted and allows fast search, insert, and delete operations by maintaining all values in leaf nodes linked sequentially.

intermediate

How does a B+ tree differ from a B-tree?

In a B+ tree, all actual data records are stored only at the leaf nodes, which are linked in a sequence. Internal nodes only store keys to guide searches. In contrast, a B-tree stores data in both internal and leaf nodes.

beginner

Why are leaf nodes in a B+ tree linked together?

Leaf nodes in a B+ tree are linked to allow efficient range queries and ordered traversal. This means you can quickly scan through a range of values without going back up the tree.

intermediate

What happens when a node in a B+ tree becomes full?

When a node is full, it splits into two nodes, and the middle key moves up to the parent node. This keeps the tree balanced and ensures that operations remain efficient.

beginner

What is the main advantage of using a B+ tree for database indexes?

The main advantage is that B+ trees provide fast and efficient access to data with logarithmic search time, support for range queries, and a balanced structure that keeps operations quick even as data grows.

Where are the actual data records stored in a B+ tree?

A Only in leaf nodes

B Only in internal nodes

C In both internal and leaf nodes

D Nowhere, B+ tree stores only keys

In a B+ tree, all actual data records are stored only in the leaf nodes.

Why are leaf nodes linked in a B+ tree?

A To store parent pointers

B To store duplicate keys

C To reduce tree height

D To speed up range queries and ordered traversal

Leaf nodes are linked to allow efficient scanning of data in order, which helps with range queries.

What triggers a node split in a B+ tree?

A When a node has too few keys

B When leaf nodes are unlinked

C When a node becomes full

D When the root node is empty

A node splits when it becomes full to maintain balance and efficiency.

Which of the following is NOT true about B+ trees?

A Data is stored only in internal nodes

B They allow fast search operations

C They keep data sorted

D Leaf nodes are linked sequentially

Data is stored only in leaf nodes, not internal nodes.

What is the main benefit of B+ trees in databases?

A They use less memory than hash indexes

B They provide fast, balanced access and support range queries

C They store data in random order

D They do not require balancing

B+ trees keep data balanced and sorted, enabling fast searches and efficient range queries.

Explain the structure of a B+ tree and how it supports efficient database indexing.

Think about how the tree keeps data sorted and balanced.

Describe what happens during a node split in a B+ tree and why it is important.

Consider how the tree grows and stays balanced.

Practice

1. What is the main purpose of a B+ tree index in a database?

easy

A. To speed up data retrieval by organizing keys in a balanced tree

B. To store data in a random order for faster insertion

C. To compress data to save storage space

D. To encrypt data for security

Solution

1. Step 1: Understand the role of B+ tree indexes

   B+ tree indexes organize keys in a balanced tree structure to allow quick searching.

2. Step 2: Compare options with B+ tree purpose

   Only To speed up data retrieval by organizing keys in a balanced tree describes speeding up data retrieval using a balanced tree, which matches B+ tree function.

3. Final Answer:

   To speed up data retrieval by organizing keys in a balanced tree -> Option A

4. Quick Check:

   B+ tree index purpose = speed up search [OK]

Hint: B+ trees speed up search by balanced key organization [OK]

Common Mistakes:

• Confusing B+ tree with data compression
• Thinking B+ tree encrypts data
• Assuming B+ tree stores data randomly

2. Which of the following is the correct property of a B+ tree node?

easy

A. Nodes are linked only vertically, not horizontally

B. Each node contains only data records, no keys

C. Leaf nodes contain only keys, internal nodes contain data records

D. Internal nodes contain keys and pointers, leaf nodes contain data pointers

Solution

1. Step 1: Recall B+ tree node structure

   Internal nodes hold keys and pointers to child nodes; leaf nodes hold keys and pointers to actual data.

2. Step 2: Match options with B+ tree node properties

   Internal nodes contain keys and pointers, leaf nodes contain data pointers correctly states internal nodes have keys and pointers, leaf nodes have data pointers.

3. Final Answer:

   Internal nodes contain keys and pointers, leaf nodes contain data pointers -> Option D

4. Quick Check:

   B+ tree node structure = internal keys + leaf data [OK]

Hint: Internal nodes hold keys; leaves hold data pointers [OK]

Common Mistakes:

• Thinking leaf nodes have no keys
• Believing nodes link only vertically
• Confusing data records with keys in internal nodes

3. Consider a B+ tree of order 3 (each node can have max 3 children). If we insert keys 10, 20, 5, 6, 12 in order, what will be the root node's keys after all insertions?

medium

A. [6, 12]

B. [5, 6, 10]

C. [10]

D. [12, 20]

Solution

1. Step 1: Insert keys step-by-step in B+ tree order 3

   Insert 10, 20, 5 fills root node keys [5,10,20]. Inserting 6 causes split because max keys is 2 (order 3 means max 2 keys per node). The middle key 10 moves up as root key.

2. Step 2: Determine root keys after split

   After split, root has key [10], left child has [5,6], right child has [12,20].

3. Final Answer:

   [10] -> Option C

4. Quick Check:

   Order 3 split root key = 10 [OK]

Hint: Order 3 means max 2 keys; middle key moves up on split [OK]

Common Mistakes:

• Assuming root keeps all keys without split
• Confusing order with max keys per node
• Forgetting to move middle key up on split

4. A B+ tree index is not updating correctly after inserting a new key. Which of the following is the most likely cause?

medium

A. The tree height is too large

B. The leaf nodes are not linked properly after split

C. The root node contains too many keys

D. The keys are not sorted in the leaf nodes

Solution

1. Step 1: Identify common B+ tree update issues

   When inserting keys, leaf nodes must be linked in order to maintain correct traversal and range queries.

2. Step 2: Analyze options for update failure

   If leaf nodes are not linked properly after split, the index will not update correctly. Other options are less likely causes.

3. Final Answer:

   The leaf nodes are not linked properly after split -> Option B

4. Quick Check:

   Leaf node linkage error = update failure [OK]

Hint: Check leaf node links after splits for update issues [OK]

Common Mistakes:

• Blaming root node size without checking leaf links
• Ignoring leaf node order and linkage
• Assuming tree height causes update failure

5. You have a large database table and want to optimize range queries on a numeric column. Which feature of a B+ tree index makes it especially suitable for this task?

hard

A. Leaf nodes are linked in a sorted sequence allowing fast range scans

B. Internal nodes store full data records for quick access

C. B+ trees compress data to reduce disk space

D. B+ trees use hashing to find exact matches quickly

Solution

1. Step 1: Understand B+ tree leaf node linkage

   Leaf nodes in B+ trees are linked in a sorted order, enabling efficient sequential access for range queries.

2. Step 2: Evaluate options for range query optimization

   Leaf nodes are linked in a sorted sequence allowing fast range scans correctly identifies linked leaf nodes as the key feature for fast range scans. Other options describe unrelated features.

3. Final Answer:

   Leaf nodes are linked in a sorted sequence allowing fast range scans -> Option A

4. Quick Check:

   Linked leaf nodes = efficient range queries [OK]

Hint: Linked leaves enable fast sequential range scans [OK]

Common Mistakes:

• Confusing B+ tree with hash indexes
• Thinking internal nodes store full data
• Assuming compression is main feature