Hash Index vs B+ Tree Index - Range Queries & Equality Lookups

▶

Steps

setup

Initialize B+ Tree Structure

The B+ Tree is initialized with order 3 and keys inserted: 10, 20, 30, 40, 50, 60, 70. The tree structure is balanced with internal and leaf nodes.

💡 Setting up the tree structure is essential to visualize how keys are organized and how the tree guides searches.

Line:

bptree = BPlusTree(order=3)
bptree.insert(10)
bptree.insert(20)
...

💡 The tree is balanced with internal nodes directing searches and leaf nodes containing keys in sorted order.

search

Start Range Query: Search for Start Key 25

Begin searching from the root node to find the leaf node that may contain key 25, the start of the range query.

💡 Finding the start key's leaf node is the first step in a range query to know where to begin scanning.

Line:

node = root
while not node.is_leaf:
  node = node.child_for_key(25)

💡 Internal nodes guide the search by comparing keys to decide which child to follow.

search

Descend to Leaf Node for Key 25

At internal node 1, key 25 is less than 30, so descend to child node 2, which is a leaf node containing keys 10 and 20.

💡 Leaf nodes contain actual data keys; finding the correct leaf is crucial for efficient lookup.

Line:

node = node.children[0]  # child 2

💡 Leaf nodes hold keys in sorted order, enabling efficient range scans.

search

Locate Start Position in Leaf Node

Within leaf node 2, compare keys 10 and 20 to find the position where key 25 would be inserted or found.

💡 This step identifies the exact starting point for the range scan.

Line:

pos = find_position(node.keys, 25)

💡 Even if the key is not present, the position guides where to start scanning next keys.

traverse

Begin Range Scan at Leaf Node 3

Since key 25 is greater than keys in leaf 2, move to the next leaf node 3 to start scanning keys within the range.

💡 B+ Trees link leaf nodes for efficient sequential access during range queries.

Line:

node = next_leaf(node)  # move to node 3

💡 Leaf nodes are linked, enabling efficient range scans without returning to the root.

traverse

Scan Keys in Leaf Node 3

Scan keys 30 and 40 in leaf node 3, both within the range 25 to 65, so they are included in the result.

💡 Scanning leaf nodes sequentially collects all keys in the query range efficiently.

Line:

for key in node.keys:
  if key >= 25 and key <= 65:
    result.append(key)

💡 Leaf nodes store keys in sorted order, so scanning is straightforward and efficient.

traverse

Move to Next Leaf Node 4 for Range Scan

After finishing leaf node 3, move to leaf node 4 to continue scanning keys in the range 25 to 65.

💡 Sequential leaf node traversal allows scanning large ranges efficiently without repeated tree traversals.

Line:

node = next_leaf(node)  # move to node 4

💡 Leaf nodes are linked in order, enabling efficient range scans.

traverse

Scan Keys in Leaf Node 4

Scan keys 50, 60, and 70 in leaf node 4. Keys 50 and 60 are within the range and included; key 70 is outside the range and excluded.

💡 Range scans stop when keys exceed the upper bound, avoiding unnecessary reads.

Line:

for key in node.keys:
  if key > 65:
    break
  result.append(key)

💡 Sorted keys allow early termination of range scans.

traverse

Complete Range Scan and Return Results

Range scan completes after key 70 is found outside the range. The collected keys 30, 40, 50, and 60 are returned as the query result.

💡 The B+ Tree efficiently supports range queries by combining search and sequential leaf scans.

Line:

return result  # keys: 30, 40, 50, 60

💡 B+ Tree leaf node linkage enables efficient retrieval of all keys in the range without repeated tree traversals.

traverse

Final State: Range Query Result

The final state shows the B+ Tree unchanged and the answer containing all keys found in the range query.

💡 The final step confirms the correctness of the range query and the stable tree structure.

Line:

answer = [30, 40, 50, 60]

💡 The B+ Tree efficiently supports both equality and range queries with minimal node visits.

class BPlusTreeNode:
    def __init__(self, keys=None, children=None, is_leaf=False, parent=None):
        self.keys = keys or []
        self.children = children or []
        self.is_leaf = is_leaf
        self.parent = parent

class BPlusTree:
    def __init__(self, order=3):
        self.order = order
        self.root = BPlusTreeNode(is_leaf=True)

    def insert(self, key):
        # Insert keys to build tree (not shown fully here)
        pass

    def search_leaf(self, key):
        # STEP 2: Start at root
        node = self.root  # STEP 2
        while not node.is_leaf:  # STEP 2
            # STEP 2: Decide child to descend
            i = 0
            while i < len(node.keys) and key >= node.keys[i]:
                i += 1
            node = node.children[i]  # STEP 3
        return node  # STEP 3

    def range_query(self, start_key, end_key):
        result = []
        # STEP 2-4: Find leaf node for start_key
        node = self.search_leaf(start_key)  # STEP 2-4
        i = 0
        while i < len(node.keys) and node.keys[i] < start_key:
            i += 1  # STEP 4
        # STEP 5-9: Scan leaf nodes
        while node:
            while i < len(node.keys) and node.keys[i] <= end_key:
                result.append(node.keys[i])  # STEP 6-8
                i += 1
            if i < len(node.keys):
                break  # STEP 8
            node = self.next_leaf(node)  # STEP 5,7
            i = 0
        return result  # STEP 9

    def next_leaf(self, node):
        # Return next leaf node (linked list)
        # For simplicity, assume parent and siblings known
        # STEP 5,7
        return None  # placeholder

# Usage example:
# bptree = BPlusTree(order=3)
# for key in [10,20,30,40,50,60,70]:
#     bptree.insert(key)  # STEP 1
# result = bptree.range_query(25, 65)  # STEP 2-9

📊

Hash Index vs B+ Tree Index - Range Queries & Equality Lookups - Watch the Algorithm Execute, Step by Step

Watching this visualization helps you understand the structural advantages of B+ Trees for range queries compared to hash indexes, by seeing exactly how keys are located and how leaf nodes are scanned sequentially.

search

3050

1020

leaf

3040

leaf

506070

leaf

Initial B+ Tree constructed with keys 10,20,30,40,50,60,70

searchKey: 25

3050

1020

leaf

3040

leaf

506070

leaf

At root, key 25 < 30, so descend to child node 2

searchKey: 25

3050

1020

leaf

3040

leaf

506070

leaf

Descended to leaf node 2 to locate key 25

searchKey: 25

3050

1020

leaf

3040

leaf

506070

leaf

Key 25 not found in leaf 2; start scanning after key 20

traverseKey: 25

3050

1020

leaf

3040

leaf

506070

leaf

Moved to leaf node 3 to start scanning keys >= 25

traverseKey: 30

3050

1020

leaf

3040

leaf

506070

leaf

Scanned keys 30 and 40 in leaf node 3, both within range

traverseKey: 40

3050

1020

leaf

3040

leaf

506070

leaf

Moved to leaf node 4 to continue scanning keys in range

traverseKey: 50

3050

1020

leaf

3040

leaf

506070

leaf

Scanned keys 50 and 60 in leaf node 4; stopped at key 70 outside range

traverse

3050

1020

leaf

3040

leaf

506070

leaf

Range scan complete; keys 30, 40, 50, 60 returned

Key Takeaways

✓ B+ Trees efficiently support range queries by linking leaf nodes for sequential scans.

This is hard to see from code alone because the linkage and sequential scanning are structural properties best understood visually.

✓ Internal nodes guide searches by directing to the correct child based on key comparisons.

Visualizing the active path clarifies how the tree narrows down the search space step-by-step.

✓ Range scans stop early when keys exceed the upper bound, avoiding unnecessary reads.

Seeing the scan stop at the right key helps understand the efficiency of B+ Tree range queries.

Practice

1. You have a SQL query with multiple clauses: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY, and LIMIT. To correctly process the query and produce the expected result, which approach best models the order in which these clauses are logically executed by the database engine?

easy

A. Execute clauses in the written order from top to bottom as they appear in the query.

B. Execute clauses in the logical order: FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY -> LIMIT.

C. Execute all filtering clauses first (WHERE and HAVING), then grouping, then selection, ignoring FROM order.

D. Execute SELECT first to identify columns, then FROM to get tables, then apply filters and limits.

Solution

1. Step 1: Understand SQL logical execution order

   SQL does not execute clauses in the written order. Instead, it first identifies data sources (FROM), then filters rows (WHERE), groups rows (GROUP BY), filters groups (HAVING), selects columns (SELECT), orders results (ORDER BY), and finally limits output rows (LIMIT).

2. Step 2: Match problem description to logical execution order

   The logical order ensures correct filtering and grouping before selection and ordering, which matches Execute clauses in the logical order: FROM -> WHERE -> GROUP BY -> HAVING -> SELECT -> ORDER BY -> LIMIT exactly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Logical execution order matches database engine processing [OK]

Hint: SQL executes clauses logically, not in written order [OK]

Common Mistakes:

• Assuming SQL executes clauses top-to-bottom as written

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. Which of the following statements about the Atomicity property of ACID is INCORRECT?

medium

A. Atomicity guarantees that either all operations of a transaction are applied or none are.

B. Atomicity ensures that once a transaction starts, it cannot be interrupted by other transactions.

C. Atomicity helps prevent partial updates that could leave the database in an inconsistent state.

D. Atomicity is typically implemented using mechanisms like write-ahead logging and rollback.

Solution

1. Step 1: Recall Atomicity meaning

   Atomicity means all-or-nothing execution of a transaction.

2. Step 2: Analyze each option

   A is correct; C is correct as partial updates violate atomicity; D is correct as logging and rollback implement atomicity.
3. B is incorrect because Atomicity does not prevent interruption by other transactions; that is Isolation's role.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Atomicity is about completeness, not concurrency control.

Hint: Atomicity = all-or-nothing, not about concurrency

Common Mistakes:

• Confusing Atomicity with Isolation
• Assuming Atomicity controls transaction scheduling

4. Which of the following statements about cost estimation in query optimization is TRUE regarding its limitations?

medium

A. Cost estimation always accurately predicts query execution time because it uses precise statistics

B. Cost estimation is unnecessary if the query uses indexes

C. Cost estimation ignores CPU costs and focuses only on I/O costs

D. Cost estimation can be inaccurate due to outdated statistics or assumptions about data distribution

Solution

1. Step 1: Understand cost estimation limitations

   Cost estimation relies on statistics that may be stale or incomplete, leading to inaccuracies.

2. Step 2: Analyze each option

   Cost estimation always accurately predicts query execution time because it uses precise statistics: Cost estimation is heuristic, not always precise.
   Cost estimation can be inaccurate due to outdated statistics or assumptions about data distribution: Correct--statistics can be outdated or assumptions invalid.
   Cost estimation ignores CPU costs and focuses only on I/O costs: Cost models consider CPU, I/O, and sometimes network.
   Cost estimation is unnecessary if the query uses indexes: Index usage reduces cost but estimation is still needed.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cost estimation is an approximation influenced by statistics quality.

Hint: Cost estimation is only as good as the statistics and assumptions it uses.

Common Mistakes:

• Believing cost estimation is perfectly accurate
• Thinking cost models ignore CPU costs
• Assuming indexes remove the need for cost estimation

5. Identify the bug in the following Python code that attempts to find customers with orders using a JOIN simulation:

medium

A. Line 3: The return statement should remove duplicates explicitly with DISTINCT.

B. Line 2: The list comprehension incorrectly filters customers by order IDs instead of customer IDs.

C. Line 1: Using a list instead of a set for order_customer_ids causes duplicates and slower lookups.

D. Line 1: The variable name order_customer_ids is misleading and should be order_ids.

Solution

1. Step 1: Analyze data structure used for order_customer_ids

   Using a list causes O(m) lookup per customer, leading to O(n*m) time and duplicates.

2. Step 2: Identify impact on performance and correctness

   Using a set enables O(1) lookups and avoids duplicates, improving performance and correctness.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing list with set fixes performance and duplicate issues [OK]

Hint: Sets provide O(1) membership checks, lists do not [OK]

Common Mistakes:

• Using list instead of set for membership
• Confusing customer_id with order_id
• Assuming duplicates are handled automatically