Why the Disk Refuses to Give You One Byte
Suppose your program asks the operating system for 100 bytes starting at byte 10,000 of a file. You would reasonably expect the disk to deliver exactly those 100 bytes. It does not. The disk moves data in fixed-size units, and the smallest unit it can read or write is much larger than 100 bytes. Every design decision in a disk-based data structure rests on this fact. If you assume the disk hands you bytes, your estimate of what a lookup costs will be off by a factor of around 40, and your tree layout will be wrong in ways that are hard to spot later.
Your Program Thinks in Bytes, the Disk Thinks in Addresses
Your program treats a file as a long row of bytes and can point at any one of them. The disk does not see the file at all. It sees a numbered list of storage units, and each unit has an address. The unit is called a block (or sector, at the hardware level), and it is the smallest thing the device can transfer in one operation.
Think of a mail carrier who delivers to apartment buildings rather than individual flats. You can ask for a letter addressed to flat 3B, but the carrier brings the whole building's mail bag to the door. Sorting the bag into flats is your problem, not the carrier's. The disk is the carrier, the block is the bag, and the bytes you want are one letter inside it.
The operating system sits between the two. When you ask for 100 bytes, it works out which block holds them, reads that block into memory, and copies out the slice you asked for. The rest of the block is read and then thrown away from your program's point of view, though the operating system may keep it around (a separate story).
Sectors Are Set by Physics and Bookkeeping
Why is the unit so large? Part of the answer is the hardware itself. A spinning disk reads magnetic patterns off a track with a head that passes over the platter at a fixed speed. A flash drive reads charge levels from a grid of cells. In both cases, the device is built to produce a stream of data in chunks, and the chunk is the natural unit of its electronics.
The other part is overhead. Each sector carries more than its payload. It stores its own address so the drive can find it, and it stores an error-correction code, extra bits computed from the payload that let the drive detect and repair flipped bits. Those extra bits are a fixed cost per sector. If a sector were only 1 byte of payload, nearly all the space on the surface would go to labels and checks. Making the sector larger spreads that fixed cost across more useful bytes.
Historically, a sector was 512 bytes. Modern drives commonly use 4096-byte physical sectors, because bigger sectors waste less space on overhead and because the error-correction codes get more efficient as the payload grows. Flash storage uses its own internal page sizes, and erasing data happens in even larger groups, but the interface you see still presents fixed-size units.
:::html-embed spec: static diagram of a single disk sector laid out as a horizontal bar. Left segment labelled "Sector address" (small), middle large segment labelled "Payload: 4096 bytes", right small segment labelled "Error-correction code". Above the bar, a bracket spanning the whole bar labelled "One physical sector, read as a unit". Below the bar, a note reading "Overhead is a fixed cost per sector; larger payloads amortize it." Plain labels, no numbers beyond 4096. :::
Every Layer Rounds Up Again
The disk is not the only layer that rounds. The file system, which organises files into blocks on the disk, usually has its own block size, commonly 4 KB on Linux systems. The operating system's memory management also works in pages, typically 4 KB on common hardware. So a request for 100 bytes passes through several layers, and each one deals in units that are at least as large as the one below it.
This stacking matters because the largest unit wins. If the file system uses 4 KB blocks on a disk with 512-byte sectors, the file system will still ask the disk for 4 KB at a time, which the disk serves as eight sector reads. You do not get to pick a smaller unit by choosing a smaller layer. The rounding happens at every boundary, and the cost you actually pay is set by the coarsest one in the path.
How those blocks stay in memory and get reused is a separate question, and it has its own mechanics. For now, hold on to the simpler point: whatever the layer, your 100-byte request costs a whole block.
Writing 100 Bytes Means Rewriting a Whole Block
Reading wastes effort, but writing is where the rounding really hurts. The disk cannot change 100 bytes inside a block in place without the help of the layer above it. The only operation it offers is "write this whole block." So to update 100 bytes, the system must read the surrounding block, change the 100 bytes in memory, and write the entire block back. This pattern is called read-modify-write.
Put numbers on it. Suppose a 4096-byte block holds a record you want to update, and the update changes 100 bytes. You have written 4096 bytes to change 100 of them. The ratio of bytes moved to bytes you cared about is about 41, and that ratio is called write amplification. Ordinary reads have a milder version of the same problem, which is why the ratio for a 100-byte read is about 41 too: 4096 divided by 100 is roughly 41.
A common wrong intuition is that small updates are cheap because they are small. On a disk they are only cheap in the data you change, not in the work the disk performs. The cost follows the block, not the change.
$$ \frac{4096}{100} \approx 41 $$
:::html-embed spec: static diagram of a 4096-byte block drawn as a long horizontal rectangle divided into 41 equal narrow columns. One narrow column at the left is shaded and labelled "100 bytes you asked for"; the remaining columns are unshaded and labelled "Bytes read or written anyway". Caption beneath reads "Roughly 41 times the data you wanted moves through the disk." :::
Why This Shapes Every Structure That Lives on Disk
Once you accept that the disk moves blocks, the design question changes. You are no longer asking how to make each comparison cheap, because comparisons happen in memory and cost almost nothing. You are asking how to arrange your data so that each block you fetch is full of keys you will actually use. A structure that touches many blocks to find one answer pays for every one of them.
This is why disk-based search trees look different from the binary search trees you may have met in an algorithms course. A binary tree puts one key in each node and fetches one node per step. On disk, that means fetching a whole block to read one key, which wastes almost all of it. The alternative is to pack many keys into each node sized to one block, so every block read narrows the search by a large factor. The later parts of this book take that idea and work out the details, including how many keys fit in a node and how deep the tree becomes.
Keep the carrier and the bag in mind. The question is never "how do I get the letter?" It is "how do I make sure every bag I carry has the letters I need?"
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.