这是一个创建于 1750 天前的主题，其中的信息可能已经有所发展或是发生改变。
有时候需要在文件上构建一颗 B 树、一张巨大的哈希表（动态数据结构）
面临的第一个问题：在文件上还能存数据结构的内存指针吗？——不能，只能存文件偏移代替
第二个问题：怎么对文件的存储空间进行管理？
构建 B 树、哈希表要为数据结构申请存储空间（文件偏移），删除数据会释放存储空间（文件偏移），已释放的存储空间能被重新利用吗？会不会有碎片化的问题？
看起来都指向了这个答案：在文件上实现 malloc 和 free
目前想到的方案：
- 大块存储空间使用 buddy 分配算法、小块存储空间使用 freelist （改良变种）管理
- “内存”管理的元数据和普通数据一起持久化到文件
- 使用 mmap 映射文件方便读写，使用 truncate 伸缩文件
初步做了一个 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 |
Select Language