Your math is unrealistic. You are tossing around theoretical numbers, which are meaningless for an actual implementation. Assume you have actually implemented

Your math is unrealistic. You are tossing around theoretical numbers, which are meaningless for an actual implementation. Assume you have actually implemented this very simple LSM. Is it reliable? i.e., are you using ARIES WAL? If so, then every insert has an additional cost of at least k for the log record. Are you using a raw block device, or are you using a filesystem? If a filesystem, then every insert has additional costs for metadata updates, and these costs are some multiple of the block size, not the key size. If using a filesystem, every "rewrite" of a level includes multiple metadata updates to empty/delete existing files and create/allocate new files. If not using a filesystem, then you must somehow manage metadata about the existence and size of your multiple levels yourself, as well as a space mapping of the raw block device. A B+tree gets most of that for free because it uses a single file, so the amount of filesystem-level metadata updating is minimal.