Recall that I’ve claimed that it takes 28 years to fill a disk with random insertions, given a set of reasonable assumptions. Recall what they are:
We are focusing on the storage engine (a la MySQL) level, and we are looking at a database on a single disk—the one we are using for illustration is the 1TB Hitachi Deskstar 7K1000. It has a disk seek time 14ms and transfer rate of around 69MB/s. [See tomshardware.com] We insert random pairs, each 8 bytes. So that’s 62.5 billion pairs to fill the disk, and at 4KB-size blocks, that 2^28 leaves (= 2^40 bytes / 2^12 bytes/leaf).
Now, my analysis requires each insertion to induce a disk seek. Suppose we do something clever with main memory. After all, we have this main memory hanging around. It should be possible to buffer up some insertions, and once we fill up main memory, insert key/value pairs that belong on the same leaf. Thus, fetching a …
[Read more]