Storage, Keys, Query and Performance

Introduction

What is it? This chapter opens the box under the SQL you write. Until now we treated a table as "rows and columns". Here we learn how a storage engine (InnoDB, the default MySQL engine) physically stores those rows on disk, how it caches them in memory, how it writes changes safely, and how B+ tree indexes make lookups fast.

Why do we need it? Almost every performance rule you have seen has a storage reason behind it:

• "Keep the primary key short" comes from how secondary indexes store the primary key.
• "Too many indexes slow down writes" comes from how every insert touches every index.
• "Queries are fast when data is in memory" comes from pages and the buffer pool.
• "Indexes make range queries fast" comes from linked leaf pages.

When you know the storage model, these stop being rules to memorize and become things you can reason about.

Real-world analogy Think of a big library.

• A page is a bookshelf. The librarian never fetches a single sentence; she brings the whole shelf to the desk.
• The buffer pool is the reading table: shelves already on the table can be used at once.
• The clustered index is the library arranged by catalog number, with the full books on the shelves.
• A secondary index is an extra card catalog (by author, by topic). Each card only says "catalog number 4120". You then walk to that shelf for the full book.
• The redo log is the front-desk diary: every change is written in the diary before anything else, so after a power cut the staff can rebuild the shelves from the diary.

Business use case A company's orders table grows to 200 million rows. Reads are fast for hot customers, but inserts slow down and the disk fills up. The cause is a 36-character UUID primary key and eight secondary indexes: every index entry carries that long key, and every insert updates all nine B+ trees. This chapter explains exactly why, and what to do about it.

Dataset Used

This chapter is about internals, so it needs only one small example table, and a tiny set of rows for drawing B+ trees.

The example table (illustrative; the source describes it in words)

CREATE TABLE employees (
  id      INT PRIMARY KEY,
  email   VARCHAR(255) NOT NULL,
  country CHAR(2),
  dept    VARCHAR(50),
  ph_no   VARCHAR(20),
  UNIQUE KEY uq_email (email),
  KEY idx_country (country)
) ENGINE=InnoDB;

• id is the primary key.
• email has an index (unique here).
• country has an index.

The B+ tree walkthrough (section 12) uses 11 tiny records. Each record has a clustered key (the key the tree is ordered by) and two values:

The meaning of the two values does not matter. The clustered key matters.

Look at your own server (extra). These statements show the real numbers behind this chapter:

SELECT @@innodb_page_size;          -- 16384 bytes (16 KB) by default
SELECT @@innodb_file_per_table;     -- 1 = each table gets its own .ibd file
SELECT @@innodb_buffer_pool_size;   -- size of the page cache, in bytes
SELECT @@datadir;                   -- where the files live on disk

-- size of the clustered index (data) and of all secondary indexes, per table
SELECT table_name, data_length, index_length
FROM information_schema.tables
WHERE table_schema = 'tuf_sql';

-- how often a page was found in memory vs read from disk
SHOW GLOBAL STATUS LIKE 'Innodb_buffer_pool_read%';

1. Where Rows Actually Live

When beginners start learning databases, they often imagine that rows are stored one after another on disk in a very simple way, almost like lines written in a notebook. A mental picture usually looks like this:

 [row] [row] [row] [row] ...

This is a useful starting point for intuition, but it is not how a database actually stores and retrieves data. The real story is much more structured.

The common mental model

At first glance it feels natural to think:

• a table contains rows
• those rows are stored on disk
• when the database needs a row, it reads that row

This sounds simple, but disk systems do not usually work at the level of a single row. Databases are built on top of the operating system and storage hardware, and storage devices are optimized to read and write data in chunks, not tiny individual pieces. So although we logically think in rows, the engine physically works with something larger.

The database reality

 File  =>  Pages (fixed size)  =>  Records inside pages

A table is not stored as "just rows in a line". Instead:

• the table is represented as one or more files
• each file is broken into pages
• each page contains multiple records
• the database reads and writes these pages during I/O

So the true unit of storage and movement is the page, not the row.

 What you imagine                  What really exists

 [row][row][row][row]...           table file
                                   +---------+---------+---------+-----
                                   | Page 0  | Page 1  | Page 2  | ...
                                   | r r r r | r r r r | r r r r |
                                   +---------+---------+---------+-----

Why disk I/O does not happen one row at a time

Disk I/O is expensive compared to CPU and memory. So database engines work with fixed-size blocks, called pages. When the database needs one row, it usually does not fetch only that row. It loads the entire page that contains the row.

This has several advantages:

• fewer disk operations overall
• predictable storage organization
• better caching
• efficient scanning and indexing
• easier management of free space

From the engine's point of view, the page is the practical unit of reading, writing, caching, and managing data.

Example: InnoDB and the .ibd file

In MySQL's InnoDB engine, table data is often stored in a tablespace file such as employees.ibd. This file is not a flat list of rows. It is divided into pages:

 employees.ibd
 +--------+--------+--------+--------+-----
 | Page-0 | Page-1 | Page-2 | Page-3 | ...
 +--------+--------+--------+--------+-----

Each page has a fixed size, and records are stored inside the pages in InnoDB's internal format. The .ibd file stores:

• the table's actual row data
• the table's indexes

Page size in InnoDB

In InnoDB, the default page size is 16 KB. It can be configured (4 KB, 8 KB, 16 KB, 32 KB, or 64 KB), but only when the server is first initialized. The page size determines:

• how much data moves in one disk read or write
• how many rows fit in a page
• how index nodes are structured
• how buffering works in memory
• how efficiently scans and lookups happen

So when a row is accessed, the database often brings in an entire 16 KB page, not just the few bytes of that one row. As a rough feel: if a row is about 200 bytes, one page holds roughly 70 to 80 rows, so one disk read brings in dozens of neighbouring rows for free.

A page, simplified (extra)

 One 16 KB page (simplified)
 +--------------------------------------+
 | page header (what this page is)      |
 +--------------------------------------+
 | records, linked in key order         |
 |   rec  rec  rec  rec  rec ...        |
 +--------------------------------------+
 | free space (room to grow)            |
 +--------------------------------------+
 | page directory (for quick search)    |
 +--------------------------------------+
 | trailer (checksum)                   |
 +--------------------------------------+

Records live inside pages

A row is still very real logically: SQL queries operate on rows, return rows, filter rows, and join rows. But physically, rows are placed inside pages:

• rows do not live independently on disk
• they are packed into database pages
• page layout decides where records are placed
• page management affects insert, update, and delete behavior

So when someone asks, "Where does a row actually live?", the accurate answer is:

A row lives inside a page, and pages live inside the database file.

Pages exist on disk and in memory

Pages are not only stored on disk. They are also cached in memory. So InnoDB works with pages on disk and pages cached in memory. If a needed page is already in memory, the database can avoid disk access, which is much faster. The database is constantly moving pages between disk storage, the memory cache, and internal processing. Physically, the database is page-oriented, not row-oriented.

2. Pages Are Fixed-Size, Files Are Variable-Size

Once we know rows live in pages, a natural question is: are pages and files both fixed in size?

• Pages are fixed-size.
• Files are variable-size.

Fixed-size pages

InnoDB organizes storage around pages of a predefined size (16 KB by default). Whatever table or index you work with, the engine organizes data into page-sized blocks. The page size is decided by the storage engine settings, it does not change from row to row, and once chosen the engine manages storage using that unit. Because it is configurable, we can call it "fixed-ish". This design lets the engine predict how data is laid out, how much fits in memory, and how disk I/O should happen.

Files grow with data

A database file, such as an InnoDB tablespace file, is not fixed in size. It grows as more data is inserted, more indexes are created, and more internal bookkeeping is needed. Examples of variable-size structures:

• .ibd tablespace files
• redo log capacity
• undo and internal storage structures

So each page stays 16 KB, but the number of pages in a file increases over time.

 A page is one standard brick.  A file is the whole building.

 brick size never changes  ->  [16 KB]
 building grows with bricks ->  [16][16][16][16][16][16] ... more added over time

Memory effect: how many pages can be cached

Because the database works in pages, memory is used to cache pages. The practical question is not "how much memory does the machine have?" but "how many pages can fit in memory?"

More memory means more cached pages, fewer disk reads, and faster performance.

Disk effect: how fast pages can be read or written

The database does not say "read one row from disk". It says "read this page" or "write this page back". So disk speed controls:

• how quickly pages can be read
• how quickly dirty pages can be flushed
• how efficiently scans and index traversals happen

In a page-based engine, disk performance is essentially the speed of moving pages in and out of storage.

3. What If a Record Becomes Too Large?

Pages are fixed-size, so a row cannot grow forever inside one page. The database handles an oversized record differently depending on the type of data.

Case 1: Mostly TEXT, BLOB, or large VARCHAR

Depending on the InnoDB row format, page size, column type, and value size, InnoDB can move part of large variable-length fields (TEXT, BLOB, and some VARCHAR values) to overflow pages. The whole long value is not stored inside the main page. Instead:

• the main record keeps the essential in-page part
• the large external portion is stored elsewhere
• the record keeps a reference (a pointer) to the overflow storage

 Main page                                 Overflow pages
 +-------------------------------+         +-------------+   +-------------+
 | id | name | ... | [pointer] ----+-------> | big text    |-->| more text   |
 +-------------------------------+         +-------------+   +-------------+
  the "core row body" stays here            oversized content lives here

This keeps the row manageable while still supporting large column values. It is how large text-heavy rows are usually handled.

Case 2: Mostly fixed-size columns

If the row is made mostly of fixed-size columns and the total row structure becomes too large, the engine has much less flexibility. Fixed-size data cannot be moved off-page the way large TEXT or BLOB data can. MySQL may then raise:

 Error 1118 - Row size too large

This happens because the row format cannot be organized within the allowed limits of the page structure.

A practical takeaway: a row that stays small keeps more rows per page, which means fewer page reads for the same data.

4. Disk Hierarchy in InnoDB: How Files Are Organized

We know InnoDB works with pages. Where do these pages live on disk? In InnoDB, tables and indexes live inside a tablespace, and a tablespace is made of pages.

 Disk => data directory => database folder => tablespace files => pages => records / index data

When you create a table, InnoDB is not storing a list of rows somewhere. It creates and manages structured files, and inside those files, data is organized page by page.

The disk layout

 Disk
 └── data dir/
     ├── db/
     │   ├── employees.ibd
     │   └── ...
     ├── ibdata1
     └── redo logs

Data directory. The main location where MySQL keeps database files. If someone asks "where is the physical storage?", the first broad answer is: inside the data directory (SELECT @@datadir; shows it).

Database folder. Inside the data directory, each database (schema) usually has its own folder, for example data dir/db/.

File per table. With the file-per-table approach (the default), every table gets its own .ibd file:

One table corresponds to one .ibd file. With 100 tables, you may have 100 such files.

ibdata1. This is the system tablespace: a shared InnoDB area for system-level information and internal storage work. For this mental model it is enough to know:

• .ibd files are generally table-specific
• ibdata1 is system-level, shared storage

(In MySQL 8, some things that used to sit in ibdata1, such as undo logs, can live in their own files.)

Redo logs. Redo logs are not table data files. Their purpose is durability: they help InnoDB remember changes so that after a crash, committed work can be recovered.

• .ibd stores the page-based data and index structures
• redo logs store the record of changes needed for recovery

5. What Is Inside employees.ibd?

Take the example table employees(id, email, country, dept, ph_no), where id is the primary key, email has an index, and maybe country has an index too.

Even though logically this is one table, physically InnoDB organizes its data into different page-based structures, depending on how the table is indexed.

Clustered index

In InnoDB, the table's main data is stored using the clustered index. By default, the clustered index is based on the primary key. If id is the primary key, the actual row data is physically organized by id. The table data is not stored in a separate raw heap and indexed later. The main row storage is the primary-key structure.

 id1 => record1
 id2 => record2
 id3 => record3

What the file contains

employees.ibd is a collection of pages that serve several purposes:

 employees.ibd
 +---------------------------+------------------------+-----------------+
 | clustered index pages     | secondary index pages  | free / allocated|
 | (ordered by id,           | (by email, by country) | pages           |
 |  FULL rows)               |                        |                 |
 +---------------------------+------------------------+-----------------+

Clustered-index pages. These store data in primary-key order, with the full row:

 page 0: records ordered by id (1, 2, 3, ...)
 page 1: the next set of records
 page 2: more records

So the table's actual data pages are primarily the clustered index pages.

Secondary index pages. If we create an index on email, InnoDB needs another page-based structure organized by email. Another set of pages appears in the same .ibd file. An index on country adds another set. So one file can hold:

• one structure organized by id
• one structure organized by email
• one structure organized by country

The more indexes you have, the more physical structures must be stored and maintained.

Free and allocated pages. Some pages are in use, some are reserved for future growth, and some are free and ready to be reused. Not every page must hold active data. Storage engines always keep some internal management space to make growth efficient.

Where are B+ trees stored?

B+ trees are stored in pages inside the .ibd file. A B+ tree is not an abstract object floating separately from the file system. Its nodes are pages.

• the clustered index is a B+ tree stored in pages
• the secondary index on email is another B+ tree stored in pages
• the secondary index on country is another B+ tree stored in pages

When we say "InnoDB uses B+ trees", physically it means: InnoDB stores B+ tree nodes inside pages, and those pages live inside files like employees.ibd.

6. Why Databases Feel Fast

A common beginner question: if data is stored on disk, and disk is slow compared to memory, why do databases feel fast?

InnoDB serves queries from RAM pages whenever possible.

The database is fast not because disk is fast, but because it works very hard to avoid disk access again and again.

The core read principle

InnoDB does not read one individual row from disk. It reads pages. So if a query needs a record, InnoDB first finds which page contains it, and then asks: can I get that page from RAM, or do I have to go to disk?

The example

A query wants rows R1, R3, and R5. On disk:

• Page P-0 contains R1 and R3
• Page P-1 contains R5

The rows are spread across two pages. The database first checks the buffer pool in RAM.

What is the buffer pool?

The buffer pool is InnoDB's main memory area where pages are cached. It keeps frequently used pages so future reads can avoid going back to disk. It is page-based caching, not row-based caching: if a page is useful, InnoDB keeps the whole page in RAM.

 Query needs R1, R3, R5
        |
        v
 Check the buffer pool (RAM) for P-0 and P-1
        |
   +----+---------------------------+
   |                                |
  HIT                              MISS
 (both pages in RAM)       (page not in RAM)
   |                                |
 use the pages now         read the 16 KB page(s) from disk
 no disk access            put them in the buffer pool
   |                                |
   +---------------+----------------+
                   v
        extract R1, R3, R5 and answer

If it is a hit. The pages are already in memory, InnoDB uses them directly, no disk is touched. This is called a buffer pool hit (cache hit), the best case.

If it is a miss. InnoDB must go to disk. Again, disk does not return individual rows, it returns pages. To get R1, R3, R5 it reads P-0 and P-1: two 16 KB pages. They are placed in the buffer pool, and only then does the database use them.

Why future queries become faster

Once P-0 and P-1 are in RAM, they may stay cached for some time. If the same query (or a similar one needing rows from these pages) comes again, InnoDB uses the cached pages with no disk trip. The first access may need disk I/O; later accesses may be served from RAM.

Hot pages

Some pages are needed again and again: popular users, recent orders, current session data, frequently searched products, and index pages near the top of a B+ tree. These become hot pages, and InnoDB tries to keep them in the buffer pool. That is why hot workloads feel much faster than cold ones.

Pages cannot stay forever

RAM is limited. The database cannot keep every page forever. InnoDB uses cache management strategies (a variation of "least recently used") to decide what stays cached, what is removed, and which old pages newly read pages replace. The exact algorithm is deeper, but the idea is simple: keep useful pages in RAM and remove less useful ones when space is needed. The buffer pool keeps changing with the workload.

Measuring it (extra)

SHOW GLOBAL STATUS LIKE 'Innodb_buffer_pool_read%';

Hit ratio = 1 - (reads / read_requests). For example, 1,000,000 requests with 5,000 disk reads is a 99.5% hit ratio. A falling ratio means the working set no longer fits in memory.

7. How Does InnoDB Choose the Clustering Key?

The clustered index decides how the main table data is physically organized, so this choice matters. InnoDB follows a clear order.

 Does the table have a PRIMARY KEY?
    |
   yes --> use it                                        (Rule 1)
    |
    no
    |
 Is there a UNIQUE index where every column is NOT NULL?
    |
   yes --> use the first such index                      (Rule 2)
    |
    no
    |
 Create a hidden 6-byte key: DB_ROW_ID  and use that     (Rule 3)

Rule 1: Use the primary key

If the table has a primary key, InnoDB uses it as the clustering key. This is the default and most common case. If id is the primary key, rows are physically organized by id, and the clustered index is built on id with the full row stored in it. This is the ideal scenario, because the clustering key is explicit and controlled by the table design.

Rule 2: Use the first unique NOT NULL column

If there is no primary key, InnoDB looks for the first unique index whose columns are all NOT NULL. Suppose the table has no primary key, but email is UNIQUE and NOT NULL. InnoDB may use email as the clustering key, and rows are physically organized by email. Even without an explicit primary key, InnoDB tries to find a stable unique identifier.

Rule 3: Create a hidden synthetic key

If neither exists, InnoDB creates its own hidden clustered key: a synthetic 6-byte internal value called DB_ROW_ID. It is an internal row identifier used only so that InnoDB can still build a clustered index. It is not a user-defined column, and you cannot use it in your queries.

Why this matters. Always define a primary key yourself. Otherwise the clustering key is either an accident of which unique column came first, or a hidden key you can never use for lookups.

8. Write Flow in InnoDB: Insert, Update, Delete

So far we built intuition for reading. Now: what happens when the database changes data (INSERT, UPDATE, DELETE)?

InnoDB is memory-first and disk-later.

Memory first, disk later

Many beginners imagine: the query comes, the database immediately updates the disk, then the query completes. That is not the full picture. InnoDB does not usually rewrite the main table file for every write while you wait. The flow is:

1. bring the relevant pages into RAM if needed
2. modify those pages in RAM
3. mark them as dirty
4. record the change in the redo log
5. commit
6. flush dirty pages to disk later, in the background

 query --> pages in RAM changed (dirty) --> redo log flushed --> COMMIT returns
                                                  |
                               later, in the background: dirty pages written to .ibd

Step 1: Identify the relevant rows and pages

Suppose a query modifies R1, R3, and R5, where R1 and R3 are in page P-0, and R5 is in page P-1. InnoDB works with pages P-0 and P-1, not with isolated rows on disk.

Step 2: Check the buffer pool

The first step is the same as in a read: does the buffer pool already hold the required pages?

• hit: use the pages already in RAM
• miss: read the pages from disk into RAM first

Every write first needs the right pages in the buffer pool.

Step 3: Modify the pages in RAM

Once the pages are in memory, InnoDB applies the update, delete, or insert in RAM. Call the old version on disk V1. After the change, the memory copy is V2:

• disk still has V1
• RAM has the newer V2

Memory is now ahead of disk.

What is a dirty page?

A dirty page is a page in memory whose contents are newer than the copy stored on disk. If P-0 in RAM has been updated but P-0 on disk still has the old data, the RAM page is dirty. It has changes that have not yet been written back to the main data file.

Step 4: Append a redo log record

After modifying the page in memory, InnoDB records the change in the redo log. A simple way to think of it: documentation of what change was done. It contains enough information to replay the change later if needed. This protects the system from losing committed changes in a crash. Even if the main data page has not been written to the .ibd file yet, the change is documented in the redo flow.

Step 5: Commit

At COMMIT, the critical guarantee is not "the main .ibd pages have been rewritten". With the fully durable innodb_flush_log_at_trx_commit=1 setting and reliable storage flushes, the redo information for the committed change is flushed before success is returned. Other settings or storage that does not honor flushes weaken that guarantee.

So the commit can complete before the dirty data pages are written back to the table file. That is why the system can be both fast and durable.

Step 6: The redo log is flushed

At commit the redo log is flushed, so the change is safely documented on disk. After commit:

• the redo log has the durable record of the change
• RAM has dirty pages with the newer version
• the main data file may still temporarily have the old version

This is normal. A query can be committed even though the main page write to .ibd may happen later, because durability is protected by the redo log.

(The setting innodb_flush_log_at_trx_commit controls this. The default, 1, flushes the redo log at every commit, which is the fully durable choice. Other values trade some durability for speed.)

Step 7: Background flush writes dirty pages later

At some later time, a background process writes the dirty pages from RAM back to the .ibd file. The disk page moves from V1 to V2, and the main data file catches up with what was already in memory. This is called flushing dirty pages. Redo space becomes reusable as checkpoint progress advances beyond the relevant log records; flushing dirty pages enables that checkpoint progress, but one page flush alone is not the reuse boundary.

 time --->

 write arrives:   disk P-0 = V1        RAM P-0 = V1
 modify in RAM:   disk P-0 = V1        RAM P-0 = V2  (dirty)
 redo appended:   redo log: "P-0: change V1->V2"
 COMMIT:          redo log flushed to disk   <-- commit is safe here
 ...later...
 background:      disk P-0 = V2        RAM P-0 = V2  (clean)

The important crash scenario

What if the system crashes after commit but before the dirty pages were flushed to .ibd? This is exactly what redo logs are for.

• RAM had updated pages (V2)
• disk still had V1
• the redo log had already been flushed at commit
• then the machine crashed

RAM is gone, so the dirty pages are lost. But the redo log is on disk. On restart, InnoDB reads the redo log, sees the committed changes, and replays them, bringing the data back to the correct latest version.

 crash!  RAM lost         disk: page = V1        redo log: "V1->V2" (committed)
                                     |
 restart: InnoDB replays the redo log  --> page = V2   (committed change is NOT lost)

Why data is not lost after commit. A committed change is not safe because the .ibd page was rewritten. It is safe because the redo log was durably flushed. After a crash, the RAM copy may be gone and the main data page may still be old, but the redo log lets recovery rebuild the committed state.

What happens to reads after the update?

Suppose the update is done in RAM, the page is dirty, and the background flush has not happened. Another query wants to read that row. InnoDB reads the needed page version through the buffer pool, but buffer residency is separate from transaction visibility. MVCC and the transaction's isolation level determine which committed row version a reader can see; an existing snapshot may continue to see an older version even while a newer page is resident in memory. (This is another reason RAM is so central.)

Read flow vs write flow

The write flow starts like the read flow, then adds dirty pages, redo logging, commit handling, and background flush.

9. If Pages Were Stored Linearly, How Much Would Operations Cost?

Let us start with the simplest idea, without knowing anything about B+ trees. We have a file like employees.ibd with many pages, and only the clustered index exists, so records are in primary-key order:

 id1 => record1
 id2 => record2
 id3 => record3

Suppose each page holds only 4 records (real pages hold many more, but a small number makes the logic easy to see). The brute-force idea is to chain the pages one after another:

 P0 => P1 => P2 => P3

Now let us see how expensive operations become.

Insert

To insert a record with key id15, we start at the first page and check: does P0 have space? If not, P1? If not, P2? Eventually we find a page with room and insert the record in sorted order. In the worst case we scan through all the relevant pages. The cost is roughly O(N), where N is the amount of data or pages scanned.

Someone could say "remember the last free page". That is an optimization on top, not a fundamental solution. The linear model still does not scale.

Update

To update the record with id12, the only brute-force way is to begin at the first page and keep scanning (page 0, page 1, page 2, ...) until the record is found. In the worst case, it is near the end. So lookup for an update is also O(N). A separate hash map from key to page could speed up the lookup, but then you pay extra space and extra maintenance. The linear page organization alone is not enough.

Delete

To delete id11, we first find it, which can take O(N). After deletion there is another issue: the data is meant to stay logically ordered by the clustering key, so a gap must be handled carefully. Delete is not just "find and erase". You also preserve the sorted structure and page organization. Overall delete also has a brute-force flavour of O(N).

Range scan

Suppose we want records from R12 to R14, or from some lower bound L to an upper bound R.

• First we may have to scan through the structure to locate where the lower bound starts: O(N).
• Then we iterate through the matching records. If the range has R - L + 1 records, this costs O(R - L + 1).

Total: O(N) + O(R - L + 1). The range itself is cheap to read. The expensive part is the long scan just to reach the start of the range.

Why linear storage fails as a core design

A database with huge files and many pages cannot rely on this. Some cases can be patched with hash maps or extra bookkeeping, but you keep adding side structures. What we want is a structure that is:

• page-friendly
• balanced
• efficient for equality lookups
• efficient for range scans
• efficient without full linear scans

That is exactly where the B-tree family comes in.

10. The B-Tree Family and B+ Trees

At a broad level, a B-tree is a family of balanced, multi-way search trees designed for page-based storage.

Balanced. The tree is structured so that no branch becomes extremely long while another stays short. If one path became too deep, some lookups would be much slower than others. Balanced trees keep access costs predictable, which is exactly what a database wants.

Multi-way. A binary tree allows at most two children per node. Databases work with pages, and a page can hold many keys. So database index structures are multi-way: one node guides us to many children. That makes the tree much shorter in height, and shorter height means fewer page reads.

 Binary tree node:   2 children            B-tree node (one page):  hundreds of children

        [k]                                   [k1|k2|k3| ... |k500]
       /   \                                 /  |   |   |       \
                                          many children, one page read

What is a B+ tree?

A B+ tree is a variant in the B-tree family, with three important characteristics.

1. Internal nodes are for navigation. The internal nodes act like routing layers. They tell us which branch to follow, but they are not where the full entries are stored. Their job is to compare keys, decide direction, and move us downward efficiently.

2. Actual entries live in the leaf pages. When you finally look for the actual stored records (or index entries), you land in the leaf level. The upper levels guide you, and the leaf level stores the real entries.

3. Leaf pages are linked. The leaf pages are typically linked to each other in order. Once you find the first matching key of a range scan, you can continue through the neighbouring leaf pages. For queries like:

WHERE id BETWEEN 100 AND 500
WHERE email >= 'a' AND email < 'f'

you do not restart from the root for every next record. You reach the starting point once, then walk through the linked leaves. That is why B+ trees are so strong for range scans.

                     [ root: navigation only ]
                      /          |           \
            [ internal ]    [ internal ]    [ internal ]      <- navigation only
            /    |    \      /   |   \       /   |   \
        [leaf]<->[leaf]<->[leaf]<->[leaf]<->[leaf]<->[leaf]   <- real entries, linked

Why the tree stays so shallow (extra)

Each level costs about one page read. Because one page holds many keys, the fan-out (children per node) is large, often around a thousand for a compact key. As a rough feel, with a fan-out near 1000, three levels can address around a billion entries, and the top levels are almost always cached in the buffer pool. So finding one row in a huge table typically costs only one or two real disk reads.

Why people say "B-tree index" even for B+ trees

In many discussions vendors casually say "B-tree index". At a generic level, B-tree is the broader family name. But in real systems, the implementation is often very close to a B+ tree, sometimes with engine-specific changes, because it works extremely well for:

• equality lookups
• ordered traversal
• range scans
• page-based organization

So "B-tree index" is a practical umbrella term, while the real internal behaviour is usually closer to a B+ tree.

Why different databases tune the structure

Different databases have different goals: some optimize writes, some analytical scans, some concurrency, some compression, some storage layout. So real systems tune and extend the B+ tree idea. The first-principles foundation stays the same:

• navigation through internal nodes
• real entries in leaves
• linked leaves for range access
• page-aware, balanced structure

11. What Happens When You Add an Index?

Suppose the table is stored in employees.ibd. By default it already has its clustered index, organized by the clustering key (primary key, first unique NOT NULL column, or hidden DB_ROW_ID). Now you add another index, for example:

• an index on email
• an index on country
• a composite index on (email, country)

New secondary index structures are created. Each gets its own page-organized, B+ tree-like structure inside the same tablespace file. After adding these indexes, employees.ibd may contain:

• clustered index pages
• secondary index pages for email
• secondary index pages for country
• secondary index pages for (email, country)

Adding an index does not replace the clustered index. It adds another organized access path.

The clustered index stays untouched

The base table organization does not disappear. The database creates more pages for the new index:

• the original clustered pages still exist
• new pages are allocated for each extra index

That is why indexes improve read performance, but also consume more space and make writes more expensive. Every additional index is another structure that must be maintained.

Secondary index = another key organization

Each lives in its own page set, usually as a B+ tree-like structure.

A composite index is a separate structure too

Even if you already have an index on email and an index on country, creating (email, country) creates another separate structure, because (email, country) is a different ordered key arrangement. Composite indexes are not "automatically covered" just because single-column indexes exist. Each one is its own storage path.

12. Building a B+ Tree with Data

Let us build a B+ tree by hand using the 11 tiny records from the dataset section.

The setup

We assume the worst case for keys: there is no primary key, and no unique non-null column. So InnoDB uses the hidden key DB_ROW_ID as the clustering key. For convenience, we use simple labels as the clustered keys: 1, 2, 3, ..., 10, and 0 for the last record.

(A real hidden row id only ever grows, so a real later row would never get 0. The label 0 is a teaching device, used at the end to show an insert that goes to the far left.)

The tree is built ordered by the clustered key, and the actual row data is stored alongside it in the leaf pages.

Real pages hold many entries. To see splits quickly, this walkthrough assumes:

• a leaf page holds at most 3 records
• an internal page holds at most 3 keys

The important structural moments are leaf overflow, page split, parent creation, internal-node growth, and root split.

Split rules used

• A full leaf that gets one more record splits into two sorted leaves. The first key of the right leaf is copied up into the parent as a separator.
• A full internal node that gets one more key splits into two. The middle key moves up (it is not kept in the children).
• If the root splits, a new root is created, and the tree grows one level taller.

Step 1: Start inserting into a single leaf page

The tree is empty. The first inserts go into the first leaf.

 insert 1 => (101, 30)
 insert 2 => (102, 40)
 insert 3 => (103, 5)

 [ 1 | 2 | 3 ]          one leaf, no parent needed yet

Leaf capacity is 3, so all three fit. There is no need for a parent or internal node. The tree is a single leaf.

Step 2: Insert the 4th entry and trigger the first split

Insert 4 => (104, 6). The leaf is full (capacity 3), so inserting the 4th entry causes an overflow. A B+ tree splits the leaf into two sorted leaf pages:

 Left leaf:  1, 2          Right leaf:  3, 4

Now there is more than one leaf, so we need a way to navigate between them. The first parent (the root) appears, holding the separator key 3:

• anything less than 3 is found in the left child
• anything greater than or equal to 3 is found in the right child

        [ 3 ]
       /     \
 [ 1 | 2 ]   [ 3 | 4 ]

The tree grew from one leaf page to one internal root with two leaf children. This is the first time the tree shape is visible.

Step 3: Insert 5 and 6

Insert 5. Compare with root separator 3. Since 5 >= 3, go to the right leaf [3, 4]. It has room, so:

        [ 3 ]
       /     \
 [ 1 | 2 ]   [ 3 | 4 | 5 ]

Insert 6. 6 >= 3, so the right leaf again. It is full (3, 4, 5), so inserting 6 causes another leaf overflow. The leaf splits in sorted order:

 Middle leaf: 3, 4         New right leaf: 5, 6

The new right leaf begins with 5, so the separator 5 goes into the parent. The parent becomes 3, 5:

            [ 3 | 5 ]
           /    |    \
   [ 1 | 2 ] [ 3 | 4 ] [ 5 | 6 ]

Routing now: keys < 3 go to the left leaf; keys >= 3 and < 5 go to the middle leaf; keys >= 5 go to the right leaf.

Step 4: Insert 7 and 8

Insert 7. From separators 3, 5: 7 >= 5, so go to the rightmost leaf [5, 6]. It has room: [5, 6, 7].

Insert 8. The rightmost leaf is full, so it splits in sorted order:

 Left part: 5, 6         Right part: 7, 8

The new right leaf starts with 7, so separator 7 goes up. The parent becomes 3, 5, 7:

                [ 3 | 5 | 7 ]
               /    |    |    \
        [ 1 | 2 ] [ 3 | 4 ] [ 5 | 6 ] [ 7 | 8 ]

Every split preserves sorted order, and every parent key helps future searches.

Step 5: Insert 9 and 10 (the root overflows)

Insert 9. Root separators 3, 5, 7, so 9 >= 7: go to the rightmost leaf [7, 8]. It has room: [7, 8, 9].

Insert 10. The rightmost leaf is full, so it splits:

 Left: 7, 8         Right: 9, 10

The parent must receive separator 9. But the parent currently holds 3, 5, 7. Adding 9 would make it 3, 5, 7, 9, which is too many keys. The parent itself overflows:

        [ 3 | 5 | 7 | 9 ]      <-- too many keys (capacity is 3)

So the overflow has propagated upward:

• leaf overflow may force a parent insertion
• a parent insertion may overflow the parent
• that forces an internal-node split
• if the root overflows, the tree height increases

The internal node splits. The middle key 7 moves up into a brand-new root. The left internal node keeps 3, 5, and the right internal node keeps 9:

                      [ 7 ]                       <- new root
                   /           \
           [ 3 | 5 ]             [ 9 ]            <- internal nodes
          /    |     \          /      \
   [ 1 | 2 ] [ 3 | 4 ] [ 5 | 6 ]  [ 7 | 8 ] [ 9 | 10 ]    <- leaves

The tree height has grown by one level, and all leaves are still at the same depth. Even with more records, the tree stays shallow. That is one of the greatest strengths of B+ trees.

(Note on the original notes: they show the right internal node as 7, 9. The pushed-up key 7 is not repeated in the child, and that right node has only two leaves below it, so it needs just the one key 9.)

Step 6: Insert 0

Insert 0 => (111, 2). How do we find its place?

• Root [7]: 0 < 7, so go left.
• Left internal [3 | 5]: 0 < 3, so go to the leftmost leaf.
• The leftmost leaf [1, 2] has room: it becomes [0, 1, 2].

                      [ 7 ]
                   /           \
           [ 3 | 5 ]             [ 9 ]
          /    |     \          /      \
  [0 | 1 | 2] [3 | 4] [5 | 6]  [7 | 8] [9 | 10]

Instead of scanning a chain of pages, we followed only a few routing decisions. Even with growing data, search and insertion stay guided by a small number of steps.

The finished tree

Height: 3 levels. Every lookup visits exactly 3 pages (root, one internal, one leaf).

13. Performing Operations on the B+ Tree

Now that the structure is built, let us see how common operations work.

Search

Search for key 6:

1. Start at the root [7]: 6 < 7, go left.
2. Internal [3 | 5]: 6 >= 5, go to the third child.
3. Leaf [5 | 6]: do a small local search and find 6 => (106, 30).

 [7] --(6 < 7)--> [3|5] --(6 >= 5)--> [5|6] --> found 6

Instead of a full scan, we follow a short path through a shallow tree. Search cost depends on the tree height, not on the number of records.

Range scan

Get all keys from 2 to 6:

1. Search for 2 like a normal point lookup: root, internal [3 | 5], leaf [0 | 1 | 2].
2. Read 2. Do not go back to the root for 3, 4, 5, and so on. Because leaves are linked, follow the link to [3 | 4], read 3 and 4.
3. Follow the link to [5 | 6], read 5 and 6.
4. The next key (7) is beyond the range, so stop.

 search down to the start:  [7] -> [3|5] -> [0|1|2]
 then walk sideways:        [0|1|2] -> [3|4] -> [5|6]   (stop: next key is 7)

The cost is: the search to reach the start of the range, plus the sequential walk through the range entries. That is why B+ trees are excellent for ordered and range-based access, not only equality lookup.

Insert

The logic is what we just did:

1. navigate to the correct leaf
2. insert in sorted order
3. if the leaf overflows, split it
4. push the separator to the parent
5. if the parent overflows, split the parent
6. continue upward if needed
7. if the root overflows, create a new root

Insert stays efficient because the tree stays balanced and shallow.

Delete

Delete works similarly in spirit. First locate the key by searching down the tree, then remove it from the leaf. If the deletion affects separator logic or makes a page too empty (underflow), the tree may rebalance (borrow from or merge with a neighbour) or update separators. InnoDB typically marks the record as deleted first, and a background purge cleans it up later.

Update

Update is simple conceptually: search for the key, locate the entry, modify the value or record. So update is search + local modification. If the update changes an indexed column, it is handled like a delete of the old index entry plus an insert of the new one in that index. The expensive full scan is avoided.

Cost summary

Here R - L + 1 is the number of matching records, and the tree height grows very slowly (logarithmically) as data grows.

14. How a Unique Constraint Is Enforced

Suppose a column email is declared UNIQUE. How does the database enforce it? The answer is: an index-backed lookup plus concurrency-safe enforcement.

1. Lookup through an index

For a unique column, the database creates or uses an index on it. For email UNIQUE, there is a B+ tree-like secondary index on email. Before inserting a new email, the database can search that index quickly and check: does this email already exist? Without the index, uniqueness checking would need an expensive scan. So enforcement starts with a fast lookup.

2. Concurrency-safe enforcement

Lookup alone is not enough. Two transactions may insert the same email at almost the same time:

 Query 1: check for jai@gmail.com  -> not found
 Query 2: check for jai@gmail.com  -> not found     (before Query 1 finished inserting)
 Query 1: insert jai@gmail.com
 Query 2: insert jai@gmail.com      <- would break uniqueness!

If the system used a careless "check then insert", both could insert the value. So the storage engine and its transactional machinery (locking on the index records) guarantee that only one insert succeeds, and the conflicting one waits and is then rejected with a duplicate-key error (error 1062).

The full answer: lookup + concurrency-safe enforcement.

Practical consequence. Do not enforce uniqueness only by "SELECT, then INSERT if not found" in application code. Put a UNIQUE constraint in the database, and handle the duplicate-key error (or use INSERT ... ON DUPLICATE KEY UPDATE, from the JSON notes).

15. Why a Wrong Primary Key Can Quietly Destroy You

To see why the primary key matters so much, we must be clear about what is stored in the clustered index and what is stored in secondary indexes.

The clustered index stores the full row

In InnoDB, the clustered index is a B+ tree whose key is the clustering key (primary key, first unique NOT NULL column, or hidden row id; in a good design, simply the primary key). The crucial part:

the leaf level of the clustered index contains the full row.

For employees(id, email, country, ph_no) with id as the primary key, the clustered index is organized by id, and the leaf pages store the complete record:

 id1 => full row R1
 id2 => full row R2
 id3 => full row R3

The clustered index leaf level is not just "an index". It is the table data itself.

A secondary index does not store the full row

Suppose we also create an index on email. A common beginner assumption is "the email index stores email => full row". In InnoDB, that is not how it works. The leaf level of a secondary index stores its secondary key plus the clustered primary-key columns needed to identify the row; clustered-key columns already present in the secondary key are not redundantly duplicated:

 (secondary key, needed clustered-primary-key columns)

So the email index is conceptually:

 email1 => id1
 email2 => id2
 email3 => id3

Not email1 => full row. The full row exists only once, in the clustered index. Secondary indexes store just enough to find the row later.

The lookup path

SELECT *
FROM employees
WHERE email = 'a@example.com';

The database does not get the full record directly from the secondary index leaf. The path is:

 secondary index (email)  =>  clustered index (id)  =>  full row

 1. search the B+ tree on email
 2. find the matching secondary-index entry  (email -> id)
 3. extract the primary key (id)
 4. search the clustered index with that id
 5. fetch the full row from the clustered-index leaf

This is often called a double lookup (secondary-to-clustered lookup).

Why InnoDB designs it this way

"Why not store the full record in every index, so there is no second lookup?" It sounds tempting, but it would be a bad design, for two reasons.

1. The primary key is the stable address of the row. The clustered index stores the full row once, as the single source of truth. If every secondary index stored full copies, every row would be duplicated again and again across indexes, which is extremely wasteful. So InnoDB stores the full row once, and lets secondary indexes point to it with the clustered key.

2. Updates would become chaotic. If a row were duplicated in the clustered index, the email index, the country index, the phone index, and a composite index, then updating one row would mean updating many full-row copies across many B+ trees. That creates:

• more storage waste
• more write amplification
• more redo logging
• more complexity
• more chances of stale copies and inconsistency

Instead, secondary indexes store secondary key + primary key, so the database avoids maintaining many copies of the full row.

When do we NOT need the clustered index? (Covering index)

SELECT id
FROM employees
WHERE email = 'a@example.com';

The query needs email (to search) and id (to return). The email index already stores (email, id). After searching the secondary index, the database already has the answer. There is no need to go to the clustered index. The query is answered entirely from the secondary index. This is a covering index situation: the index "covers" all the data the query needs. (In EXPLAIN, you see Using index in the Extra column.)

Why the primary key becomes so important

If every secondary index stores (secondary key, primary key), then the primary key is not stored just once. It is copied into every secondary index entry. So the size of the primary key matters much more than most people realize.

Real implication 1: a wide primary key makes every secondary index bigger

And this is multiplied by the number of rows and the number of secondary indexes.

A worked estimate (extra). Take 10 million rows and 3 secondary indexes, counting only the copied primary key:

The wide key makes the secondary indexes about four and a half times heavier, before counting page overhead. The consequences:

• fewer entries fit per page
• B+ trees become wider and deeper faster
• more pages are needed
• cache efficiency drops
• disk I/O increases

And all of this can happen silently over time.

Another cost of random keys (extra). A random UUID as the primary key inserts rows in random places of the clustered B+ tree, which causes many page splits and cache misses. An auto-increment key always inserts at the right edge of the tree (like inserting 9 and 10 in the walkthrough). If you need UUIDs, store them compactly (for example BINARY(16) in MySQL 8; the swap flag in UUID_TO_BIN(uuid, 1) is specifically useful for time-part reordering of version 1 UUIDs) or use time-ordered ids.

Real implication 2: more indexes mean slower writes

Whenever a new row is inserted, the database must add an entry in the clustered index and in every secondary index. With:

• a clustered index on id
• a secondary index on email
• a secondary index on country
• a secondary index on phone
• a composite index on (country, email)

every insert must update all five structures. The more indexes you define, the more places each write must touch. More indexes = slower writes. This is an unavoidable tradeoff: indexes help reads, but make writes heavier. And because each secondary index entry includes the primary key, the cost is worse when the primary key is wide. A bad primary key choice combines badly with too many indexes.

 One INSERT into a table with a clustered index and 4 secondary indexes

 INSERT --> clustered index  (full row)
        --> index on email    (email, id)
        --> index on country  (country, id)
        --> index on phone    (phone, id)
        --> index on (country, email)   (country, email, id)

 five B+ trees changed, five sets of redo records, five chances of a page split

A good primary key is

• short (an integer type is ideal)
• stable (never changes)
• increasing (inserts land at the right edge)
• meaningless (a surrogate key, as in the Day 35 notes)

16. Index Strategy at Scale

1. What happens when you add indexes?

The first principle: indexes help reads, but indexes tax writes. Whenever you add an index, you add another structure that the database must maintain. Reads that use it may become much faster, but every insert, update, or delete may now need to touch one more B+ tree. Indexing is not free acceleration.

Why reads improve. If a query can use an index, the database avoids scanning too many rows. It navigates a B+ tree and reaches the target rows efficiently.

Why writes slow down. A new row must always be inserted into the clustered index, and a new entry must be inserted into every relevant secondary index. With a clustered index plus four secondary indexes, one insert is no longer "one insert". It is one clustered-index write plus several secondary-index writes.

2. What happens when you add a new index to existing production data?

Suppose the table already has millions of rows and you decide "I need a new index on country". Adding an index to an existing large table is not just a metadata change. The database must build the index from the data already present:

1. scan the existing table data to get the indexed key values
2. pair each indexed value with the clustered key / primary key
3. sort the keys
4. build the B+ tree for the new index

 existing table (millions of rows)
        |
   scan --> (country, id) pairs --> sort --> build new B+ tree
        |
   real work: CPU, memory, disk I/O  (and time)

This is a substantial operation. It is not instantaneous, and on a very large table it can take significant time.

Why this can hurt in production. With live traffic, you are asking the system to scan lots of data, sort lots of index entries, build a new B+ tree, and potentially compete for CPU, memory, and I/O with normal application traffic. Adding an index in production is operationally meaningful. It is not something to treat casually. (In InnoDB, building a secondary index normally lets other queries keep running, but the extra load is still real.)

3. Adding an index is one-time work. Maintaining it is forever.

Many people focus only on the initial cost of adding an index. The better question is: what is the long-term cost of keeping this index? Once it exists, every future write must maintain it. The real burden is permanent maintenance. A new index may look like a win for one slow query today, but it silently adds write cost to every insert, update, and delete from that day on.

4. What happens on insert when many indexes already exist?

Suppose the table already has several indexes. One new record means:

• inserting the full row into the clustered index
• inserting the corresponding key entry into every secondary index

So one write operation multiplies into many index updates, which means:

• more page access
• more page splits over time
• more redo logging
• more dirty pages
• more write amplification

Once a heavily indexed table gets busy, write performance can degrade noticeably. "Just add one more index" is not a harmless production habit.

5. The main production question: many different queries, do we need many indexes?

In production, many kinds of queries exist: user-facing reads, admin filters, background jobs, exports, reporting queries, rare troubleshooting queries. The naive thought is "add an index for every query pattern". The answer is no, not for every query. You often need several indexes in a real system, but you must prioritize.

6. Index the important query patterns, not every possible query

Design indexes for the query patterns that matter most. Usually that means:

• the top 5 to 20 hot query patterns that account for most real traffic
• critical background jobs that must not fall behind

These affect user experience, latency, throughput, and operational health. Everything else does not automatically deserve its own index.

What about less important queries? You have other options:

• accept slower performance
• cache the result
• pre-compute it
• move it to an analytics system
• run it on a replica or a separate workload path

Not every query belongs on the hot OLTP path. If a query is occasional, expensive, and not user-critical, it may be better to keep it slower than to add a permanent write tax to the primary table.

7. The practical query-index framework

For each important query, ask:

So instead of "index every column separately", think: can one composite index match the real query pattern better?

A small worked example (illustrative). On employees:

8. Composite indexes need careful thinking

Composite indexes are powerful, but not magical. Suppose you create an index on (email, phone_no). The index is ordered first by email, then by phone_no.

 index on (email, phone_no)  -- sorted by email, then phone_no

 (a@x.com, 7001)
 (a@x.com, 7009)
 (b@x.com, 6500)
 (c@x.com, 5000)
 (c@x.com, 9000)

• A query that filters on email can use it very well.
• A query that filters only on phone_no may not use it the way you expect, because phone numbers are scattered across all emails.

The B+ tree is organized by the defined column sequence. A composite index is not the same as "independent indexing of all included columns". Composite indexes must be designed around real query patterns, not around the list of columns developers happen to use.

9. When one table cannot serve all query patterns: change the architecture

Sometimes the problem is not "we forgot one more index". It is that too many competing workloads are being forced through the same OLTP table. Then adding more and more indexes does not solve everything. Two common approaches:

Vertical split. Separate hot and cold columns into different tables. Suppose employees has id, email, country, phone_no. User-facing traffic cares about id, email, country, while phone_no is used by a different class of queries. Instead of over-indexing one big table:

 employees_core(id, email, country)      <- hot OLTP table, few indexes
 employee_phone(id, phone_no)            <- separate table, its own indexing

Each table gets its own indexing strategy, which reduces pressure on the hot table and lets you optimize workloads separately.

Sharding or partitioning. Reduce the working set each query has to consider, through:

• partitioning
• sharding
• read replicas (depending on the system design)

The mechanics depend on the architecture, but the idea is the same: separate workloads instead of forcing everything through one growing, index-heavy path. This matters most when scale is large enough that index tuning alone is no longer enough.

10. If OLTP is suffering, do not keep indexing forever

If the transactional system struggles because too many query patterns compete on the same tables, you do not index your way out forever. Excessive indexing has costs:

• slower writes
• bigger storage
• more maintenance
• more page churn
• more memory pressure
• more operational complexity

When a table is asked to support too many different query shapes, the mature solution is often not "another index". It is:

• split workloads
• move reporting elsewhere
• cache hot reads
• precompute expensive aggregations
• use analytics systems for analytics-type access

That is the long-term scaling mindset.

Deep Dive

Internal behavior. A page is 16 KB; the clustered index is a B+ tree of pages; secondary indexes are more B+ trees; reads and writes go through the buffer pool; changes are protected by the redo log. A full leaf that overflows splits, which can leave pages partly empty (fragmentation) and is why random inserts are more expensive than ordered inserts.

NULL handling (in this chapter's context).

Performance considerations

• Keep rows narrow so more rows fit per page.
• Keep the primary key short, stable, and increasing.
• Keep the hot working set within the buffer pool size.
• Every secondary index copies the primary key and taxes every write.
• Prefer one good composite index over several single-column indexes.
• Use covering indexes for the hottest read queries when the extra columns are few.
• Remove unused indexes (MySQL 8's sys.schema_unused_indexes helps).
• Build new indexes on big tables carefully, in a quiet period.

Database behavior.

• This chapter describes InnoDB (the MySQL default). Other engines and databases organize storage differently. For example, PostgreSQL stores table rows in a heap, and its indexes point to row locations, unlike InnoDB's primary-key-based clustering.
• SQL Server also has clustered indexes, with its own rules.
• The 16 KB page size is an InnoDB default; some systems use 8 KB pages.

Storage vocabulary

Real-world Use Cases

• Capacity planning: estimating buffer pool size from the size of the hot data, and index size from row counts and key widths.
• Choosing a primary key: short integer surrogate keys for big tables, and compact or time-ordered ids when UUIDs are required.
• Index reviews: listing the top query patterns, dropping unused indexes, and merging single-column indexes into composites.
• Write-heavy systems (logs, events, payments): fewer indexes, a narrow key, and batch inserts.
• Read-heavy systems (catalogs, dashboards): covering indexes and replicas.
• Schema migrations: planning the cost of adding an index to a live table.
• Crash recovery: understanding why committed data survives a power failure (the redo log).
• Workload separation: moving reports to a replica or an analytics store, and splitting hot and cold columns.

Review Tips

Interviewers commonly ask:

• "Where does a row physically live in InnoDB?" — In a page (16 KB) inside a tablespace file, in the leaf of the clustered index.
• "Why does the database read pages and not rows?" — Disk I/O is expensive and works in blocks; one page read brings many rows, which helps caching.
• "What is the buffer pool?" — The in-memory cache of pages. It is why hot data is fast.
• "What is a dirty page?" — A page in memory that is newer than the copy on disk.
• "What happens on COMMIT in InnoDB?" — The redo log is flushed durably. Dirty pages are written to the table file later in the background.
• "What happens if the server crashes after a commit, before pages were flushed?" — On restart, InnoDB replays the redo log, so the committed change is not lost.
• "How does InnoDB choose the clustering key?" — Primary key, else the first unique NOT NULL index, else a hidden 6-byte row id.
• "What does a secondary index store?" — The index key plus the primary key, not the full row.
• "Why does a wide primary key hurt?" — It is copied into every secondary index entry, making them bigger, and making the tree deeper and the cache less efficient.
• "Why do indexes slow down writes?" — Each insert, update, or delete must also update every index.
• "What is a covering index?" — An index that holds all the columns a query needs, so no clustered lookup is required.
• "Why B+ trees and not binary trees or hash maps?" — Wide nodes mean a shallow tree (few page reads), sorted leaves give ordered access, and linked leaves make range scans cheap. Hash maps cannot do ranges.
• "How is a UNIQUE constraint enforced?" — By an index lookup plus concurrency-safe enforcement inside the engine.
• "You have 30 different queries. Do you index all of them?" — No. Index the hot, critical patterns, use composites, and move or accept slower for the rest.

Common Mistakes to Avoid

Mistake 1: Thinking rows are stored one after another, and that the database reads one row

Why it happens: The row is the unit we write SQL in.

Result: wrong guesses about performance.

Correct: The page is the unit of I/O and caching.

Mistake 2: Not defining a primary key

Why it happens: The table works without one.

Result: InnoDB picks a clustering key by accident, or creates a hidden one you cannot use.

Correct: Always declare a primary key.

Mistake 3: Using a wide or random primary key (like CHAR(36) UUID)

Why it happens: UUIDs are convenient across systems.

Result: bigger secondary indexes, more page splits, worse cache use.

Correct: A short integer surrogate key, or compact, time-ordered ids.

Mistake 4: Believing secondary indexes store the full row

Why it happens: "The index has the data."

Result: surprise at the double lookup and at the index size.

Correct: A secondary index stores the index key plus the primary key, and a lookup of other columns goes back to the clustered index.

Mistake 5: Adding an index for every slow query

Why it happens: Each index fixes one query.

Result: slower writes, more storage, and a fragile table.

Correct: Index the hot patterns, use composites, and accept slower for the rest.

Mistake 6: Assuming a composite index works for any of its columns

Why it happens: It "contains" the column.

Result: a filter on only the second column does not use it well.

Correct: Remember the order: (email, phone_no) helps email, and email + phone_no, not phone_no alone.

Mistake 7: Creating an index on a huge live table without planning

Why it happens: It looks like a quick fix.

Result: heavy CPU and I/O during the build.

Correct: Schedule it, watch the load, and consider an online schema-change tool.

Mistake 8: Forgetting that an index is permanent write tax

Why it happens: The first cost (the build) is what people notice.

Result: writes slowly degrade.

Correct: Judge every index by its ongoing cost, and remove unused ones.

Mistake 9: Thinking COMMIT means the table file is already updated

Why it happens: "Committed" sounds final on disk.

Result: confusion about durability.

Correct: COMMIT means the redo log is durable. The table page is flushed later.

Mistake 10: Enforcing uniqueness only in application code

Why it happens: "We check before inserting."

Result: two concurrent requests both pass the check.

Correct: A UNIQUE constraint, plus handling the duplicate-key error.

Mistake 11: Forgetting that a large buffer pool is the cheapest speed-up

Why it happens: Attention goes to query rewrites.

Result: a hot working set that does not fit in memory.

Correct: Check the buffer pool hit ratio and size it to the hot data.

Mistake 12: Keeping huge TEXT/BLOB columns in hot tables

Why it happens: It is easy to keep everything in one table.

Result: rows are heavy, and off-page reads slow queries that touch them.

Correct: Keep hot rows narrow, and move large content to a separate table or storage.

Mistake 13: Expecting a B+ tree to help every condition

Why it happens: "It is indexed."

Result: a function or leading wildcard on the column still forces a scan (see Day 36 sargability).

Correct: Write conditions the index can navigate.

Mistake 14: Indexing your way out of a workload problem

Why it happens: Indexing is the tool everyone knows.

Result: a table with many indexes that is still slow.

Correct: Separate the workloads: vertical splits, replicas, caching, and analytics stores.

Key Takeaways

• Rows are stored inside pages, and pages live in files. The page (16 KB by default in InnoDB) is the unit of reading, writing, caching, and management.
• Pages are fixed-size and files grow. Memory capacity is best thought of as "how many pages fit in the buffer pool".
• Large variable-length columns can move to overflow pages. An oversized fixed-size layout can fail with error 1118.
• Disk hierarchy: data directory, database folder, a .ibd file per table, ibdata1 (system tablespace), and redo logs.
• One .ibd file holds clustered index pages, secondary index pages, and free or allocated pages. B+ trees are stored in these pages.
• Databases feel fast because the buffer pool serves pages from RAM. A miss reads whole pages from disk, and hot pages stay cached.
• The clustering key is the primary key, else the first unique NOT NULL index, else a hidden 6-byte DB_ROW_ID.
• InnoDB is memory-first, disk-later: modify pages in RAM (dirty), append the redo log, commit by flushing the redo log, and flush dirty pages in the background. After a crash, the redo log is replayed.
• A linear chain of pages makes insert, update, delete, and range-scan start costs O(N).
• B+ trees are balanced, multi-way trees: internal nodes navigate, leaves hold the entries, and leaves are linked for range scans.
• Adding an index creates a new B+ tree in the same file and does not replace the clustered index. Composite indexes are separate structures too.
• When a leaf overflows it splits, and the overflow can propagate up to the root, making the tree one level taller. Trees stay shallow.
• Search follows one short path. A range scan searches once, then walks the linked leaves.
• A UNIQUE constraint uses an index lookup plus concurrency-safe enforcement.
• The clustered index leaf holds the full row. A secondary index leaf holds (secondary key, primary key), so a lookup of other columns needs a second step to the clustered index, unless the index covers the query.
• The primary key is copied into every secondary index, so a wide key bloats all of them. Keep it short, stable, and increasing.
• Every extra index taxes every write and is permanent maintenance. Building one on a large live table is real work.
• Index the top hot query patterns, prefer composites, and move or accept slower for the rest. If OLTP still suffers, split the workload instead of indexing forever.