Disks Hand You Blocks, Not Bytes
Most of the search trees you learned about assume that touching a piece of data costs about the same everywhere. A binary search tree in memory jumps from node to node through pointers, and each jump is cheap. Put the same tree on a disk and that assumption breaks. Each jump may cost thousands of times more than a memory access, and the cost depends on how the data is laid out. To design a tree that works on disk, you first need to know what a disk actually does when you ask it for something.
Why the Disk Refuses to Give You One Byte
When your program asks for 100 bytes from a file, the disk does not hand over exactly those 100 bytes. The operating system reads a block, a fixed-size chunk of data, and returns the part you asked for. On most systems a block is 4 KB, which is 4096 bytes, though the size varies with the device and the file system. The block is the smallest unit the storage hardware and the operating system agree to move at once.
The reason is physical. A disk stores data on a surface that is divided into sectors, and reading one spot means finding the right position and then transferring a whole run of bits from it. Fixing the transfer unit makes the hardware simpler and lets the operating system keep track of where everything lives with a manageable amount of bookkeeping. The consequence for you is simple: a 100-byte read and a 4 KB read are, from the disk's point of view, the same request.
A useful way to hold this in your head is to think of a file as a long row of 4 KB boxes. Your node might sit at byte 9,000. The box that contains it runs from byte 8,192 to 12,287, and the disk will hand you the entire box no matter how little of it you need.
What a Block Read Actually Costs
Once you accept that a read fetches a whole block, the next question is what that fetch costs. The answer depends on the device, and the gap between devices is large. Reading from main memory takes on the order of 100 nanoseconds. A random read from a solid-state drive takes roughly 100 microseconds, about a thousand times longer. A random read from a spinning hard disk takes around 5 to 10 milliseconds, because the head has to move to the right track and then wait for the platter to rotate under it.
| Storage | Approximate time for one random 4 KB read |
|---|---|
| Main memory (DRAM) | about 0.1 microseconds |
| Solid-state drive (SSD) | about 100 microseconds |
| Spinning hard disk (HDD) | about 5 to 10 milliseconds |
Most of that time is spent getting to the block, not moving the bytes. Transferring 4 KB is fast once the data is under the head. The fixed cost of positioning and starting the transfer dominates, which means reading one block costs nearly the same whether you use all 4 KB or only 100 bytes of it.
This is the detail that most often surprises people. You might think that reading less data must be cheaper. On a disk, the number of block reads is the number that matters, and the size of each read barely changes the price. A structure that needs five block reads to find a key is slow, even if each of those reads only touches a few bytes of a block.
Random Versus Sequential Blocks
The order in which you read blocks matters as well. If the blocks you need sit next to each other on the disk, the drive can read them one after another without repositioning. This is a sequential read. If they are scattered, each one forces a new positioning step. This is a random read. On a spinning disk, a sequential read can deliver a hundred megabytes per second or more, while a stream of random 4 KB reads may manage only a few hundred blocks per second.
Solid-state drives narrow this gap but do not erase it. They still perform better when reads are large and grouped together, and they still pay a noticeable latency for each separate request. Sequential access is cheap, random access is expensive, and the gap is largest on the devices that are slowest to reposition.
So a disk-friendly design asks two questions. How many blocks does an operation need? And are those blocks close together or spread across the device? A tree whose nodes point to blocks anywhere on the disk pays the random-read price at every level, which is why the layout of nodes on disk becomes part of the design and not an afterthought.
Memory Keeps Blocks Around, Not Bytes
Operating systems try to hide the cost of block reads by keeping recently used blocks in memory. The collection of cached blocks is often called the page cache, and a database usually runs its own buffer pool on top of it. When your program asks for a block that is already in memory, the request costs about the same as any memory access. When it is not, the system has to fetch the block from the device, which is the expensive case.
This cache works because access patterns have locality: data used recently tends to be used again soon, and nearby data tends to be used together. A tree's upper levels are touched by nearly every lookup, so they usually stay cached. The lower levels are touched less often, so they are more likely to be read from the disk.
Caching does not change the rule that blocks are the unit of cost. It only changes which blocks you pay for. If you count block reads that miss the cache, you have a fair estimate of how a disk-based structure will perform. That count, not the number of comparisons a search makes, is the measure that tells you whether a design is fast or slow on disk.
AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.