四叉树的核外实现
我正在尝试在辅助内存（硬盘）上构建四叉树数据结构（或者只是说一棵树）。
我有一个 C++ 程序来执行此操作，并使用 fopen 来创建文件。另外，我使用 tesseral 编码将每个单元存储在一个以其相应代码命名的文件中，以将其存储在磁盘上的一个目录中。
问题是，在创建大约 1,100 个文件后，fopen 仅返回 NULL 并停止创建新文件。我可以在该目录中手动创建更多文件，但使用 C++ 它无法创建任何其他文件。
我知道 ext3 文件系统上 inode 的最大限制是（来自维基百科）32,000，但我的远小于这个限制，还要注意我可以在磁盘上手动创建文件；只是不是通过fopen。
另外，我真的很欣赏关于在磁盘上存储非常动态的四叉树的最佳方法的任何想法（我需要节点位于单独的文件中，并且四叉树的深度可能为 50）。
使用嵌套目录是一种想法，但我认为它会降低性能，因为遵循文件系统上的链接来访问文件。
谢谢， 尼玛
I am trying to build a Quadtree data structure(or let's just say a tree) on the secondary memory(Hard Disk).
I have a C++ program to do so and I use fopen to create the files. Also, I am using tesseral coding to store each cell in a file named with its corresponding code to store it on the disk in one directory.
The problem is that after creating about 1,100 files, fopen just returns NULL and stops creating new files. I can create further files manually in that directory, but using C++ it can not create any further files.
I know about max limit of inode on ext3 filesystem which is (from Wikipedia) 32,000 but mine is way less than that, also note that I can create files manually on the disk; just not through fopen.
Also, I really appreciate any idea regarding the best way to store a very dynamic quadtree on disk(I need the nodes to be in separate files and the quadtree might have a depth of 50).
Using nested directories is one idea, but I think it will slow down the performance because of following the links on the filesystem to access the file.
Thanks,
Nima
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
失败的 fopen() 调用的 errno 值是多少？
您是否将创建的文件保持打开状态？如果是，您很可能超出了每个进程打开文件的最大数量。
Whats the errno value of the failed fopen() call?
Do you keep the files you have created open? If yes you are most probably exceeding the maximum number of open files per process.
当您使用目录作为数据结构时，您将维护该结构的工作委托给文件系统，而文件系统不一定是为此而设计的。
编辑：弗兰克可能是对的，您已经超出了可用文件描述符的数量。您可以增加这些，但这表明您也在使用 ABI 的内部结构作为数据结构。缓慢且（随着资源耗尽）不稳定。
要么为非常特定的操作系统安装编写代码，要么使用 SQL 数据库。
When you use directories as data structures, you delegate the work of maintaining that structure to the file system, which is not necessarily designed to do that.
Edit: Frank is probably right that you'v exceeded the number of available file descriptors. You can increase those, but that shows that you're also using internals of your ABI as a data structure. Slow and (as resources are exhausted) unstable.
Either code for a very specific OS installation, or use a SQL database.
我不知道为什么
fopen不起作用。查看错误号。然而，将所有内容存储在一个目录中并不是一个好主意。当您添加大量文件时，速度会变慢。为树的每个级别都有一个目录也会很慢。
相反，请将多个级别合并到一个目录中。例如，您可以为树的每四层设置一个目录。这将限制目录数量、嵌套数量以及每个目录的文件数量，从而提供非常好的性能。
I have no idea why
fopenwouldn't work. Look aterrno.However, storing everything in one directory is a bad idea. When you add a lot of files, it will get slow. Having a directory for every level of the tree will also be slow.
Instead, combine multiple levels into one directory. You could, for example, have one directory for every four levels of the tree. This would limit the number of directories, amount of nesting, and number of files per directory, giving very good performance.
该限制可能来自：
The limitation could come from: