B-tree index (default) behavior in PostgreSQL - Step-by-Step Execution

Concept Flow - B-tree index (default) behavior

Start: Insert/Search Key

↓

Check Root Node

↓

Compare Key with Node Keys

↓

Go to Child

↓

Repeat at Child

↓

If Insert and Node Full

↓

Split Node and Promote Middle Key

↓

Update Parent Node

↓

End

The B-tree index starts at the root, compares keys to find the correct child or leaf, and on insert splits nodes if full, promoting keys up to keep the tree balanced.

Execution Sample

PostgreSQL

CREATE TABLE fruits(id SERIAL PRIMARY KEY, name TEXT);
CREATE INDEX idx_name ON fruits(name);
INSERT INTO fruits(name) VALUES ('apple'), ('banana'), ('cherry');
SELECT * FROM fruits WHERE name = 'banana';

This creates a table and a B-tree index on the 'name' column, inserts some fruits, and queries for 'banana' using the index.

Execution Table

Step	Action	Node Level	Keys in Node	Comparison Result	Next Step/Output
1	Start search for 'banana'	Root	['apple', 'cherry']	'banana' > 'apple', < 'cherry'	Go to child between 'apple' and 'cherry'
2	At leaf node	Leaf	['apple', 'banana', 'cherry']	'banana' == 'banana'	Found key, return row(s)
3	Insert 'date'	Leaf	['apple', 'banana', 'cherry']	'date' > 'cherry'	Insert at leaf
4	Leaf node full after insert	Leaf	['apple', 'banana', 'cherry', 'date']	Node full (max keys reached)	Split leaf node
5	Split leaf node	Leaf	Left: ['apple', 'banana'], Right: ['cherry', 'date']	Promote 'cherry' to parent	Update parent node
6	Update root node keys	Root	['cherry']	Root updated with promoted key	Insertion complete
7	Search for 'date'	Root	['cherry']	'date' > 'cherry'	Go to right child leaf
8	At leaf node	Leaf	['cherry', 'date']	'date' == 'date'	Found key, return row(s)
9	End	-	-	-	Search/Insert complete

💡 Search ends when key is found or leaf reached; insert ends after node split and parent update if needed.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 5	After Step 6	Final
Root Node Keys	['apple', 'cherry']	['apple', 'cherry']	['apple', 'cherry']	['cherry']	['cherry']	['cherry']
Leaf Node Keys	['apple', 'banana', 'cherry']	['apple', 'banana', 'cherry', 'date']	Node split	Left: ['apple', 'banana'], Right: ['cherry', 'date']	N/A	N/A
Search Key	N/A	'date'	'date'	'date'	'date'	N/A

Key Moments - 3 Insights

Why does the root node keys change after inserting 'date'?

Because the leaf node became full and split, the middle key 'cherry' was promoted to the root node to keep the tree balanced, as shown in execution_table rows 4-6.

Why do we go to a child node after comparing keys in the root?

In a B-tree, internal nodes guide the search by comparing keys and choosing the correct child node to continue searching, as seen in execution_table row 1.

What happens when the leaf node is full during insert?

The leaf node splits into two nodes, and the middle key is promoted to the parent node to maintain balance, shown in execution_table rows 4 and 5.

Visual Quiz - 3 Questions

Look at the execution_table, at which step is the leaf node split due to being full?

A Step 4

B Step 3

C Step 5

D Step 6

💡 Hint

Check the 'Action' column for 'Node full after insert' and 'Split leaf node' in rows.

According to variable_tracker, what are the root node keys after the split and promotion?

A ['apple', 'banana']

B ['apple', 'cherry']

C ['cherry']

D ['banana', 'date']

💡 Hint

Look at 'Root Node Keys' values after Step 5 and Step 6 in variable_tracker.

If we searched for 'apple' instead of 'banana', at which step would the search go to the left child?

A Step 7

B Step 1

C Step 2

D Step 8

💡 Hint

Refer to execution_table row 1 where the root node keys guide the search direction.

Concept Snapshot

B-tree index stores keys in sorted order in nodes.
Search starts at root, compares keys, and moves down child nodes.
Leaf nodes hold actual keys and pointers to rows.
On insert, if node is full, it splits and promotes middle key.
This keeps the tree balanced for fast search and insert.
PostgreSQL uses B-tree as default index type.

Full Transcript

A B-tree index in PostgreSQL organizes data in a balanced tree structure. When searching for a key, it starts at the root node and compares the key with keys stored there. Depending on the comparison, it moves to the appropriate child node. This process repeats until it reaches a leaf node where the actual key is stored. If the key is found, the corresponding row is returned. When inserting a new key, if the leaf node is full, it splits into two nodes and the middle key is promoted to the parent node. This promotion may propagate up to the root, keeping the tree balanced. This behavior ensures efficient search and insert operations. The execution table shows step-by-step how a search and insert happen, including node splits and key promotions. The variable tracker shows how keys in nodes change during these steps. Key moments clarify why nodes split and how the tree structure updates. The visual quiz tests understanding of these steps. The concept snapshot summarizes the B-tree index behavior in PostgreSQL.

Practice

1. What is the primary purpose of a B-tree index in PostgreSQL?

easy

A. To speed up searching and sorting operations

B. To store large binary objects

C. To manage user permissions

D. To backup the database automatically

Solution

1. Step 1: Understand the role of indexes

   Indexes help databases find data faster without scanning the entire table.

2. Step 2: Identify B-tree index function

   B-tree indexes organize data to speed up searching and sorting efficiently.

3. Final Answer:

   To speed up searching and sorting operations -> Option A

4. Quick Check:

   B-tree index = speed up search/sort [OK]

Hint: B-tree indexes speed up search and sort operations [OK]

Common Mistakes:

• Confusing B-tree with storing large objects
• Thinking indexes manage permissions
• Assuming indexes handle backups

2. Which of the following is the correct syntax to create a B-tree index on the column username of table users?

easy

A. CREATE BTREE INDEX idx_username ON users (username);

B. CREATE INDEX idx_username ON users USING bitmap (username);

C. CREATE INDEX idx_username ON users (username) USING hash;

D. CREATE INDEX idx_username ON users USING btree (username);

Solution

1. Step 1: Recall correct CREATE INDEX syntax

   The syntax is CREATE INDEX index_name ON table_name USING index_type (column);

2. Step 2: Identify correct index type and syntax

   B-tree is default and specified as USING btree; CREATE INDEX idx_username ON users USING btree (username); matches this exactly.

3. Final Answer:

   CREATE INDEX idx_username ON users USING btree (username); -> Option D

4. Quick Check:

   Correct syntax uses USING btree [OK]

Hint: Use 'USING btree' in CREATE INDEX for B-tree indexes [OK]

Common Mistakes:

• Using incorrect index type like hash or bitmap
• Wrong keyword order in CREATE INDEX
• Omitting USING clause or misspelling it

3. Given a table products(id SERIAL PRIMARY KEY, price NUMERIC) with a B-tree index on price, what will the query SELECT * FROM products WHERE price > 100 ORDER BY price; most likely use?

medium

A. A sequential scan ignoring the index

B. A B-tree index scan to quickly find rows with price > 100

C. A hash index scan on price

D. A bitmap index scan on price

Solution

1. Step 1: Understand query conditions and index type

   The query filters with price > 100 and orders by price; B-tree indexes support range queries and sorting.

2. Step 2: Identify index usage

   PostgreSQL will use the B-tree index to efficiently find and order matching rows.

3. Final Answer:

   A B-tree index scan to quickly find rows with price > 100 -> Option B

4. Quick Check:

   Range query + order = B-tree index scan [OK]

Hint: Range queries with ORDER BY use B-tree index scans [OK]

Common Mistakes:

• Assuming sequential scan always used
• Confusing hash or bitmap index usage
• Ignoring index benefits for range queries

4. You created a B-tree index on column email but notice queries filtering by LOWER(email) are slow. What is the likely problem?

medium

A. B-tree indexes only work on numeric columns

B. The index was created on the wrong table

C. B-tree indexes do not support functions like LOWER() by default

D. The database needs to be restarted to use the index

Solution

1. Step 1: Understand function usage in WHERE clause

   Using LOWER(email) means the query filters on a transformed value, not the raw column.

2. Step 2: Recognize index limitations

   Regular B-tree indexes do not support functions unless a functional index is created.

3. Final Answer:

   B-tree indexes do not support functions like LOWER() by default -> Option C

4. Quick Check:

   Function in filter needs functional index [OK]

Hint: Use functional indexes for queries with functions like LOWER() [OK]

Common Mistakes:

• Thinking B-tree only works on numbers
• Assuming index applies automatically after restart
• Mistaking wrong table for index issue

5. You want to enforce uniqueness on a column serial_number and speed up queries filtering by it. Which is the best approach using B-tree indexes?

hard

A. Create a UNIQUE B-tree index on serial_number

B. Create a non-unique B-tree index and a separate UNIQUE constraint

C. Create a hash index and a UNIQUE constraint

D. Create a UNIQUE constraint without an index

Solution

1. Step 1: Understand uniqueness enforcement

   PostgreSQL enforces UNIQUE constraints using unique indexes, usually B-tree by default.

2. Step 2: Combine uniqueness and performance

   Creating a UNIQUE B-tree index both enforces uniqueness and speeds up lookups on that column.

3. Final Answer:

   Create a UNIQUE B-tree index on serial_number -> Option A

4. Quick Check:

   Unique B-tree index = uniqueness + speed [OK]

Hint: Use UNIQUE B-tree index to enforce uniqueness and speed queries [OK]

Common Mistakes:

• Creating separate index and constraint unnecessarily
• Using hash index which doesn't enforce uniqueness
• Assuming UNIQUE constraint works without an index