讨论一下文件型数据库的内部数据结构

Question

其实这个问题主要是想研究一下动态改变文件大小，并在中间插入数据的处理。比如Access，一个文件里可以存放多个表，每个表可以分别操作。如果这些表在文件中是连续存放的，
那么在一个处在中间位置的表的大小发生改变的时候，后面的表都要向后移动，当然，这应该是被Cache的，不然加入一条记录就移动大量数据是没法让人接受的。问题是，这种情况下，这个Cache是怎么实现的呢？每一个表分别用一个文件？像光盘镜像那样几百兆大小的文件，如果往里面加入或删除一个文件，又是怎么避免大量的数据移动的呢？有些ZIP文件可能更大。因为这个问题的涉及面这么广，
所以我怀疑是不是操作系统解决了这个问题，在文件中插入数据的操作可以由操作系统分配磁盘空间。但一般的文件操作函数里并没有相应的操作啊。希望听听各位的高见。

Answer 1

对数据抽取特征值，比如说数据库的索引就是特征值，然后在文件内部建立索引，表明该数据块实际在文件中的位置，这样就不必进行实际上的数据大挪移了。
对于大型巨量数据，要考虑用非线性存储，比如说m序的B-树，ntfs文件结构就是这样实现的，大文件内部也可以这样。
这样对数据的访问可以大致是O(n*log(n))的数量级。

Answer 2

不好意思，过了这么久才来 -_-
谢谢严兄的回答。不过你说的B树只能用来查找吧，我的问题是在文件中间插入或删除数据之后，怎么使得对整个文件操作最小。
想想看那些光盘镜像文件，还有Zip，即时有好几G那么大，但如果你删除其中一个小文件还是瞬间完成的事，这是怎么实现的呢？难道他们把后面的数据填充到了空出来的位置，然后缩小了文件尺寸？

Answer 3

B树当然不仅仅是查找的，还能动态增加、删除数据。B树节点的冗余结构，保证了一般的修改并不会引起大量数据修改。特别是，如果节点中保存的不是大量数据本身，而仅仅是数据的连接，比如文件系统中文件的存放地址，那么更符合这种情况。说光盘影像。比如Winiso，当删除iso中文件并保存的时候是马上完成的，但你请注意，这个iso文件不会缩小！这些空间还是占据的。要释放也可以，需要“另存为”，但这就是数据重新组织，是个长时间大数据量的操作了，
说zip文件，以我的经验，当重新组织zip文件的时候，特别是大zip包的时候，整个zip文件是重写的，很费时间。