Fondamentaux des index B-Tree

Ever looked up a word in a dictionary? You don't read every page; you use the alphabetical index to jump straight to the letter, then the word.

Database indexes work similarly. They are special lookup tables that the database search engine can use to speed up data retrieval. Without them, finding specific data in a large table can be like reading every page of a book to find one word.

In PostgreSQL, the B-Tree index is the most common and default type. It's so fundamental that when you create a PRIMARY KEY, PostgreSQL automatically builds a B-Tree index for it!

The 'B' often stands for 'balanced,' referring to how the tree keeps all its 'leaves' (where data pointers are) at roughly the same depth, ensuring efficient searches.

Think of a B-Tree as a hierarchical structure, like an upside-down tree. It's made up of different types of nodes:

• Root Node: The very top node; every search starts here.
• Branch Nodes: Intermediate nodes that point towards other branch nodes or leaf nodes. They guide the search path.
• Leaf Nodes: The bottom-most nodes. These contain the actual index entries and pointers to the rows in your table.

Each node in a B-Tree contains a sorted list of keys and pointers. The keys are the values from the indexed column (e.g., user IDs, product names).

Branch nodes have keys that define ranges, pointing to the next node in the path. Leaf nodes contain the actual indexed key values and a Tuple ID (TID), which is a physical pointer to the exact location of the row in the table.

When you query for a specific value, PostgreSQL traverses the B-Tree:

1. It starts at the root node.
2. Compares your search value with the keys in the current node to decide which child pointer to follow.
3. It moves down through branch nodes until it reaches a leaf node.
4. Once in the leaf node, it finds the key and uses its associated TID to fetch the full row directly from the table.

Let's see a simple query that benefits from an index. When you create a PRIMARY KEY, PostgreSQL automatically creates a B-Tree index behind the scenes.

Try running this SQL. Notice how quickly it finds the specific user:

In the previous example, the query for id = 3 was very fast because the PRIMARY KEY constraint on the id column automatically created a B-Tree index.

This index allows PostgreSQL to avoid scanning every single row in the users table. Instead, it uses the B-Tree to quickly locate the specific id=3 entry and then fetches the corresponding row.

B-Tree indexes aren't just great for finding exact matches (like id = 3). Because the keys in the leaf nodes are stored in sorted order and linked together, B-Trees are also highly efficient for range queries.

Queries using operators like >, <, >=, <=, or BETWEEN can quickly traverse the leaf nodes to find all values within a specified range.

Another significant benefit of B-Trees is their ability to speed up sorting operations. Since the index entries are already stored in sorted order, if your query includes an ORDER BY clause on the indexed column, PostgreSQL can often use the index to return results already sorted.

This can save the database from performing a separate, potentially expensive, sort operation on the entire dataset.

Let's test your understanding of B-Tree indexes.

Great job! In this lesson, you learned about the fundamentals of B-Tree indexes:

• They are the most common index type in PostgreSQL.
• They are 'balanced' trees made of root, branch, and leaf nodes.
• Nodes store sorted keys and pointers (TIDs) to actual table rows.
• B-Trees dramatically speed up finding specific data (equality searches).
• They are also very efficient for range queries and can help with ORDER BY clauses.

Understanding these basics is key to optimizing your PostgreSQL queries!