Database Indexing (B-Trees)

Metadata

1. Overview

What problem does it solve?

Imagine an unorganized physical library with 10 million books. If I ask you to find a specific book by title, your only option is to walk through every single aisle and check every single book. This is called a Full Table Scan. It takes O(N) time.

A Database Index is the equivalent of the library's card catalog. It is a separate, highly organized data structure that allows the database engine to find the exact location of a row on disk in O(\log N) time, turning a query that takes 5 seconds into one that takes 5 milliseconds.

What breaks without it?

• Horrible Latency: Without indexes, a query on a 1-billion row table will scan the entire hard drive, locking up the database and timing out the client.
• CPU Spikes: Scanning millions of irrelevant rows consumes massive amounts of CPU and Memory (thrashing the Buffer Pool).
• Deadlocks: Table scans hold locks on rows for a long time, causing write operations from other users to stall and crash.

2. Motivation

Why not just use Hash Maps?

We learned in Block 005 (Hashing) that Hash Maps have O(1) lookup time. Why don't databases use Hash Maps?

Hash Maps are great for exact match lookups (WHERE id = 42). But they are completely useless for range queries (WHERE age > 18 AND age < 30). Because a hash function randomizes the output, hash(18) and hash(19) are stored in completely different locations.

To support range queries, sorting, and efficient disk storage, databases need a data structure that keeps keys sorted and is optimized for reading blocks of data from a spinning hard drive. Enter the B-Tree.

3. Real-World Usage

4. Prerequisites

5. Visual Explanation

The B+ Tree (How MySQL stores data)

In a B+ Tree, the internal nodes act purely as "traffic cops" directing the search. The actual row data (or a pointer to the row on disk) is only stored at the very bottom in the "Leaf Nodes".

Furthermore, the Leaf Nodes are connected via a linked list, making range queries extremely fast.

graph TD
    Root["[ 50 ]"] --> L1["[ 20 | 35 ]"]
    Root --> R1["[ 75 | 90 ]"]
    
    L1 --> LL1["[ 10, 15 ]"]
    L1 --> LL2["[ 20, 25, 30 ]"]
    L1 --> LL3["[ 35, 42 ]"]
    
    R1 --> RL1["[ 50, 60 ]"]
    R1 --> RL2["[ 75, 80 ]"]
    R1 --> RL3["[ 90, 99 ]"]
    
    %% Linked List between leaves for fast range scans
    LL1 -.-> LL2 -.-> LL3 -.-> RL1 -.-> RL2 -.-> RL3
    
    style Root fill:#f9f,stroke:#333
    style LL1 fill:#bbf,stroke:#333
    style LL2 fill:#bbf,stroke:#333
    style LL3 fill:#bbf,stroke:#333
    style RL1 fill:#bbf,stroke:#333
    style RL2 fill:#bbf,stroke:#333
    style RL3 fill:#bbf,stroke:#333

Query: SELECT * WHERE id = 25

1. Start at Root [50]. 25 is less than 50, go left.
2. At [20 | 35]. 25 is between 20 and 35, go down middle.
3. Arrive at Leaf [20, 25, 30]. Found 25! (Takes exactly 3 disk reads, even if the table has 1 billion rows).

6. Internal Working

6.1 Clustered vs Secondary Indexes

Clustered Index (Primary Key):

• Determines the physical order of the data on the hard drive.
• There can only be one clustered index per table.
• The leaf nodes contain the actual full row data (id, name, email).

Secondary Index (e.g., Index on email):

• A separate B-Tree.
• The leaf nodes do not contain the row data. Instead, they contain the Primary Key.
• To find a user by email, the DB searches the Email B-Tree, finds the Primary Key (id=42), and then does a second search on the Primary Key B-Tree to fetch the row. (This is called a Bookmark Lookup or Index Lookup).

6.2 The LSM Tree (Log-Structured Merge Tree)

B-Trees are great for reading, but bad for writing. If you write randomly, the B-Tree has to split nodes and move data around on disk, which is slow.

NoSQL databases (Cassandra, RocksDB) use LSM Trees.

1. All writes go directly into RAM (MemTable). Blazing fast.
2. When RAM is full, it flushes the sorted data to disk as an immutable file (SSTable).
3. Over time, background processes merge these files together. Tradeoff: Writes are incredibly fast. Reads are slightly slower because the DB might have to check multiple files.

7. Implementation

Why Python? We will simulate how a database executes a query with and without an index, demonstrating the massive performance difference between an O(N) table scan and an O(\log N) binary search.

"""
013 - Database Indexing Simulation
Demonstrates the difference between a Full Table Scan O(N) 
and an Index Lookup O(log N).
"""
import time
import bisect

# ── 1. Create a massive mock table ──
# 1 Million rows. Format: {"id": int, "email": str, "name": str}

print("Generating 1,000,000 rows of database records...")
table = []
for i in range(1, 1_000_001):
    table.append({
        "id": i,
        "email": f"user{i}@example.com",
        "name": f"User {i}"
    })

TARGET_EMAIL = "user999999@example.com"
print("Table generation complete.\n")


# ── 2. Query WITHOUT an Index (Full Table Scan) ──

def query_without_index(email_to_find):
    """O(N) operation - Scans every row."""
    start_time = time.time()
    
    result = None
    scanned_rows = 0
    
    # The database must look at every single row
    for row in table:
        scanned_rows += 1
        if row["email"] == email_to_find:
            result = row
            break # Found it, stop scanning (in worst case, it's at the end)
            
    duration = (time.time() - start_time) * 1000
    print(f"[NO INDEX] Found: {result['name']}")
    print(f"  Rows Scanned: {scanned_rows:,}")
    print(f"  Time Taken:   {duration:.2f} ms\n")


# ── 3. Build a Secondary Index ──

print("Building Secondary Index on 'email' column...")
# An index is just a sorted list of tuples: (indexed_value, pointer_to_row)
# Real DBs use B-Trees, we will use a sorted array + Binary Search (O(log N))
email_index = []
for idx, row in enumerate(table):
    email_index.append((row["email"], idx))

# Sort the index alphabetically by email
email_index.sort(key=lambda x: x[0])
print("Index built.\n")


# ── 4. Query WITH an Index ──

def query_with_index(email_to_find):
    """O(log N) operation - Binary Search on the index."""
    start_time = time.time()
    
    # Extract just the emails for the binary search function
    just_emails = [item[0] for item in email_index]
    
    # 1. Binary Search the index to find the pointer (O(log N))
    # This simulates walking down the B-Tree
    index_pos = bisect.bisect_left(just_emails, email_to_find)
    
    result = None
    if index_pos != len(email_index) and email_index[index_pos][0] == email_to_find:
        # 2. Use the pointer to fetch the actual row O(1)
        row_pointer = email_index[index_pos][1]
        result = table[row_pointer]
        
    duration = (time.time() - start_time) * 1000
    print(f"[WITH INDEX] Found: {result['name']}")
    # Binary search takes roughly log2(1,000,000) = ~20 steps
    print(f"  Steps Taken:  ~20 (Logarithmic)") 
    print(f"  Time Taken:   {duration:.2f} ms\n")


# ── Run the Simulation ──
if __name__ == "__main__":
    print(f"Querying for: {TARGET_EMAIL}\n")
    query_without_index(TARGET_EMAIL)
    query_with_index(TARGET_EMAIL)

Sample Output

Generating 1,000,000 rows of database records...
Table generation complete.

Building Secondary Index on 'email' column...
Index built.

Querying for: user999999@example.com

[NO INDEX] Found: User 999999
  Rows Scanned: 999,999
  Time Taken:   58.42 ms

[WITH INDEX] Found: User 999999
  Steps Taken:  ~20 (Logarithmic)
  Time Taken:   0.05 ms

Result: The indexed query is 1,168x faster.

8. Complexity

Why indexes slow down Writes

Every time you INSERT, UPDATE, or DELETE a row, the database must not only update the base table, but it must also re-balance every single B-Tree index attached to that table. If a table has 10 indexes, an INSERT does 11 write operations. Do not over-index!

9. Trade-offs

10. Production Evolution

11. Common Bugs

12. Interview Questions

1. Why does a database use a B-Tree instead of a Hash Map? Hint: Hash Maps cannot do range queries (BETWEEN 10 AND 20) or sorting (ORDER BY). B-Trees keep keys sorted and allow fast sequential disk reads.

2. What is a Covering Index? Hint: When the Secondary Index contains all the columns requested in the SELECT clause, the database doesn't need to do a secondary lookup to the clustered index. It returns the data straight from the B-Tree.

3. You have an index on (age, city). Which of these queries will use the index? A) WHERE age = 20, B) WHERE city = 'NY', C) WHERE age = 20 AND city = 'NY'? Hint: A and C. B will NOT use the index due to the Left-Prefix rule. You can't search a phonebook by first name.

4. Why shouldn't you put an index on every single column? Hint: Every index requires disk space. More importantly, every INSERT, UPDATE, or DELETE requires updating every single index, drastically slowing down write performance.

13. Used By (Downstream Blocks)

• 014 SQL vs NoSQL — LSM trees are a major reason NoSQL databases scale writes better than SQL.
• 017 Data Partitioning — How to scale indexes across multiple physical servers.

14. Used In (Case Studies)

15. Related Blocks

16. Try It Yourself

Exercise 1: Composite Index Simulation

Modify the Python script. Create a table with first_name and last_name. Build a composite index (a list of tuples: (last_name, first_name, row_pointer)). Prove that searching by last_name is fast, but searching by first_name alone requires scanning the whole index.

Exercise 2: EXPLAIN query

If you have MySQL or PostgreSQL installed, create a table with 100k rows. Run EXPLAIN ANALYZE SELECT * FROM table WHERE column = 'value'. Notice it says "Seq Scan" (Sequential Scan). Add an index and run it again to see "Index Scan".

Website Metadata