Clustered vs Non-Clustered Index - When to Use Which

▶

Steps

setup

Initialize B-tree representing clustered index

We start with a B-tree of order 3 representing a clustered index on keys [10, 20, 30, 40, 50]. The root node contains keys 20 and 40, with three children nodes.

💡 Setting up the initial B-tree structure is essential to visualize how clustered indexes organize data physically in sorted order.

Line:

b_tree = BTree(order=3)
b_tree.insert(10)
b_tree.insert(20)
b_tree.insert(30)
b_tree.insert(40)
b_tree.insert(50)

💡 The B-tree structure reflects the clustered index where data is stored sorted by key.

search

Search for key 30 in clustered index

We begin searching for key 30 starting at the root node. The root node keys are 20 and 40. Since 30 is greater than 20 but less than 40, we traverse to the middle child node.

💡 This step shows how B-tree traversal narrows down the search path based on key comparisons.

Line:

if key < node.keys[0]:
    child = node.children[0]
elif key < node.keys[1]:
    child = node.children[1]
else:
    child = node.children[2]

💡 B-tree traversal uses key comparisons to decide which child node to visit next.

search

Find key 30 in leaf node

At the middle child node, which is a leaf, we check keys and find 30 present. The search is successful.

💡 Finding the key in a leaf node confirms the search operation's end in a clustered index B-tree.

Line:

if key in node.keys:
    return True

💡 Leaf nodes contain actual data keys in clustered indexes, so search ends here.

setup

Initialize B-tree representing non-clustered index

We now set up a separate B-tree representing a non-clustered index on a different attribute. This B-tree stores keys [15, 25, 35, 45, 55] with pointers to data rows.

💡 Non-clustered indexes maintain a separate B-tree structure with keys and pointers, not affecting physical data order.

Line:

non_clustered_btree = BTree(order=3)
non_clustered_btree.insert(15)
non_clustered_btree.insert(25)
non_clustered_btree.insert(35)
non_clustered_btree.insert(45)
non_clustered_btree.insert(55)

💡 Non-clustered index B-tree stores keys separately with pointers, enabling fast lookups without data reordering.

search

Search for key 35 in non-clustered index

Starting at the root node with keys 25 and 45, we compare key 35. Since 35 is greater than 25 but less than 45, we traverse to the middle child node.

💡 Traversal logic is the same as clustered index, but keys point to data rows instead of storing data physically.

Line:

if key < node.keys[0]:
    child = node.children[0]
elif key < node.keys[1]:
    child = node.children[1]
else:
    child = node.children[2]

💡 Non-clustered index traversal uses key comparisons to find pointers to data rows.

search

Find key 35 in leaf node of non-clustered index

At the leaf node, we find key 35. This key points to the actual data row in the table, completing the search.

💡 Non-clustered index leaf nodes store keys and pointers, not the data itself.

Line:

if key in node.keys:
    return pointer_to_data

💡 Non-clustered index search returns a pointer to data, requiring an additional lookup to fetch data.

insert

Insert key 25 into clustered index

We attempt to insert key 25 into the clustered index B-tree. Starting at root, 25 is between 20 and 40, so we move to the middle child node.

💡 Insertion in clustered index requires maintaining sorted order of data keys physically.

Line:

if key < node.keys[0]:
    child = node.children[0]
elif key < node.keys[1]:
    child = node.children[1]
else:
    child = node.children[2]

💡 Insertion path is determined by key comparisons, same as search.

insert

Insert key 25 into leaf node

At the leaf node with key 30, we insert 25. The node now temporarily holds keys [25, 30]. Since the node is not full, no split is needed.

💡 Inserting into a leaf node updates keys while maintaining sorted order.

Line:

node.keys.append(key)
node.keys.sort()

💡 Insertion can be simple if node has space; otherwise, splitting is required.

insert

Insert key 60 into non-clustered index

We insert key 60 into the non-clustered index B-tree. Starting at root with keys 25 and 45, since 60 > 45, we traverse to the rightmost child node.

💡 Insertion path is determined by key comparisons, same as clustered index.

Line:

if key < node.keys[0]:
    child = node.children[0]
elif key < node.keys[1]:
    child = node.children[1]
else:
    child = node.children[2]

💡 Traversal logic is consistent across index types.

insert

Insert key 60 into leaf node causing split

At the leaf node with keys [55], we insert 60. The node now has keys [55, 60]. Since the node is full (order 3 allows max 2 keys), we split the node.

💡 Node splitting maintains B-tree balance and order constraints during insertions.

Line:

node.keys.append(key)
node.keys.sort()
if len(node.keys) == order:
    split_node(node)

💡 Splitting redistributes keys and promotes a key to the parent to maintain B-tree properties.

insert

Update root after split in non-clustered index

After splitting the leaf node, key 55 is promoted to the root node. The root now has keys [25, 45, 55] and four children nodes.

💡 Promoting keys during splits maintains B-tree height and balance.

Line:

parent.keys.insert(index, promoted_key)
parent.children.insert(index + 1, new_node)

💡 Root node keys increase and children pointers update to maintain B-tree structure.

traverse

Summary: When to use clustered index

Clustered indexes are best when queries retrieve ranges of data or when data is frequently accessed in sorted order, as data is stored physically sorted by key.

💡 Understanding clustered index benefits helps optimize query performance for range scans.

💡 Clustered indexes reduce I/O for range queries by storing data physically sorted.

traverse

Summary: When to use non-clustered index

Non-clustered indexes are useful when queries filter on columns not part of the clustered index or when multiple indexes are needed, as they store keys and pointers separately.

💡 Knowing non-clustered index use cases helps design flexible indexing strategies.

💡 Non-clustered indexes enable fast lookups on non-primary key columns without affecting data order.

traverse

Final state: clustered index B-tree with inserted key

The clustered index B-tree now contains keys [10], [25, 30], and [50] in leaf nodes, maintaining sorted order after insertion.

💡 Final structure shows how clustered index maintains physical order after insertions.

💡 Clustered index B-tree structure reflects physical data order and efficient range access.

traverse

Final state: non-clustered index B-tree after split

The non-clustered index B-tree root has keys [25, 45, 55] with four children leaf nodes containing keys [15], [35], [55], and [60].

💡 Final structure shows how non-clustered index handles insertions and splits separately from data storage.

💡 Non-clustered index B-tree structure supports efficient key lookups with pointers to data rows.

class BTreeNode:
    def __init__(self, order, is_leaf):
        self.order = order
        self.keys = []  # STEP 1: Initialize keys
        self.children = []  # STEP 1: Initialize children
        self.is_leaf = is_leaf
        self.parent = None

class BTree:
    def __init__(self, order):
        self.order = order
        self.root = BTreeNode(order, True)  # STEP 1: Create root node

    def search(self, key):
        node = self.root
        while True:
            i = 0
            while i < len(node.keys) and key > node.keys[i]:
                i += 1  # STEP 2: Find child index
            if i < len(node.keys) and key == node.keys[i]:
                return node, i  # STEP 3: Key found
            if node.is_leaf:
                return None  # STEP 3: Key not found
            node = node.children[i]  # STEP 2: Traverse child

    def insert(self, key):
        node = self.root
        if len(node.keys) == 2 * self.order - 1:
            new_root = BTreeNode(self.order, False)
            new_root.children.append(node)
            node.parent = new_root
            self.root = new_root
            self.split_child(new_root, 0)  # STEP 10: Split root
            self.insert_non_full(new_root, key)
        else:
            self.insert_non_full(node, key)  # STEP 7: Insert key

    def insert_non_full(self, node, key):
        i = len(node.keys) - 1
        if node.is_leaf:
            node.keys.append(None)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1  # STEP 8: Shift keys
            node.keys[i + 1] = key  # STEP 8: Insert key
        else:
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            if len(node.children[i].keys) == 2 * self.order - 1:
                self.split_child(node, i)  # STEP 10: Split child
                if key > node.keys[i]:
                    i += 1
            self.insert_non_full(node.children[i], key)  # STEP 7: Recursive insert

    def split_child(self, parent, index):
        order = self.order
        node = parent.children[index]
        new_node = BTreeNode(order, node.is_leaf)
        new_node.parent = parent
        parent.keys.insert(index, node.keys[order - 1])  # STEP 10: Promote key
        parent.children.insert(index + 1, new_node)  # STEP 11: Insert new child
        new_node.keys = node.keys[order:]  # STEP 10: Split keys
        node.keys = node.keys[:order - 1]
        if not node.is_leaf:
            new_node.children = node.children[order:]
            node.children = node.children[:order]

# Usage example with step comments matching visualization
btree = BTree(order=3)  # STEP 1
for key in [10, 20, 30, 40, 50]:
    btree.insert(key)  # STEP 7-11
node, idx = btree.search(30)  # STEP 2-3

📊

Clustered vs Non-Clustered Index - When to Use Which - Watch the Algorithm Execute, Step by Step

Watching the step-by-step traversal and modification of the B-tree helps understand the fundamental differences between clustered and non-clustered indexes and their impact on query performance.

setup

2040

10

leaf

30

leaf

50

leaf

Initial B-tree setup representing clustered index

searchKey: 30

2040

10

leaf

30

leaf

50

leaf

At root, key 30 is between 20 and 40, traverse middle child

searchKey: 30

2040

10

leaf

30

leaf

50

leaf

Key 30 found in leaf node of clustered index

setup

2545

15

leaf

35

leaf

55

leaf

Initial B-tree setup representing non-clustered index

searchKey: 35

2545

15

leaf

35

leaf

55

leaf

At root, key 35 is between 25 and 45, traverse middle child

searchKey: 35

2545

15

leaf

35

leaf

55

leaf

Key 35 found in leaf node of non-clustered index

insertKey: 25

2040

10

leaf

30

leaf

50

leaf

At root, key 25 is between 20 and 40, traverse middle child for insertion

insertKey: 25

2040

10

leaf

2530

leaf

50

leaf

Inserted key 25 into leaf node without splitting

insertKey: 60

2545

15

leaf

35

leaf

55

leaf

At root, key 60 > 45, traverse right child for insertion

splitKey: 60↑ promoted: 55

254555

15

leaf

35

leaf

55

leaf

60

leaf

Leaf node split after inserting key 60, key 55 promoted to root

insertKey: 55↑ promoted: 55

254555

15

leaf

35

leaf

55

leaf

60

leaf

Root updated with promoted key 55 after leaf split

traverse

Clustered index stores data physically sorted, ideal for range queries

traverse

Non-clustered index stores keys separately, useful for multiple indexing needs

traverse

2040

10

leaf

2530

leaf

50

leaf

Final clustered index B-tree after insertion

traverse

254555

15

leaf

35

leaf

55

leaf

60

leaf

Final non-clustered index B-tree after insertion and split

Key Takeaways

✓ Clustered indexes store data physically sorted by key, optimizing range queries.

This insight is hard to see from code alone because physical data ordering is a conceptual property, not just a data structure detail.

✓ Non-clustered indexes maintain separate B-tree structures with keys and pointers, enabling flexible lookups without affecting data order.

Visualizing separate B-trees clarifies how non-clustered indexes differ structurally and operationally from clustered indexes.

✓ B-tree node splitting and key promotion maintain balance and order, critical for efficient insertions in both index types.

Watching splits and promotions step-by-step reveals the dynamic balancing process that is abstracted away in code.

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. Which of the following is a common misconception about optimistic concurrency control in high-contention environments?

medium

A. Optimistic concurrency control always improves throughput by avoiding locks

B. It can lead to increased transaction aborts and retries under contention

C. It assumes conflicts are rare and validates data before commit

D. It reduces blocking but may increase latency due to retries

Solution

1. Step 1: Understand optimistic concurrency assumptions

   Optimistic control assumes conflicts are rare and avoids locking during transaction execution.

2. Step 2: Analyze behavior under high contention

   When conflicts are frequent, many transactions abort and retry, reducing throughput.

3. Step 3: Evaluate misconception

   Believing optimistic control always improves throughput ignores the cost of retries and aborts in high-contention scenarios.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Optimistic concurrency is beneficial mainly when conflicts are infrequent.

Hint: Optimistic concurrency shines only when conflicts are rare, not always.

Common Mistakes:

• Assuming no locks means always better performance
• Ignoring the cost of transaction retries
• Confusing optimistic validation with locking

3. Which of the following statements about cardinality in ER diagrams is INCORRECT?

medium

A. In a 1:1 relationship, both entities must have the same number of instances.

B. A 1:N relationship means one entity instance on the 'one' side can relate to many instances on the 'many' side.

C. An N:M relationship requires an associative entity to be properly implemented in a relational schema.

D. Cardinality constraints define the minimum and maximum number of entity instances involved in a relationship.

Solution

1. Step 1: Analyze statement A

   Incorrect: 1:1 relationship restricts each instance to relate to at most one on the other side, but does not require equal number of instances in both entities.

2. Step 2: Analyze statement B

   Correct: 1:N means one instance relates to many on the other side.

3. Step 3: Analyze statement C

   Correct: N:M relationships require associative entities for relational implementation.

4. Step 4: Analyze statement D

   Correct: Cardinality defines numeric constraints (min and max) on relationships.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   1:1 cardinality restricts relationships, not entity counts.

Hint: Cardinality limits relationships per instance, not total entity counts.

Common Mistakes:

• Assuming 1:1 means equal number of entities on both sides
• Confusing cardinality with entity population size

4. Which of the following statements about deadlocks in Two-Phase Locking (2PL) is INCORRECT?

medium

A. Strict 2PL completely prevents deadlocks by ordering lock acquisition

B. Deadlock detection algorithms can resolve deadlocks by aborting one of the transactions

C. Deadlocks occur when two or more transactions wait indefinitely for locks held by each other

D. Deadlocks can arise even if transactions follow the 2PL protocol

Solution

1. Step 1: Understand deadlock conditions

   Deadlocks happen when transactions cyclically wait for locks held by each other, which can occur under 2PL.

2. Step 2: Analyze deadlock prevention

   Strict 2PL does not guarantee deadlock prevention; it only ensures serializability.

3. Step 3: Evaluate options

   A, B, and D are correct statements. C is incorrect because strict 2PL does not prevent deadlocks by ordering lock acquisition.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Deadlocks require detection and resolution even under strict 2PL.

Hint: Strict 2PL ensures serializability but not deadlock prevention [OK]

Common Mistakes:

• Assuming strict 2PL prevents deadlocks
• Confusing deadlock detection with prevention
• Believing 2PL eliminates all concurrency issues

5. Consider a relation R(A,B,C,D) with functional dependencies F = {A -> B, B -> C, C -> D}. You decompose R into R1(A,B), R2(B,C), and R3(C,D). Which of the following statements about this decomposition is TRUE regarding lossless join and dependency preservation?

hard

A. The decomposition is neither lossless nor dependency preserving because the chain of dependencies is broken across relations.

B. The decomposition is lossless and dependency preserving because each FD is represented in one of the decomposed relations.

C. The decomposition is dependency preserving but not lossless because the common attributes do not form keys in the decomposed relations.

D. The decomposition is lossless but not dependency preserving because enforcing A -> B requires joining R1 and R2.

Solution

1. Step 1: Check lossless join condition

   Each pair of relations shares a key attribute: R1 and R2 share B (key in R2), R2 and R3 share C (key in R3), so lossless join holds.

2. Step 2: Check dependency preservation

   All FDs appear in one of the relations: A -> B in R1, B -> C in R2, C -> D in R3.

3. Step 3: Confirm no FD requires join enforcement

   Each FD is enforceable in its own relation, so dependency preservation holds.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Options A, B, and C incorrectly claim loss or preservation failures.

Hint: If each FD is in one relation and common attributes are keys, decomposition is lossless and dependency preserving.

Common Mistakes:

• Assuming chain dependencies require joins to enforce
• Believing lossless join requires all keys in all relations
• Confusing dependency preservation with global key presence