B-Trees: Internal Structure & Index vs. Sequential Scans

1. The Default: Sequential Scan

Imagine being asked to find every mention of the name "Paul Atreides" in a library where books are placed on shelves in no particular order. You would have no choice but to start at the first shelf, pick up every book, flip through every page, and repeat until you've checked the entire library. This is a sequential scan (or full table scan).

When you issue a query like SELECT * FROM chunks WHERE content LIKE '%Gom Jabbar%'; on a table with no index, PostgreSQL does the digital equivalent of this. It must read every single row (or more precisely, every page of data on disk) and check if it matches your condition.

For a small table, this is perfectly acceptable. But for your capstone project, which will eventually store millions of text chunks, a sequential scan for every query would be catastrophically slow. Its performance is O(N), where N is the size of the table. As your data grows, query time grows linearly. This is not a scalable design.

2. The Solution: B-Tree Indexes

To solve the library problem, you would create a card catalog. Instead of searching the books themselves, you'd go to the "P" drawer, find the card for "Paul Atreides," and it would tell you exactly which books and pages contain that name. This is an index.

In database systems, the most common type of index is the B-Tree. Or, to be more precise, a variation called the B+Tree. While PostgreSQL documentation often refers to them as "B-Trees," their implementation is a B+Tree, a distinction you'll appreciate.

To understand the internal mechanics from first principles, we'll turn to a classic lecture from Carnegie Mellon University's Database Group. It provides a phenomenal breakdown of the B+Tree data structure.

The PostgreSQL documentation on B-Tree Implementation confirms that the real-world system uses these exact concepts.

3. The Planner's Dilemma: Index Scan or Sequential Scan?

Now you understand two ways to find data:

1. Sequential Scan: Read the whole table. O(N)
2. Index Scan: Traverse the B-Tree to find pointers to the rows, then fetch those rows. O(log N) for the lookup, plus the cost of fetching the data.

It seems like an index scan is always better, but it's not that simple. The decision is made by a component called the Query Planner (or Optimizer). Its sole job is to find the most efficient execution plan for your query, and it does this by estimating the cost of different plans.

The core of this decision boils down to the cost of I/O. Accessing data on a disk (even an SSD) is one of the slowest operations a database performs. The planner's model simplifies this into two main types of I/O:

• Sequential I/O: Reading data blocks that are physically next to each other. This is fast and efficient. A sequential scan primarily uses this.
• Random I/O: Jumping to different, non-contiguous locations on the disk to read data blocks. This is much slower. An index scan involves random I/O: first to read parts of the index, then to jump to the actual table data, which could be scattered all over the disk.

PostgreSQL models this trade-off with two key configuration parameters.

This cost differential is the heart of the planner's decision.

• When your query is highly selective (e.g., WHERE id = 42, which matches one row), an index scan is a clear winner. The cost is roughly (cost of a few random I/Os to traverse the tree) + (cost of one random I/O to fetch the data). This is far cheaper than reading the entire table.

• When your query is not selective (e.g., WHERE value > 10, which might match 50% of the table), the planner must compare two scenarios:

  1. Sequential Scan Cost: (total_pages * seq_page_cost)
  2. Index Scan Cost: (index_pages_read * random_page_cost) + (table_rows_to_fetch * random_page_cost)

  If the query needs to retrieve a large percentage of the table's rows, the accumulated cost of thousands of expensive random I/Os for the index scan will exceed the cost of one cheap sequential scan. In this case, the planner will wisely choose the sequential scan, even if an index is available.

The "tipping point" is typically when a query needs to fetch somewhere between 5% and 10% of the total rows in a table. Below this threshold, an index scan is preferred; above it, a sequential scan is often more efficient.

This image perfectly visualizes the two paths the database engine can take.

4. Practical Investigation

Let's prove this behavior. For this task, you'll need to use the psql command-line interface.

1. Connect to your database: psql -U youruser -d yourdb

2. Create an experimental table: We'll create a table with 100,000 rows.

   CREATE TABLE IF NOT EXISTS planner_test (
       id SERIAL PRIMARY KEY,
       payload TEXT,
       value INT
   );
   
   -- Generate 100,000 rows of data
   INSERT INTO planner_test (payload, value)
   SELECT
       md5(random()::text),
       (random() * 10000)::int
   FROM generate_series(1, 100000);
   
   -- Create an index on the 'value' column
   CREATE INDEX IF NOT EXISTS idx_planner_test_value ON planner_test(value);
   
   -- Ensure the planner has statistics about the table
   ANALYZE planner_test;
   

3. Test a highly selective query: Find a single value.

   EXPLAIN SELECT * FROM planner_test WHERE value = 1234;
   

   Observe the query plan. You should see Index Scan using idx_planner_test_value. The planner correctly identified that using the index is the fastest way to find this single row.

4. Test a non-selective query: Find all values greater than a low number.

   EXPLAIN SELECT * FROM planner_test WHERE value > 100;
   

   This query will match most of the rows. Look at the plan. You should see Seq Scan on planner_test. The planner has calculated that it's cheaper to read the whole table than to perform ~99,000 random I/O operations.

5. Find the tipping point: Experiment with the WHERE value > X clause, changing X to find the approximate value where the planner switches from an Index Scan to a Seq Scan. Try values like 8000, 9000, 9500. There is no need to be exact; the goal is to observe the behavior change.

In your engineering journal, document the results of this experiment. What was the approximate selectivity at which the planner's strategy changed? This hands-on feel for the planner's decision-making is invaluable.

Conclusion

You have now moved beyond simply using a database to understanding how it thinks. This is a crucial step towards engineering robust and performant systems.

Key Takeaways:

• Sequential Scans read an entire table (O(N)) and are efficient only for small tables or non-selective queries.
• B+Tree Indexes are balanced search trees that provide O(log N) lookups, enabling fast, selective queries. They maintain balance through splits and merges.
• The PostgreSQL Query Planner makes a cost-based decision between an index scan and a sequential scan.
• This decision is dominated by the estimated I/O cost, driven by the random_page_cost vs. seq_page_cost parameters and the selectivity of the query.
• For highly selective queries, index scans are preferred. For queries that retrieve a large portion of the table, a sequential scan is often cheaper.

In our next lesson, we will go one level deeper. The EXPLAIN command you used today has a more powerful sibling: EXPLAIN ANALYZE. We will learn to use it to inspect and interpret detailed query execution plans, identifying exactly where and why a query is slow. This is the fundamental skill of database performance tuning.