B-Tree vs B+ Tree - Structure & Why DBMS Prefers B+

▶

Steps

setup

Initialize B-Tree Structure

We start by initializing an empty B-Tree of order 3 (max 2 keys per node). The root node is empty and is a leaf.

💡 Initialization sets the foundation for understanding how keys and children will be organized in the B-Tree.

Line:

class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []

💡 The root node starts empty and is a leaf, meaning it has no children yet.

setup

Initialize B+ Tree Structure

We initialize an empty B+ Tree of order 3. The root is also a leaf node but will store only keys and data pointers; internal nodes will store keys only as guides.

💡 This setup highlights the key difference that B+ Tree leaves hold actual data keys, while internal nodes guide searches.

Line:

class BPlusTreeNode:
    def __init__(self, leaf=True):
        self.keys = []
        self.children = []

💡 The root node is a leaf and will hold all keys initially, unlike B-Tree where keys can be in internal nodes.

insert

Insert keys into B-Tree root

Insert keys 10 and 20 into the B-Tree root node. Since the root is a leaf and has space, keys are simply added in sorted order.

💡 This step shows how keys are stored in all nodes in B-Tree, including the root and leaves.

Line:

root.keys.append(10)
root.keys.append(20)
root.keys.sort()

💡 Keys are stored directly in the root node, demonstrating B-Tree's property of keys in all nodes.

insert

Insert keys into B+ Tree leaf

Insert keys 10 and 20 into the B+ Tree leaf node. Keys are stored only in leaves, so the root leaf now holds these keys.

💡 This step highlights that B+ Tree stores all data keys in leaves, unlike B-Tree which stores keys in all nodes.

Line:

leaf.keys.append(10)
leaf.keys.append(20)
leaf.keys.sort()

💡 Data keys reside only in leaf nodes in B+ Tree, internal nodes will later hold guide keys.

insert

Insert key 30 causing B-Tree root split

Insert key 30 into B-Tree root node which is full (max 2 keys). This triggers a split: the middle key 20 is promoted, root splits into two children.

💡 Splitting nodes maintains B-Tree balance and order constraints, ensuring efficient search.

Line:

root.keys.append(30)
root.keys.sort()
if len(root.keys) == order:
    split_root()

💡 Splitting promotes a middle key to parent, creating new child nodes and increasing tree height.

insert

Insert key 30 causing B+ Tree leaf split

Insert key 30 into B+ Tree leaf node which is full. Leaf splits into two leaves; middle key 20 is promoted to new root internal node.

💡 B+ Tree splits differ: only leaves split and promote keys to internal nodes which guide searches.

Line:

leaf.keys.append(30)
leaf.keys.sort()
if len(leaf.keys) == order:
    split_leaf()

💡 B+ Tree internal nodes store only guide keys, leaves hold all data keys linked sequentially.

search

Traverse B-Tree to search key 30

Start at root node with key 20. Since 30 > 20, traverse to right child node containing key 30.

💡 Traversal decisions depend on key comparisons at internal nodes to find correct child.

Line:

if key > node.keys[0]:
    node = node.children[1]

💡 B-Tree search uses keys in internal nodes to decide traversal path.

search

Traverse B+ Tree to search key 30

Start at root internal node with key 20. Since 30 > 20, traverse to right leaf node containing key 30.

💡 B+ Tree internal nodes guide search but data keys are only in leaves.

Line:

if key > node.keys[0]:
    node = node.children[1]

💡 B+ Tree search always ends at leaf nodes where data keys reside.

traverse

Range query efficiency in B-Tree

To perform a range query, B-Tree requires traversing multiple leaf nodes which are not linked, causing multiple tree traversals.

💡 B-Tree leaves are not linked, so range queries are less efficient.

Line:

# No direct code, conceptual step

💡 Range queries in B-Tree require repeated traversal from root to leaves.

traverse

Range query efficiency in B+ Tree

B+ Tree leaf nodes are linked sequentially, allowing efficient range queries by scanning leaf nodes directly without repeated root traversals.

💡 Linked leaves in B+ Tree enable fast sequential access, a key advantage for DBMS.

Line:

# Conceptual step showing leaf linkage

💡 B+ Tree supports efficient range queries via linked leaf nodes.

reconstruct

Summary: B-Tree vs B+ Tree structure

Summarize the structural differences: B-Tree stores keys in all nodes; B+ Tree stores keys only in leaves with internal nodes as guides. B+ Tree leaves are linked for efficient range queries.

💡 This step consolidates the key structural insights from the previous steps.

Line:

# No code, conceptual summary

💡 Understanding these differences explains why B+ Trees are preferred in DBMS indexing.

reconstruct

Final state: Key insights from B+ Tree preference

The final state highlights that B+ Tree's leaf-only data storage and linked leaves enable efficient range queries and sequential access, making it ideal for DBMS indexing.

💡 This final step reinforces the practical advantages of B+ Trees over B-Trees.

Line:

# Conceptual final step

💡 DBMS prefer B+ Trees because they optimize both point and range queries with minimal tree traversal.

class BTreeNode:
    def __init__(self, leaf=True):  # STEP 1
        self.keys = []
        self.children = []
        self.leaf = leaf

class BPlusTreeNode:
    def __init__(self, leaf=True):  # STEP 2
        self.keys = []
        self.children = []
        self.leaf = leaf

# STEP 3: Insert keys into B-Tree root
root = BTreeNode(leaf=True)
root.keys.append(10)
root.keys.append(20)
root.keys.sort()

# STEP 4: Insert keys into B+ Tree leaf
leaf = BPlusTreeNode(leaf=True)
leaf.keys.append(10)
leaf.keys.append(20)
leaf.keys.sort()

# STEP 5: Insert key 30 causing B-Tree root split
root.keys.append(30)
root.keys.sort()
if len(root.keys) == 3:  # order 3
    # split root
    mid = root.keys[1]
    left = BTreeNode(leaf=True)
    right = BTreeNode(leaf=True)
    left.keys = [root.keys[0]]
    right.keys = [root.keys[2]]
    new_root = BTreeNode(leaf=False)
    new_root.keys = [mid]
    new_root.children = [left, right]
    root = new_root

# STEP 6: Insert key 30 causing B+ Tree leaf split
leaf.keys.append(30)
leaf.keys.sort()
if len(leaf.keys) == 3:
    mid = leaf.keys[1]
    left_leaf = BPlusTreeNode(leaf=True)
    right_leaf = BPlusTreeNode(leaf=True)
    left_leaf.keys = [leaf.keys[0]]
    right_leaf.keys = [leaf.keys[2]]
    root_bplus = BPlusTreeNode(leaf=False)
    root_bplus.keys = [mid]
    root_bplus.children = [left_leaf, right_leaf]
    leaf = root_bplus

# STEP 7: Traverse B-Tree to search key 30
node = root
key = 30
if key > node.keys[0]:
    node = node.children[1]
# node.keys == [30]

# STEP 8: Traverse B+ Tree to search key 30
node = leaf
if key > node.keys[0]:
    node = node.children[1]
# node.keys == [30]

# STEP 9 & 10: Conceptual range query steps
# B-Tree: multiple traversals
# B+ Tree: linked leaves

# STEP 11 & 12: Summary and final insights

📊

B-Tree vs B+ Tree - Structure & Why DBMS Prefers B+ - Watch the Algorithm Execute, Step by Step

Watching the step-by-step construction and traversal of both trees reveals why B+ Trees are preferred in DBMS for indexing large datasets, especially for range queries and sequential access.

setup

leaf

Initialized empty B-Tree root node as leaf.

setup

leaf

Initialized empty B+ Tree root node as leaf.

insertKey: 20

1020

leaf

Inserted keys 10 and 20 into B-Tree root node.

insertKey: 20

1020

leaf

Inserted keys 10 and 20 into B+ Tree leaf node.

splitKey: 30↑ promoted: 20

20

10

leaf

30

leaf

Root node split; key 20 promoted; tree height increased.

splitKey: 30↑ promoted: 20

20

10

leaf

30

leaf

Leaf node split; key 20 promoted to root internal node.

searchKey: 30

20

30

leaf

Traversed right child of root to find key 30.

searchKey: 30

20

30

leaf

Traversed right leaf node to find key 30.

traverse

20

10

leaf

30

leaf

Range queries require multiple traversals to leaves in B-Tree.

traverse

20

10

leaf

30

leaf

Leaf nodes linked for efficient range queries in B+ Tree.

reconstruct

20

10

leaf

30

leaf

20

10

leaf

30

leaf

Summary of B-Tree and B+ Tree structural differences.

reconstruct

20

10

leaf

30

leaf

Final state showing B+ Tree advantages for DBMS indexing.

Key Takeaways

✓ B+ Trees store all data keys in leaf nodes only, while B-Trees store keys in all nodes.

This difference is hard to grasp from code alone but is visually clear when seeing node contents step-by-step.

✓ B+ Tree leaf nodes are linked sequentially, enabling efficient range queries and sequential scans.

The linked leaf structure is a key advantage for DBMS, which is difficult to visualize without explicit leaf linkage.

✓ Splitting in B+ Trees promotes keys to internal nodes as guides, separating data storage from search keys.

Understanding the split and promotion mechanism clarifies why B+ Trees maintain balance and efficient search.

Practice

1. In which scenario is the Isolation property of ACID most critical to ensure correct database behavior?

easy

A. When a transaction must be completed entirely or not at all to avoid partial updates

B. When multiple transactions run concurrently and must not see each other's intermediate states

C. When the database must maintain integrity constraints after each transaction

D. When committed transactions must survive system crashes and power failures

Solution

1. Step 1: Understand Isolation's role

   Isolation ensures that concurrent transactions do not interfere by hiding intermediate states from each other.

2. Step 2: Analyze each option

   A describes Atomicity, C describes Consistency, D describes Durability.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Isolation is about concurrency control, so B is correct.

Hint: Isolation = hiding intermediate states during concurrency

Common Mistakes:

• Confusing Isolation with Atomicity
• Mixing Consistency with Durability

2. Consider the following Python code simulating SQL query execution order using linked nodes. What is the exact output when executing the query plan starting from the FROM clause node?

class QueryPlanNode:
    def __init__(self, name):
        self.name = name
        self.next = None
    def set_next(self, node):
        self.next = node
    def execute(self):
        print(f"Executing {self.name} clause")
        if self.next:
            self.next.execute()

from_clause = QueryPlanNode('FROM')
where_clause = QueryPlanNode('WHERE')
group_by_clause = QueryPlanNode('GROUP BY')
having_clause = QueryPlanNode('HAVING')
select_clause = QueryPlanNode('SELECT')
order_by_clause = QueryPlanNode('ORDER BY')
limit_clause = QueryPlanNode('LIMIT')

from_clause.set_next(where_clause)
where_clause.set_next(group_by_clause)
group_by_clause.set_next(having_clause)
having_clause.set_next(select_clause)
select_clause.set_next(order_by_clause)
order_by_clause.set_next(limit_clause)

from_clause.execute()

easy

A. Executing FROM clause
Executing WHERE clause
Executing GROUP BY clause
Executing HAVING clause
Executing SELECT clause
Executing ORDER BY clause
Executing LIMIT clause

B. Executing SELECT clause
Executing FROM clause
Executing WHERE clause
Executing GROUP BY clause
Executing HAVING clause
Executing ORDER BY clause
Executing LIMIT clause

C. Executing FROM clause
Executing SELECT clause
Executing WHERE clause
Executing GROUP BY clause
Executing HAVING clause
Executing ORDER BY clause
Executing LIMIT clause

D. Executing FROM clause
Executing WHERE clause
Executing HAVING clause
Executing GROUP BY clause
Executing SELECT clause
Executing ORDER BY clause
Executing LIMIT clause

Solution

1. Step 1: Trace execution starting from FROM node

   The execute() method prints the current node's clause name, then recursively calls execute() on the next node if it exists. The chain is FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY -> LIMIT.

2. Step 2: Confirm output order matches linked nodes

   Each clause prints in the linked order, so output lines are exactly the clauses in the chain order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Output matches linked list traversal order [OK]

Hint: Linked nodes print clauses in linked order [OK]

Common Mistakes:

• Confusing printed order with written SQL order

3. In which scenario is the Two-Phase Locking (2PL) protocol most appropriate to ensure serializability in a database system?

easy

A. When transactions require only read operations and no writes

B. When transactions involve both reads and writes and strict serializability is required

C. When transactions are short-lived and deadlocks are impossible

D. When optimistic concurrency control is preferred over locking

Solution

1. Step 1: Understand 2PL's purpose

   2PL ensures serializability by acquiring locks in a growing phase and releasing them in a shrinking phase, which is essential when transactions perform both reads and writes.

2. Step 2: Analyze each option

   A is incorrect because 2PL is not necessary if only reads occur; shared locks suffice without strict 2PL. B is unrelated as optimistic concurrency control avoids locking. C is wrong since deadlocks can occur regardless of transaction length. D correctly identifies the scenario where 2PL is most appropriate.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   2PL is designed for mixed read-write transactions requiring strict serializability.

Hint: 2PL is for mixed read-write transactions needing serializability [OK]

Common Mistakes:

• Assuming 2PL is needed for read-only transactions
• Believing short transactions cannot deadlock
• Confusing locking with optimistic concurrency

4. Suppose the Employee table can have NULL salaries and you want to find the second highest salary excluding NULLs. Which modification to the optimal DISTINCT + ORDER BY + LIMIT OFFSET query correctly handles this scenario?

hard

A. Use ROW_NUMBER() without filtering NULLs, as it automatically ignores NULLs.

B. Remove DISTINCT and rely on ORDER BY and LIMIT OFFSET to handle NULLs.

C. Add WHERE Salary IS NOT NULL inside the subquery selecting DISTINCT salaries.

D. Use MAX(Salary) twice without any NULL filtering.

Solution

1. Step 1: Identify the issue with NULL salaries

   NULL salaries can appear in the result set and affect ordering and offsets.

2. Step 2: Modify query to exclude NULLs

   Adding WHERE Salary IS NOT NULL inside the subquery ensures only valid salaries are considered for DISTINCT and ordering.

3. Step 3: Verify other options

   Removing DISTINCT or relying on ROW_NUMBER() without filtering NULLs can return NULL or incorrect results; MAX() twice without filtering also fails.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Filtering NULLs before ordering ensures correct second highest salary [OK]

Hint: Filter NULL salaries before ordering to avoid incorrect results [OK]

Common Mistakes:

• Not filtering NULLs causes NULL to appear as second highest
• Assuming ROW_NUMBER() ignores NULLs automatically

5. Suppose you want to find all pairs of employees and projects they can work on, regardless of any matching keys, but your current INNER JOIN query returns no rows. Which join type should you use to get all combinations, and what is a potential downside?

hard

A. Use CROSS JOIN to get Cartesian product; downside is potentially huge result size

B. Use LEFT JOIN to include all employees and matching projects; downside is missing unmatched projects

C. Use FULL OUTER JOIN to include all employees and projects; downside is NULLs in unmatched columns

D. Use SELF JOIN on employees to pair them with projects; downside is ambiguous columns

Solution

1. Step 1: Identify join type for all combinations

   CROSS JOIN returns the Cartesian product of two tables, producing all possible pairs regardless of matching keys.

2. Step 2: Consider downside

   The Cartesian product can be very large, leading to performance issues and large result sets.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   CROSS JOIN produces all pairs but can explode result size [OK]

Hint: CROSS JOIN yields all combinations, beware size explosion [OK]

Common Mistakes:

• Using INNER JOIN expecting all pairs
• Confusing FULL OUTER JOIN with Cartesian product