Answers · Where the data lives
Why does inserting a single row sometimes cost many page writes?
In shortA row insert usually writes one page, but when the target page is full it splits in half and the split can climb to the root, so rare inserts write several pages for each index.
Sometimes it costs many page writes because the bottom page is full, so it splits in half and the parent has to be told where the new boundary is; if that parent is also full, the split climbs. In the ordinary case the bottom page has room and the insert is one page write, with nothing above it changing because no boundary moved.
The easy case is exact. Descend to the bottom page holding the new key. If that page has 300 keys and there is a free slot, put the key in the correct position inside the page and write the page back. One read and one write. The upper signposts are untouched because the range of keys covered by every page is exactly what it was before the insert.
When the bottom page is full the arithmetic changes. The page holds 300 keys; after a split about 150 stay and about 150 move to a fresh page. That is two page writes for the halves, plus one write for the parent because the parent gains one signpost for the new boundary: 2 + 1 = 3 page writes. The parent learns one fact, not 300, because everything from the first key in the new page onwards is now on the new page. Both halves are left about half full, so this region can absorb roughly another 150 insertions before either half splits again. The split is not a copy of the full page plus a new page; it moves the upper half so that one expensive event is amortised over about 150 future inserts. If the split merely wrote one key to a fresh page, the old page would stay full and the next insert would split again.
| step | level | what happened | pages written | running total | what happened |
|---|---|---|---|---|---|
| 1 | bottom | full page split in half | 2 | 2 | Both halves are written. |
| 2 | second | parent was full, split in half | 2 | 4 | The second level repeats the same procedure. |
| 3 | root | root was full, split in half | 2 | 6 | The root also splits. |
| 4 | new root | a fresh page made above the old root | 1 | 7 | Every path grows by one level at once. |
If the parent is full, the same procedure runs at the next level. The trace gives 2 writes at the bottom, 2 at the second level, 2 at the root, and 1 for the new root page above the old root: 2+2+2+1=7 page writes for one inserted row. That is seven against one. The depth only increases when the root splits, and that single event lengthens every path from top to bottom at once, which is why no separate rebalancing step appears.
The natural guess is that one inserted row is one page write. It fails because the guess treats the page boundary as fixed. An insert that fits changes no boundary, so the guess is right. An insert that does not fit changes a boundary, and a boundary is stored in the parent as a signpost. The parent write is not optional bookkeeping; without it a lookup for a key that moved to the new page would descend to the old page and not find it. The second part of the guess is that the parent has room. It usually does, because it holds 300 entries and gains one entry only when one of its 300 children splits, but usually is not always. When it does not, the split repeats upward. And the cost is per index: a table with six indexes performs six descents and at least six bottom-page writes for the row before the split multiplier is counted.
For six indexes the plotted relation gives 1 + 2.6 × 6 = 16.6 page writes per inserted row for random keys, against 1 + 1.1 × 6 = 7.6 for keys that arrive in order. The difference is 16.6 - 7.6 = 9.0 page writes per row, which is the cost of scattering inserts across the whole structure instead of hitting one hot right-hand page. Even the ordinary case is six page writes for six indexes plus the row itself, not one.
| condition | fill factor, per cent | indexes | page splits, thousands | index size, MB |
|---|---|---|---|---|
| one index, random keys | 100 | 1 | 3400 | 710 |
| six indexes, random keys | 100 | 6 | 20400 | 4300 |
| six indexes, 70 per cent fill | 70 | 6 | 9100 | 6100 |
| six indexes, keys in order | 70 | 6 | 3200 | 6100 |
The arithmetic stops being true when the page has room. It also stops being true as a single number when the indexed key is monotonic: a timestamp or a sequence always inserts at the right-hand end, so one page is hot and cached and splits stay local. A random identifier inserts anywhere, so the bottom page is cold and splits are spread through the structure. The fill factor changes the starting point: build pages 100 per cent full and the index is as small as possible, 4300 MB in the six-index random case, and splits start immediately; build them 70 per cent full and the index is 6100 MB, which is 6100 - 4300 = 1800 MB larger, but splits fall from 20400 thousand to 9100 thousand, a reduction of 20400 - 9100 = 11300 thousand. In a system where an update writes a new row version, every index on the old location must also learn the new location even when the indexed column did not change, so the write cost can appear on updates as well as inserts.
Worth keeping
- An insert writes one page when the target bottom page has room; the upper signposts stay correct because no page boundary moved.
- A split writes both halves and the parent, and a full parent repeats the same procedure, so one insert can write up to seven pages.
- Every index is a separate structure, so a table with six indexes pays that cost six times before the row itself is counted.
Where this goes next
This question is one step of How an Index Actually Works, a course that works through its subject from the beginning. The page that teaches this part of it is What Happens on a Write, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why can't a hash index handle a range query like created_at > '2024-01-01'?A hash index finds only exact keys: it scrambles key order to pick a bucket, so there is no way to seek to the start of a range and walk forward.
- How does a B-tree find one row among millions in just a few reads?A B-tree finds a row by reading only a few pages: each page holds hundreds of pointers, so the tree stays three or four levels deep.
- Why is a log-structured store faster for writes than a B-tree?Because a B-tree finds a page and then rewrites it in place for every insert, while a log-structured store only appends, and appending in order is far cheaper than jumping about the disk.
- What does it mean for an index to cover a query?A covering index holds every column a query needs, so the database can answer from the index without reading the table row.
- Why is the date off by one day after I save it and read it back?You saved a calendar date as if it were a precise moment, so showing it in another time zone can move it to the day before or after.
- Is UTF-8 the same thing as Unicode, or what's the difference?No: Unicode assigns a number to each character, while UTF-8 is a way of writing those numbers as bytes, using one to four bytes per character.