How Indexes Work: Data Structures and Search Algorithms

Today, we're diving deeper into the architecture of indexes and checking out how they really work under the hood. Knowing how an index is built not only helps you understand why queries run faster, but also how to pick the best indexes for different jobs.

When we talk about index structure, we mean how the data is organized inside the index to make searching fast. Imagine a filing cabinet. If all the documents are just thrown in a pile, finding the one you need is tough. But if the cabinet is sorted alphabetically, searching gets way easier. Indexes work just like that: they organize data so you can find what you need as quickly as possible.

B-TREE Index Structure

B-TREE (balanced tree) is the most commonly used index type in PostgreSQL. Basically, it's a tree-like structure where data is organized into nodes, and searching happens by navigating from the root of the tree down to the leaves.

What it looks like:

         Root
          /       |       \
      Node 1    Node 2    Node 3
     /   \       |       /   \
Leaf1 Leaf2   Leaf3  Leaf4 Leaf5

Each node holds key values that help guide the search. For example, if the root node has values [10, 20, 30], then:

• All data less than 10 is in Leaf 1.
• All data between 10 and 20 is in Leaf 2, and so on.

Advantages of B-TREE indexes:

• Fast data search: search complexity is O(log n), which is way faster than linear search.
• Great for range queries (like finding all values between 10 and 50).

Example: let's say we have a students table with an age column. When we create a B-TREE index on that column:

CREATE INDEX age_idx ON students (age);

PostgreSQL builds a balanced tree for the age values, letting you quickly find students of a certain age or in an age range.

Search Algorithm in B-TREE

When you run a query, PostgreSQL uses the index to search for data like this:

1. Figures out the search key (like age 25).
2. Starts at the root node.
3. Compares the key with the node's value ranges and moves to the right child node.
4. Repeats step 3 until it hits a leaf.
5. Returns the data from the leaf that matches the key.

Query example:

SELECT * FROM students WHERE age = 25;

The index cuts down the amount of data that needs to be scanned, making the search super fast.

Search Algorithms and Performance

Indexes speed up searches by reducing the number of rows that need to be scanned. Without an index, PostgreSQL scans the whole table (this is called a sequential scan, or Seq Scan). With an index, you get an index scan (Index Scan), which is way faster.

Comparing sequential and index scans

• Sequential scan (Seq Scan):

  • PostgreSQL reads every row in the table, checks the query conditions, and returns the matching rows.
  • Used if there's no index or if the query covers almost all the rows in the table.

• Index scan (Index Scan):

  • PostgreSQL uses the index to find the matching rows, then only looks up those rows in the table.
  • Way faster for big tables if the query only grabs a small chunk of data.

Example: without an index, searching for ages

SELECT * FROM students WHERE age = 25;

could mean reading 1 million rows. With a B-TREE index, the system might only read 100 rows.

How Index Structure Affects Performance

Indexes are faster because they cut down the amount of data that needs to be scanned. For example, if a table has millions of rows, the index organizes them so the query only needs to read a few nodes instead of the whole table.

It's super important to understand index structure. Knowing how indexes work helps you figure out why some queries are slow and how to speed them up.

It's also important to know which indexes to use. For range searches, use B-TREE. For arrays or JSONB — GIN. Picking the wrong index can actually slow your database down.

Real-World Examples

Let's check out how indexes help us in practice.

Index for Sorting

CREATE INDEX salary_idx ON employees (salary);
SELECT * FROM employees ORDER BY salary;

With a B-TREE index, PostgreSQL can return sorted data straight from the index, no extra sorting needed.

Index for Ranges

CREATE INDEX price_idx ON products (price);
SELECT * FROM products WHERE price BETWEEN 100 AND 500;

The B-TREE index lets you quickly find rows that fall in the given range.

Frequently Asked Questions and Gotchas

Why shouldn't you always use indexes? Indexes take up disk space and slow down insert, update, and delete operations, since the index structure has to be updated too. So, only create indexes for columns you use a lot.

When don't indexes help? For queries that cover most of the table (like WHERE true), PostgreSQL will go with Seq Scan, since reading index nodes doesn't give any benefit.