Tag: B-tree

Enter into psql terminal:

✗ psql postgres
psql (14.17 (Homebrew))
Type "help" for help.

postgres=# \l
                                     List of databases
           Name            |  Owner   | Encoding | Collate | Ctype |   Access privileges
---------------------------+----------+----------+---------+-------+-----------------------
 studio_development | postgres | UTF8     | C       | C     |

• Create a new test database
• Create a users Table
• Check the db and table details

postgres=# create database test_db;
CREATE DATABASE

test_db=# CREATE TABLE users (
user_id INT,
username VARCHAR(220),
email VARCHAR(150),
phone_number VARCHAR(20)
);
CREATE TABLE

test_db=# \dt
List of relations
 Schema | Name  | Type  |  Owner
--------+-------+-------+----------
 public | users | table | abhilash
(1 row)

test_db=# \d users;
                          Table "public.users"
    Column    |          Type          | Collation | Nullable | Default
--------------+------------------------+-----------+----------+---------
 user_id      | integer                |           |          |
 username     | character varying(220) |           |          |
 email        | character varying(150) |           |          |
 phone_number | character varying(20)  |           |          |

Add a Primary key to users and check the user table.

test_db=# ALTER TABLE users ADD PRIMARY KEY (user_id);
ALTER TABLE

test_db=# \d users;
                          Table "public.users"
    Column    |          Type          | Collation | Nullable | Default
--------------+------------------------+-----------+----------+---------
 user_id      | integer                |           | not null |
 username     | character varying(220) |           |          |
 email        | character varying(150) |           |          |
 phone_number | character varying(20)  |           |          |
Indexes:
    "users_pkey" PRIMARY KEY, btree (user_id)

# OR add primary key when creating the table:
CREATE TABLE users (
  user_id INT PRIMARY KEY,
  username VARCHAR(220),
  email VARCHAR(150),
  phone_number VARCHAR(20)
);

You can a unique constraint and an index added when adding a primary key.

Why does adding a primary key also add an index?

• A primary key must guarantee that each value is unique and fast to find.
• Without an index, the database would have to scan the whole table every time you look up a primary key, which would be very slow.
• So PostgreSQL automatically creates a unique index on the primary key to make lookups efficient and to enforce uniqueness at the database level.

👉 It needs the index for speed and to enforce the “no duplicates” rule of primary keys.

What is btree?

• btree stands for Balanced Tree (specifically, a “B-tree” data structure).
• It’s the default index type in PostgreSQL.
• B-tree indexes organize the data in a tree structure, so that searches, inserts, updates, and deletes are all very efficient — about O(log n) time.
• It’s great for looking up exact matches (like WHERE user_id = 123) or range queries (like WHERE user_id BETWEEN 100 AND 200).

👉 So when you see btree, it just means it’s using a very efficient tree structure for your primary key index.

Summary in one line:
Adding a primary key automatically adds a btree index to enforce uniqueness and make lookups super fast.

In MySQL (specifically InnoDB engine, which is default now):

• Primary keys always create an index automatically.
• The index is a clustered index — this is different from Postgres!
• The index uses a B-tree structure too, just like Postgres.

👉 So yes, MySQL also adds an index and uses a B-tree under the hood for primary keys.

But here’s a big difference:

• In InnoDB, the table data itself is stored inside the primary key’s B-tree.
  • That’s called a clustered index.
  • It means the physical storage of the table rows follows the order of the primary key.
• In PostgreSQL, the index and the table are stored separately (non-clustered by default).

Example: If you have a table like this in MySQL:

CREATE TABLE users (
  user_id INT PRIMARY KEY,
  username VARCHAR(220),
  email VARCHAR(150)
);

• user_id will have a B-tree clustered index.
• The rows themselves will be stored sorted by user_id.

Short version:

Why Indexing on Unique Columns (like email) Improves Lookup 🔍

Use Case

You frequently run queries like:

SELECT * FROM students WHERE email = 'john@example.com';

Without an index, this results in a full table scan — checking each row one-by-one.

With an index, the database can jump directly to the row using a sorted structure, significantly reducing lookup time — especially in large tables.

🌲 How SQL Stores Indexes Internally (PostgreSQL)

📚 PostgreSQL uses B-Tree indexes by default.

When you run:

CREATE UNIQUE INDEX idx_students_on_email ON students(email);

PostgreSQL creates a balanced B-tree like this:

          m@example.com
         /              \
  d@example.com     t@example.com
  /        \           /         \
...      ...        ...         ...

• ✅ Keys (email values) are sorted lexicographically.
• ✅ Each leaf node contains a pointer to the actual row in the students table (called a tuple pointer or TID).
• ✅ Lookup uses binary search, giving O(log n) performance.

⚙️ Unique Index = Even Faster

Because all email values are unique, the database:

• Can stop searching immediately once a match is found.
• Doesn’t need to scan multiple leaf entries (no duplicates).

🧠 Summary

What Exactly is a Clustered Index in MySQL (InnoDB)?

🔹 In MySQL InnoDB, the primary key IS the table.

🔹 A Clustered Index means:

• The table’s data rows are physically organized in the order of the primary key.
• No separate storage for the table – it’s merged into the primary key’s B-tree structure.

In simple words:
👉 “The table itself lives inside the primary key B-tree.”

That’s why:

• Every secondary index must store the primary key value (not a row pointer).
• InnoDB can only have one clustered index (because you can’t physically order a table in two different ways).

📈 Visual for MySQL Clustered Index

Suppose you have:

CREATE TABLE users (
  user_id INT PRIMARY KEY,
  username VARCHAR(255),
  email VARCHAR(255)
);

The storage looks like:

B-tree by user_id (Clustered)

user_id  | username | email
----------------------------
101      | Alice    | a@x.com
102      | Bob      | b@x.com
103      | Carol    | c@x.com

👉 Table rows stored directly inside the B-tree nodes by user_id!

🔵 PostgreSQL (Primary Key Index = Separate)

Imagine you have a users table:

users table (physical table):

row_id | user_id | username | email
-------------------------------------
  1    |   101   | Alice    | a@example.com
  2    |   102   | Bob      | b@example.com
  3    |   103   | Carol    | c@example.com

And the Primary Key Index looks like:

Primary Key B-Tree (separate structure):

user_id -> row pointer
 101    -> row_id 1
 102    -> row_id 2
 103    -> row_id 3

👉 When you query WHERE user_id = 102, PostgreSQL goes:

• Find user_id 102 in the B-tree index,
• Then jump to row_id 2 in the actual table.

🔸 Index and Table are separate.
🔸 Extra step: index lookup ➔ then fetch row.

🟠 MySQL InnoDB (Primary Key Index = Clustered)

Same users table, but stored like this:

Primary Key Clustered B-Tree (index + data together):

user_id | username | email
---------------------------------
  101   | Alice    | a@example.com
  102   | Bob      | b@example.com
  103   | Carol    | c@example.com

👉 When you query WHERE user_id = 102, MySQL:

• Goes straight to user_id 102 in the B-tree,
• Data is already there, no extra lookup.

🔸 Index and Table are merged.
🔸 One step: direct access!

📈 Quick Visual:

PostgreSQL
(Index)    ➔    (Table Row)
    |
    ➔ extra lookup needed

MySQL InnoDB
(Index + Row Together)
    |
    ➔ data found immediately

Summary:

• PostgreSQL: primary key index is separate ➔ needs 2 steps (index ➔ table).
• MySQL InnoDB: primary key index is clustered ➔ 1 step (index = table).

📚 How Secondary Indexes Work

Secondary Index = an index on a column that is not the primary key.

Example:

CREATE INDEX idx_username ON users(username);

Now you have an index on username.

🔵 PostgreSQL Secondary Index Behavior

• Secondary indexes are separate structures from the table (just like the primary key index).
• When you query by username, PostgreSQL:
  1. Finds the matching row_id using the secondary B-tree index.
  2. Then fetches the full row from the table by row_id.
• This is called an Index Scan + Heap Fetch.

📜 Example:

Secondary Index (username -> row_id):

username -> row_id
------------------
Alice    -> 1
Bob      -> 2
Carol    -> 3

(users table is separate)

👉 Flexible, but needs 2 steps: index (row_id) ➔ table.

🟠 MySQL InnoDB Secondary Index Behavior

• In InnoDB, secondary indexes don’t store row pointers.
• Instead, they store the primary key value!

So:

1. Find the matching primary key using the secondary index.
2. Use the primary key to find the actual row inside the clustered primary key B-tree.

📜 Example:

Secondary Index (username -> user_id):

username -> user_id
--------------------
Alice    -> 101
Bob      -> 102
Carol    -> 103

(Then find user_id inside Clustered B-Tree)

✅ Needs 2 steps too: secondary index (primary key) ➔ clustered table.

📈 Quick Visual:

🌐 Now, let’s do some Real SQL Query ⛁ Examples!

1. Simple SELECT * FROM users WHERE user_id = 102;

• PostgreSQL:
  Look into PK btree ➔ find row pointer ➔ fetch row separately.
• MySQL InnoDB:
  Directly find the row inside the PK B-tree (no extra lookup).

✅ MySQL is a little faster here because it needs only 1 step!

2. SELECT username FROM users WHERE user_id = 102; (Only 1 Column)

• PostgreSQL:
  Might do an Index Only Scan if all needed data is in the index (very fast).
• MySQL:
  Clustered index contains all columns already, no special optimization needed.

✅ Both can be very fast, but PostgreSQL shines if the index is “covering” (i.e., contains all needed columns). Because index table has less size than clustered index of mysql.

3. SELECT * FROM users WHERE username = 'Bob'; (Secondary Index Search)

• PostgreSQL:
  Secondary index on username ➔ row pointer ➔ fetch table row.
• MySQL:
  Secondary index on username ➔ get primary key ➔ clustered index lookup ➔ fetch data.

✅ Both are 2 steps, but MySQL needs 2 different B-trees: secondary ➔ primary clustered.

Consider the below situation:

SELECT username FROM users WHERE user_id = 102;

• user_id is the Primary Key.
• You only want username, not full row.

Now:

🔵 PostgreSQL Behavior

👉 In PostgreSQL, by default:

• It uses the primary key btree to find the row pointer.
• Then fetches the full row from the table (heap fetch).

👉 But PostgreSQL has an optimization called Index-Only Scan.

• If all requested columns are already present in the index,
• And if the table visibility map says the row is still valid (no deleted/updated row needing visibility check),
• Then Postgres does not fetch the heap.

👉 So in this case:

• If the primary key index also stores username internally (or if an extra index is created covering username), Postgres can satisfy the query just from the index.

✅ Result: No table lookup needed ➔ Very fast (almost as fast as InnoDB clustered lookup).

📢 Postgres primary key indexes usually don’t store extra columns, unless you specifically create an index that includes them (INCLUDE (username) syntax in modern Postgres 11+).

🟠 MySQL InnoDB Behavior

• In InnoDB:
  Since the primary key B-tree already holds all columns (user_id, username, email),
  It directly finds the row from the clustered index.
• So when you query by PK, even if you only need one column, it has everything inside the same page/block.

✅ One fast lookup.

🔥 Why sometimes Postgres can still be faster?

• If PostgreSQL uses Index-Only Scan, and the page is already cached, and no extra visibility check is needed,
  Then Postgres may avoid touching the table at all and only scan the tiny index pages.
• In this case, for very narrow queries (e.g., only 1 small field), Postgres can outperform even MySQL clustered fetch.

💡 Because fetching from a small index page (~8KB) is faster than reading bigger table pages.

🎯 Conclusion:

✅ MySQL clustered index is always fast for PK lookups.
✅ PostgreSQL can be even faster for small/narrow queries if Index-Only Scan is triggered.

👉 Quick Tip:

• In PostgreSQL, you can force an index to include extra columns by using: CREATE INDEX idx_user_id_username ON users(user_id) INCLUDE (username); Then index-only scans become more common and predictable! 🚀

Isn’t PostgreSQL also doing 2 B-tree scans? One for secondary index and one for table (row_id)?

When you query with a secondary index, like:

SELECT * FROM users WHERE username = 'Bob';

• In MySQL InnoDB, I said:
  1. Find in secondary index (username ➔ user_id)
  2. Then go to primary clustered index (user_id ➔ full row)

Let’s look at PostgreSQL first:

♦️ Step 1: Search Secondary Index B-tree on username.

• It finds the matching TID (tuple ID) or row pointer.
  • TID is a pair (block_number, row_offset).
  • Not a B-tree! Just a physical pointer.

♦️ Step 2: Use the TID to directly jump into the heap (the table).

• The heap (table) is not a B-tree — it’s just a collection of unordered pages (blocks of rows).
• PostgreSQL goes directly to the block and offset — like jumping straight into a file.

🔔 Important:

• Secondary index ➔ TID ➔ heap fetch.
• No second B-tree traversal for the table!

🟠 Meanwhile in MySQL InnoDB:

♦️ Step 1: Search Secondary Index B-tree on username.

• It finds the Primary Key value (user_id).

♦️ Step 2: Now, search the Primary Key Clustered B-tree to find the full row.

• Need another B-tree traversal based on user_id.

🔔 Important:

• Secondary index ➔ Primary Key B-tree ➔ data fetch.
• Two full B-tree traversals!

Real-world Summary:

♦️ PostgreSQL

• Secondary index gives a direct shortcut to the heap.
• One B-tree scan (secondary) ➔ Direct heap fetch.

♦️ MySQL

• Secondary index gives PK.
• Then another B-tree scan (primary clustered) to find full row.

✅ PostgreSQL does not scan a second B-tree when fetching from the table — just a direct page lookup using TID.

✅ MySQL does scan a second B-tree (primary clustered index) when fetching full row after secondary lookup.

Is heap fetch a searching technique? Why is it faster than B-tree?

📚 Let’s start from the basics:

When PostgreSQL finds a match in a secondary index, what it gets is a TID.

♦️ A TID (Tuple ID) is a physical address made of:

• Block Number (page number)
• Offset Number (row slot inside the page)

Example:

TID = (block_number = 1583, offset = 7)

🔵 How PostgreSQL uses TID?

1. It directly calculates the location of the block (disk page) using block_number.
2. It reads that block (if not already in memory).
3. Inside that block, it finds the row at offset 7.

♦️ No search, no btree, no extra traversal — just:

• Find the page (via simple number addressing)
• Find the row slot

📈 Visual Example

Secondary index (username ➔ TID):

♦️ When you search for “Bob”:

• Find (1592, 3) from secondary index B-tree.
• Jump directly to Block 1592, Offset 3.
• Done ✅!

Answer:

• Heap fetch is NOT a search.
• It’s a direct address lookup (fixed number).
• Heap = unordered collection of pages.
• Pages = fixed-size blocks (usually 8 KB each).
• TID gives an exact GPS location inside heap — no searching required.

That’s why heap fetch is faster than another B-tree search:

• No binary search, no B-tree traversal needed.
• Only a simple disk/memory read + row offset jump.

🌿 B-tree vs 📁 Heap Fetch

🎯 Final and short answer:

♦️ In PostgreSQL, after finding the TID in the secondary index, the heap fetch is a direct, constant-time (O(1)) access — no B-tree needed!
♦️ This is faster than scanning another B-tree like in MySQL InnoDB.

🧩 Our exact question:

When we say:

Jump directly to Block 1592, Offset 3.

We are thinking:

• There are thousands of blocks.
• How can we directly jump to block 1592?
• Shouldn’t that be O(n) (linear time)?
• Shouldn’t there be some traversal?

🔵 Here’s the real truth:

• No traversal needed.
• No O(n) work.
• Accessing Block 1592 is O(1) — constant time.

📚 Why?

Because of how files, pages, and memory work inside a database.

When PostgreSQL stores a table (the “heap”), it saves it in a file on disk.
The file is just a long array of fixed-size pages.

• Each page = 8KB (default in Postgres).
• Each block = 1 page = fixed 8KB chunk.
• Block 0 is the first 8KB.
• Block 1 is next 8KB.
• Block 2 is next 8KB.
• …
• Block 1592 = (1592 × 8 KB) offset from the beginning.

✅ So block 1592 is simply located at 1592 × 8192 bytes offset from the start of the file.

✅ Operating systems (and PostgreSQL’s Buffer Manager) know exactly how to seek to that byte position without reading everything before it.

📈 Diagram (imagine the table file):

+-----------+-----------+-----------+-----------+-----------+------+
| Block 0   | Block 1   | Block 2   | Block 3   | Block 4   |  ... |
+-----------+-----------+-----------+-----------+-----------+------+
  (8KB)       (8KB)       (8KB)       (8KB)       (8KB)

Finding Block 1592 ➔
Seek directly to offset 1592 * 8192 bytes ➔
Read 8KB ➔
Find row at Offset 3 inside it.

🤔 What happens technically?

If in memory (shared buffers / page cache):

• PostgreSQL checks its buffer pool (shared memory).
• “Do I already have block 1592 cached?”
  • ✅ Yes: immediately access memory address.
  • ❌ No: Load block 1592 from disk into memory.

If from disk (rare if cached):

• File systems (ext4, xfs, etc) know how to seek to a byte offset in a file without reading previous parts.
• Seek to (block_number × 8192) bytes.
• Read exactly 8KB into memory.
• No need to scan the whole file linearly.

📊 Final Step: Inside the Block

Once the block is loaded:

• The block internally is structured like an array of tuples.
• Each tuple is placed into an offset slot.
• Offset 3 ➔ third tuple inside the block.

♦️ Again, this is just array lookup — no traversal, no O(n).

⚡ So to summarize:

🔥 Key concept:

PostgreSQL heap access is O(1) because the heap file is a flat sequence of fixed-size pages, and the TID gives exact coordinates.

🎯 Simple Real World Example:

Imagine you have a giant book (the table file).
Each page of the book is numbered (block number).

If someone says:

👉 “Go to page 1592.”

♦️ You don’t need to read pages 1 to 1591 first.
♦️ You just flip directly to page 1592.

📗 Same idea: no linear traversal, just positional lookup.

🧠 Deep thought:

Because blocks are fixed size and TID is known,
heap fetch is almost as fast as reading a small array.

(Actually faster than searching B-tree because B-tree needs multiple comparisons at each node.)

Enjoy SQL! 🚀