I got an idea when reading this for a file system for rotational (aka, "spinning rust") old-skool hard drives (which are probably pretty dated by this point!).<p>Basically, you create a B-tree.<p>Everything except the leaf nodes (that is, the root and all of the internal nodes) are stored outwardly from the center track of the hard drive, so if that's track 40, then it would be 40 then 39, then 41, then 38, then 42, etc.<p>Now, each leaf node is stored on the start of each track, and represents all of the blocks (after the blocks it itself takes up) on that track.<p>Now, when the OS needs to write or delete a block from a file, then the OS repositions the head to that track, writes the block, and then updates the leaf node (it's already on the same track -- so it's faster than moving the hard drive head to another track to do the update).<p>Yes, the rest of the B-Tree (on other tracks) might need to be updated as well, but if you were writing a whole bunch of blocks to an empty track at the same time, I think it could save some time...<p>If we were writing to a pre-existing file, and the B-Tree already had that track's leaf-node included in its pointers (that is, let's say that we're already writing to a file that already had one block on that track), then all we'd have to do is:<p>1) Move the hard drive head to that track<p>2) Write the new block<p>3) Update the leaf node of the B-Tree to say that the block is now part of the file.<p>It gets even better.<p>If there's a single block of the file on that track, and the track is otherwise empty, then if we have enough data to fill the track, then write all of the blocks, and cache writing to the B-Tree until all of that's done... in other words, a single write!<p>B-Tree entries are a key comprising FileID + DiskBlockID.<p>Files are ordered in DiskBlockID order.<p>Should be extremely fast -- for old spinning hard drives...<p>(Yes, I know... nobody uses spinning hard drives anymore! <g>)