有时候需要在文件上构建一颗 B 树、一张巨大的哈希表(动态数据结构)
面临的第一个问题:在文件上还能存数据结构的内存指针吗?——不能,只能存文件偏移代替
第二个问题:怎么对文件的存储空间进行管理?
构建 B 树、哈希表要为数据结构申请存储空间(文件偏移),删除数据会释放存储空间(文件偏移),已释放的存储空间能被重新利用吗?会不会有碎片化的问题?
看起来都指向了这个答案:在文件上实现 malloc 和 free
目前想到的方案:
初步做了一个 naive 的实现(使用 go ): https://github.com/roy2220/fsm
有兴趣一起讨论交流!
1
codehz 2020-02-16 02:13:31 +08:00 via Android
第一个问题是错的,任何现代操作系统都提供了内存映射功能。。。
|
2
roy2220 OP @codehz 实现上已经使用了 mmap 映射文件,但是每次内存映射的地址不确定(虽然 mmap 可以指定写死的映射地址,数据结构也就可以直接引用这个地址,因为不会变化,但是这样做太 trick ?)。还是记录文件偏移更健壮,外加使用 protobuf 做数据结构的序列化,这样大小端、内存对齐就和平台无关了
|
4
Mithrandir 2020-02-16 13:50:05 +08:00
mmap + 地址重定位可解
|
5
roy2220 OP @Mithrandir 现在的方案是运行时用 mmap 地址+文件偏移定位数据块
|
6
zhuyie 2020-02-17 20:43:10 +08:00 2
可以看看微软是怎么做的。微软开源了 Outlook 所用的 PST 文件格式,它由底至上抽象了 3 个层:
1. NDB Level: Node database, basic storage 2. LTP Level: Heap, BTree, Property bags, Tables 3. Messaging Level: Folders, Messages, Attachments https://docs.microsoft.com/en-us/openspecs/office_file_formats/ms-pst/141923d5-15ab-4ef1-a524-6dce75aae546 |