B-tree index structure in DBMS Theory - Mini Project: Build & Apply

Build a Simple B-tree Index Structure

📖 Scenario: You are working on a small database system that needs to quickly find records by their keys. To do this, you will build a simple B-tree index structure step-by-step.

🎯 Goal: Build a basic B-tree index structure with nodes and keys, add a configuration for the maximum number of keys per node, insert keys into the tree, and complete the tree structure.

📋 What You'll Learn

Create a B-tree node data structure with keys and children

Add a configuration variable for maximum keys per node

Implement insertion of keys into the B-tree node

Complete the B-tree structure by linking nodes properly

💡 Why This Matters

🌍 Real World

B-trees are used in databases and file systems to quickly find and store data by keys.

💼 Career

Understanding B-tree structures helps in database design, optimization, and working with indexing systems.

1

Create the B-tree node data structure

Create a class called BTreeNode with two attributes: keys as an empty list and children as an empty list.

DBMS Theory

# Create the BTreeNode class with keys and children attributes
# Your code here

Hint

Think of a B-tree node as a box that holds keys and pointers to child nodes.

2

Add maximum keys per node configuration

Create a variable called max_keys and set it to 3 to limit the number of keys each B-tree node can hold.

DBMS Theory

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

# Set the maximum number of keys per node
# Your code here

Hint

This variable controls how many keys a node can hold before splitting.

3

Implement key insertion into B-tree node

Add a method called insert_key to the BTreeNode class that takes a parameter key and inserts it into the keys list in sorted order.

DBMS Theory

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

    # Insert a key into the keys list in sorted order
    # Your code here

max_keys = 3

Hint

Insert the key and then sort the list to keep keys ordered.

4

Complete the B-tree structure by linking nodes

Create a root node called root as an instance of BTreeNode. Insert the keys 10, 20, and 5 into root using the insert_key method.

DBMS Theory

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

    def insert_key(self, key):
        self.keys.append(key)
        self.keys.sort()

max_keys = 3

# Create root node and insert keys 10, 20, 5
# Your code here

Hint

Use the insert_key method to add keys to the root node.

Practice

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

easy

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

B. To store data in a flat file for easy access

C. To encrypt data for security

D. To backup data automatically

Solution

1. Step 1: Understand what a B-tree index does

   A B-tree index organizes data in a balanced tree structure to make searching faster.

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

   Only To speed up data searching by organizing data in a balanced tree describes speeding up search using a balanced tree, which matches B-tree index use.

3. Final Answer:

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

4. Quick Check:

   B-tree index = speed up search [OK]

Hint: B-tree indexes speed up search by balanced tree structure [OK]

Common Mistakes:

• Confusing B-tree with encryption or backup
• Thinking B-tree stores data flatly
• Assuming B-tree slows down all operations

2. Which of the following is the correct way to create a B-tree index on column name in SQL?

easy

A. CREATE INDEX idx_name BY BTREE ON table_name (name);

B. CREATE BTREE INDEX idx_name ON table_name (name);

C. CREATE INDEX idx_name ON table_name (name);

D. CREATE INDEX idx_name USING BTREE ON table_name (name);

Solution

1. Step 1: Recall SQL syntax for B-tree index creation

   The standard syntax to specify B-tree index is using USING BTREE clause.

2. Step 2: Check each option's syntax

   CREATE INDEX idx_name USING BTREE ON table_name (name); uses CREATE INDEX idx_name USING BTREE ON table_name (name); which is correct. CREATE INDEX idx_name ON table_name (name); creates an index but does not specify B-tree explicitly. Options B and D have invalid syntax.

3. Final Answer:

   CREATE INDEX idx_name USING BTREE ON table_name (name); -> Option D

4. Quick Check:

   Correct syntax includes USING BTREE [OK]

Hint: Use 'USING BTREE' clause to specify B-tree index in SQL [OK]

Common Mistakes:

• Omitting USING BTREE when required
• Using BY or incorrect keywords
• Assuming default index is always B-tree

3. Given a B-tree index on column age, what will be the result of the query:
SELECT * FROM users WHERE age BETWEEN 20 AND 30;?

medium

A. The query will scan the entire table without using the index

B. The query will use the B-tree index to quickly find rows with age between 20 and 30

C. The query will return an error because BETWEEN is not supported with B-tree

D. The query will only return rows where age is exactly 20 or 30

Solution

1. Step 1: Understand B-tree index support for range queries

   B-tree indexes support range queries efficiently, such as BETWEEN.

2. Step 2: Analyze query behavior with B-tree index

   The query uses BETWEEN 20 AND 30, so the B-tree index will help find all rows in that range quickly.

3. Final Answer:

   The query will use the B-tree index to quickly find rows with age between 20 and 30 -> Option B

4. Quick Check:

   B-tree supports range queries = fast search [OK]

Hint: B-tree indexes speed up range queries like BETWEEN [OK]

Common Mistakes:

• Thinking B-tree only supports exact matches
• Assuming BETWEEN causes errors
• Believing full table scan always happens

4. A developer created a B-tree index on column salary but notices queries using salary are still slow. Which of the following is a likely cause?

medium

A. The index was created but the column has many NULL values and queries filter on NULL

B. The B-tree index automatically speeds up all queries regardless of conditions

C. The database does not support B-tree indexes

D. The index was created on a different column by mistake

Solution

1. Step 1: Identify why B-tree index might not help

   If the column has many NULL values and queries filter on NULL, B-tree index may not be used effectively.

2. Step 2: Evaluate other options

   The B-tree index automatically speeds up all queries regardless of conditions is false because indexes don't speed up all queries automatically. The database does not support B-tree indexes is unlikely if B-tree index was created. The index was created on a different column by mistake is possible but less likely than D given the scenario.

3. Final Answer:

   The index was created but the column has many NULL values and queries filter on NULL -> Option A

4. Quick Check:

   NULL values can reduce B-tree index effectiveness [OK]

Hint: NULL values can prevent B-tree index use in queries [OK]

Common Mistakes:

• Assuming index always speeds up queries
• Ignoring NULL value impact
• Believing database lacks B-tree support without checking

5. You have a large table with millions of rows and want to optimize queries that search for customers by last name prefix (e.g., names starting with 'Sm'). How can a B-tree index help, and what is a limitation you must consider?

hard

A. B-tree index cannot help prefix searches; use hash index instead

B. B-tree index speeds up prefix searches and has no impact on insert speed

C. B-tree index can speed up prefix searches, but it may slow down insert operations

D. B-tree index only works for numeric columns, so it cannot help here

Solution

1. Step 1: Understand B-tree index support for prefix searches

   B-tree indexes support prefix searches efficiently by traversing the tree to matching keys.

2. Step 2: Consider performance trade-offs

   While B-tree indexes speed up reads, they can slow down insert and update operations because the tree must be maintained.

3. Final Answer:

   B-tree index can speed up prefix searches, but it may slow down insert operations -> Option C

4. Quick Check:

   B-tree = fast prefix search + slower inserts [OK]

Hint: B-tree helps prefix search but slows inserts due to tree maintenance [OK]

Common Mistakes:

• Thinking B-tree can't do prefix searches
• Ignoring insert/update slowdown
• Believing B-tree only works on numbers