I'm implementing my own simple database with disk storage, and I'm not sure how to go about modifying and deleting entries.

The problem is that as you delete a record from arbitrary position within a file, a "hole" is left there. As you insert a new entry, you may or may not be able to plug it into the hole. Modifying an entry in-place may be possible if the new value is smaller, leaving another hole. Or the new one may be larger, so one has to insert it some place else and delete the old one. Another hole.

If implemented like this, the database file starts looking like Swiss cheese after a while. The obvious solution is to run optimization every now and then to compact the file, but that is a tedious and not trivial to implement task as well. For instance, if the file is much larger than the amount of RAM, and you must carefully juggle the records in the file.

My question is: are there other approaches to database storage file management? And how do the big database management systems store the data on persistent storage? How do they deal with these problems?

I tried Googling but didn't get much info, possibly because I don't even know the right keywords.


The approach you describe is the same which is used, for instance, by SQL Server. With time, the data file grows, and you have to run a maintenance plan in order to shrink it by moving pages from the end of the file to its beginning. The only difference is that you're talking about records, while the usual notion is the one of pages.

Similarly, many file systems have a notion of fragmentation, which is eventually solved by performing a defragmentation on regular basis.

Note that:

  • If you're creating your own database for learning purposes and shrinking looks too complicated, then maybe you can leave it alone and focus on the things which are fun for your learning project. Just let the file grow over time—it's not like you're expecting to store terabytes of data in a home made database system anyway.

  • If you're creating your own database because you think you can do a better job compared to all existent database software products, then you may want to reconsider your choice. Note that if relational databases don't fit your needs, you may be better using other types of databases: the ones which store records, the hierarchical ones, the key-value stores, etc.


are there other approaches to database storage file management?

Don't actually delete records. Only mark them as deleted, then have your "DBMS" ignore the "marked" ones. Of course, this means that your tables get "fragmented", with lots of "holes" that you're constantly skipping over as you try to read the useful ones. To counter this, you need maintenance processes that re-write the file, actually removing all the dead records.

Postgres implements something akin to this in its VACUUM process.

Trying to work with any shared resource (file) in a multi-user, multi-threaded fashion is scary. Here's a possible, small-scale, alternative, if you feel like really thrashing your file system:

You might play with a "File per Record" implementation. Instead of trying to managing a shared file containing many records, you could put each (and every) record into a file of its own (a table is, therefore, represented by a directory).

Want to delete a record? Delete the corresponding file.

And how do the big database management systems store the data on persistent storage? How do they deal with these problems?

Every DBMS stores things differently and each has its own way of dealing with these problems ... but their owners are not very likely to give you chapter and verse on how they go about it.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.