How RocksDB Works
One thing about LSM trees that are implemented with large numbers of large files in a filesystem, such as RocksDB, is that they defer to the filesystem to deal with fragmentation and block lookup isues.  That&#x27;s not actually free.<p>LSM tree descriptions typically imply or say outright that each layer is laid out linearly, written sequentially, and read sequentally for merging.  And that looking up a block within a layer is an O(1) operation, doing random access I&#x2F;O to that location.<p>But really, the underlying filesystem is doing a lot of heavy lifting.  It&#x27;s maintaining the illusion of linear allocation by hiding how the large files are fragmented.  That sequential writing is mostly sequential, but typically becomes more fragmented in the filesystem layer as the disk gets closer to full, and over time as various uses of the filesystem mean there are fewer large contiguous regions.  More fragmented free space makes the allocation algorithms have to do more work, sometimes more I&#x2F;O, just to allocate space for the LSM tree&#x27;s &quot;linear&quot; writes.<p>Lookup of a block inside a layer requires the filesystem to lookup in its extent tree or, with older filesystems, through indirect block lookups.  Those are hidden from the LSM tree database, but are not without overhead.<p>Writing sequentially to a layer generally requires the filesystem to update its free space structures as well as its extent tree or indirect blocks.<p>Even a simple operation like the LSM tree database deleting a layer file it has finished with, is not necessarily simple and quick at the filesystem layer.<p>In other words, when analysing performance, filesystems are the unsung heroes underlying some LSM tree databases.  Their algorithmic overhead is often not included in the big-O analysis of LSM tree algorithms running over them, but should be, and their behaviour changes as disk space shrinks and over time due to fragmentation.