＋设为首页 ＋添加到收藏夹
其实讨论时希望能够一般化一些
暂只考虑二进制文件操作方式。
考虑这么一个操作，在往一个文件追加时，
实际上运行时间效率与所处的操作系统可能有密切关系，但总的说来，
在通常流行的操作系统上，能否达到常数时间复杂度？也就是说，
添加一段确定大小的数据，运行时间会不会独立于原有文件的尺寸，而是常数时间？
以下三个比较相关的问题：
在文件当中的某个位置插入一个“记录”，通常程序的写法中，都会有将
从所插入位置开始的所有剩余数据进行“后移”的操作；
如果是删除记录，又会有将删除位置后方的所有记录前移的操作；
在中的假设是可以对文件进行“截尾”的情形，如果文件系统没有
提供直接“截尾”的功能，可能意味着要把原有的文件拷贝到新的文件中，
但不复制要删除的记录。
这三个问题中，如果我要操作的记录的位置是随机的，那就需要常数复杂度O(n)，
有没有能够克服这种问题的办法呢？或者说，要达到的话必须写针对各个不同
文件系统的程序？
我觉得文件的效率可以不考虑,只要在编程的时候不做傻事就可以了,反正它基本上仅仅比Moden快... ...
楼主应该去参考数据库的实现，存放数据库的地方本质上来说其实是一个文件，设计数据库的时候，肯定要考虑到跟你的需求相关的情况，数据库的实现应该有很好的答案的。
偶也没有好法子,近来就在做文件系统,解析是晕得一塌糊涂...,效率也让人头疼...
惭愧，做东西时很少考虑到效率得问题.....
关注...
“楼主应该去参考数据库的实现，存放数据库的地方本质上来说其实是一个文件，设计数据库的时候，肯定要考虑到跟你的需求相关的情况，数据库的实现应该有很好的答案的。”
不失为一个办法，楼主研究有了眉目。拿出来给大家也研究研究？
这一般需要文件系统提供帮助，我的知识也有限，仅对我所熟悉的Linux和Windows系统说一下。
1）加快文件访问速度，达到常数时间追加，我认为，简单的mmap(Unix/Linux)和CreateFileMapping(Windows)就可以办到，先将现有文件映射到内存，这个时候就可以通过指针操作定位到文件末尾处，追加数据也仅需要普通的内存复制操作就能完成，最后将内存内容重新影射为磁盘即可。
2）在文件中添加或删除记录也可以说能够完成近似O(1)的时间复杂度。这取决于文件在磁盘中的存储结构。我们知道，Linux的ext3文件采用的是类似于链表的节点方式,每一个节点有其固定大小，可以采用O(1)时间复杂度计算出要修改的节点，那么其余的操作仅对于本块进行操作即可，如果添加数据，块增加超过的单块的长度，那么就增加一个新块，将这个新块添加到超级块中即可，同样删除的数据使得一个块失效了，将这个块删除即可。同样的办法也可以在Windows的Fat32或Fat16下操作即可，至于NTFS一直没有时间研究，因此不是很清楚，但是我想也会有同样的办法。
数据库在底层上也是操作文件,只不过采用了比较好的方法,比如分区,建立索引等等.
数据库之所以出现就是要解决大量信息在普通文件中存储带来的:存取效率低,杂乱无章,维护不方便,安全性差等问题.
文件操作本来就是效率很低的,所以一些要求及时响应的系统对文件操作甚至数据库操作次数都严格限制,还要对数据库进行优化.
许多大型数据库在进行数据更新,查询等操作的时候都是将数据读到内存进行操作,完了后commit.
国内某著名IT公司在这方面针对一些不经常更新,使用频率高的数据设计了内存表,常驻内存,效率的确得到了很大的提高.
这样，如果楼主有嵌入式系统的要求，楼主也有能力编写适配器的话，我倒有一个建议，不知道楼主是否认可。
各位可能都知道ACE这个准C++标准库，好多人可能认为它仅是作为网络编程的产品，但是他得很多的性却可以满足楼主的需求，即平均O(1)时间复杂度操作文件。它拥有几个内存分配器和与这些内存分配器相适配的hash_map结构。其中有一个内存分配器就是基于内存映射文件的，这就说明hash_map所产生的内存结构以及hash_map本身可以被转存到一个文件上，同时这个内存分配器也提供了一个地址中立的策略选项。因此不用担心其在向内存映射后原有分配指针失效的问题。这个分配器及hash_map的定义如下：
typedef ACE_Allocator_Adaptr< ACE_Malloc_T< ACE_MMAP_MEMORY_POOL, ACE_Null_Mutex, ACE_PI_Control_Block> > ALLOCATOR;
typedef ACE_Hash_Map_With_Allocator< int, class Record > HASH_MAP;
class Record是具体处理记录操作的类。
由于详细说明这些分配器需要很大的篇幅，我在这里不复述了。请楼主参考ACE的相关著作。
还是要用索引的办法, 在索引中记录ABSOLUTE地址, 在删除时仅仅做标记即可. 在"适当"的时候提交做PACK的操作.
在文件当中的某个位置插入一个“记录”，通常程序的写法中，都会有将
从所插入位置开始的所有剩余数据进行“后移”的操作；
这个问题我以前碰到过。我是这样解决的。
对文本文件建立 一个对应的二进制索引文件，直接在文件插入记录即可。插入记录时更变索引文件。查找时用二分法查找索引文件对应的记录行数。找到后处理它。
哈哈，不要担心这个问题，ACE本来就是可以支持嵌入式开发的。当然，你所接触过的开发平台不知道是什么CPU，它的C++不支持模板可能会比较不爽，那么也可以利用gcc作为它的编译器，目前大多数的硬件平台，gcc都有支持，我想只要你的嵌入式CPU还算常用的话，仅需编译一个交叉版本的gcc即可。那么就什么问题都解决了。
另外补充一句，好多路由器的嵌入式软件就是采用ACE开发的。
