database - 如何在文件级别处理从数据库中删除记录

Question

我正在开发一个简单的数据库系统（不希望使用股票数据库系统的开销，即使像 gdbm/bdb 一样简单），我试图找出处理删除的最有效方法是什么数据库文件中的记录。

我提出了两种看似幼稚的解决方案，一种在内存方面很昂贵，另一种在磁盘空间方面很昂贵，而且两者在时间方面似乎都很昂贵。第一个涉及将整个数据库读入内存，然后在旧数据库上重写它，但需要删除的记录除外。第二个涉及逐条记录地从旧数据库文件复制到新数据库文件（跳过要删除的记录），然后将新的复制到旧的。

有没有更好的办法？现有的数据库包如何处理这个问题？

Answer 1

另一种选择是在删除记录时将文件的部分标记为未使用，然后在添加新条目时将其他记录添加到文件的该部分。您可以选择使用某种“收缩”过程，该过程将在指定的时间间隔遵循您提到的方法之一。

我很确定 MySQL 的 innodb 表类型使用与此类似的方法来管理文件（尽管它们不提供收缩方法）。

Answer 2

您的数据库是作为平面文件实现的吗？我认为您可以考虑使用B+ 树 ，因为与您提到的方法相比，它会更简单。