I'm pretty sure the worst case is purely size-dependent. The write pattern in the HyperDex benchmark is pure random but it still obliterates HyperLevelDB (and

I'm pretty sure the worst case is purely size-dependent. The write pattern in the HyperDex benchmark is pure random but it still obliterates HyperLevelDB (and don't even think of vanilla LevelDB there). Keep in mind that LMDB uses free pages in sorted order, so even for a random write workload, pages are allocated in ascending order, which generally translates to unidirectional seeks on an HDD. This is why even for a purely random write load, LMDB is still faster than all of the traditional update-in-place B-trees out there - they really have to do random seeks, LMDB doesn't. (And you pay the highest in seek time when the drive head has to reverse direction.) That's why LMDB write performance remains uniform under load, while all LSMs suffer from GC/compaction pauses. But ultimately, storage is moving to solid state, and seek time will be irrelevant.