Have you increased the cache size to a decent size for your "rather large" database? File fragmentation does not affect random block access times for files on an SSD since the block access time is constant (unlike rotating rust which has stepper delays (typically 1/3 stroke) plus rotational delay (typlically 1/3 rotation) plus settling time (which may increase rotational delay by one rotation in the event of a large stroke or noisy servo positioner)). It is more likely that as the table becomes more disorganized you have insufficient cache defined to hold the working set of the tree traversal data causing excessive I/O. Note that even I/O which is serviced by the "system cache" is considerably slower than access to the same page in "application storage" because access to the "system cache", although the data itself may be cached in RAM, requires accessing "supervisor mode" to perform the I/O operation and the transition itself can be quite expensive (compared to directly accessing a page already stored in user/process memory). So the first thing I would do is look to see if the cache hit rate for the connection is adequate. See the sqlite3_db_status <https://sqlite.org/c3ref/db_status.html> for the API you can use to retrieve connection statistics from which you can compute the applicable rates. Adequate in this case means that the hit rate for the "disorganized state" should be the same as for the "organized" state. Note that this applies only to "read" queries. Updates will always require at least one I/O so it should be expected for the hit rate to fall when mixing reads with writes ... especially as a "write" may change some of the access path pages thus requiring a cache miss on the next access if a change was made though a different context (connection).