May I also mention that N log N is the total cost of compaction for a DB of size N. You don't perform a compaction on every single write. Amortised per write the cost is more like N log(N)/N == log(N).
Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.
Also, N log(N) is nowhere near exponential. O(2^N) would be exponential, and that's not what you have here.