为什么删除文件很重要
前段时间我了解到rsync删除文件的速度比许多其他工具快得多。
几天前，我在Serverfault上遇到了这个奇妙的答案，这解释了为什么rsync非常擅长删除文件。
从该答案引用：
今天我重新讨论了这个问题，因为大多数文件系统以btree格式存储目录结构，删除文件的顺序也很重要。 当您执行取消链接时，需要避免重新平衡btree。 因此，我在删除发生之前添加了一个排序。
你能否解释一下如何删除文件以防止或减少btree rebalancings的数量？
我期望答案显示如何删除以增加删除速度，并详细说明在btree级别发生的情况。 编写rsync和其他程序的人（参见问题中的链接）使用这些知识来创建更好的程序。 我认为其他程序员对这种理解能够写出更好的软件非常重要。
这不重要，也不是B型树问题。 这只是一个巧合 。
首先，这是非常多的实现依赖和非常ext3具体。 这就是为什么我说这不重要（一般用途）。 否则，放入ext3标签或编辑汇总行。
其次重要的是，ext3的不使用B树的目录项指标。 它使用Htree。 Htree类似于b-tree，但不同，不需要平衡。 在fs / ext3 / dir.c中搜索“htree”。
由于基于htree的索引，a）ext3比ext2有更快的查找比较，但b） readdir()以散列值顺序返回条目。 散列值顺序相对于文件创建时间或数据的物理布局是随机的。 众所周知，随机访问比旋转媒体上的顺序访问慢得多。
曹明明等人发表的关于OLS 2005的ext3的论文。 建议（强调我的）：
以inode编号对由readdir（）返回的目录条目进行排序。
现在，到rsync上。 Rsync按文件名排序文件。 请参阅flist.c :: fsort（），flist.c :: file_compare（）和flist.c :: f_name_cmp（）。
我没有测试以下假设，因为我没有@MIfe获得43秒的数据集。 但我认为按名称排序比readdir（）返回的随机顺序更接近最优顺序。 这就是为什么你在ext3上用rsync看到更快的结果。 如果你用随机文件名生成1000000个文件然后用rsync删除它们呢？ 你看到相同的结果吗？
假设您发布的答案是正确的，并且给定的文件系统的确将事物存储在平衡树中。 平衡一棵树是一项非常昂贵的操作。 保持树“部分”平衡非常简单，因为如果允许树略微不平衡，则只需要担心在插入/删除点周围移动东西。 然而，当谈到完全平衡的树时，当你移除一个给定的节点时，你可能会突然发现，这个节点的子节点可能属于树的完整对立面，或者对面的子节点已经成为根节点节点，并且它的所有孩子都需要在树上旋转。 这需要您执行一系列长循环，或者将所有项目放入数组并重新创建树。
5
3 7
2 4 6 8
现在删除7，容易吧？
5
3 8
2 4 6
现在删除6，仍然很容易，是的...？
5
3 8
2 4
现在删除8，呃哦
5
3
2 4
让这棵树成为适当的平衡形式，如：
4
3 5
2
相当昂贵，至少与我们已经完成的其他清除相比，并且随着我们树的深度增加而呈指数级恶化。 在移除8之前，我们可以通过移除2和4来使得它变得更快（指数级地）。特别是如果我们的树超过3层深度。
没有排序移除平均为O（K * log_I（N）^ 2）。 N表示元素总数，K表示要移除的数量，I是允许给定节点的子节点数量，log_I（N）表示深度，对于每个深度级别，我们都会按照二次方式增加操作次数。
有些订购帮助的移除平均为O（K * log_I（N）），但有时订购不能帮助您，并且您被卡住的东西需要重新平衡。 尽管如此，最小化这是最佳的。
编辑：
另一种可能的树排序方案：
8
6 7
1 2 3 4
在这种情况下完成最佳移除会更容易，因为我们可以利用我们对事物排序的知识。 在任何一种情况下，它都是可能的，事实上两者是相同的，在这个逻辑之下，逻辑仅仅是更容易理解，因为排序对于给定的场景更加人性化。 在任何一种情况下，按顺序被定义为“首先去除最远的叶子”，在这种情况下，它恰好是最远的叶子也是最小的数目，我们可以利用它来使它变得更小更优化，但这个事实对于所提供的文件系统例子来说并不一定是正确的（虽然它可能是）。
如果您按顺序删除文件，我不相信B树再平衡的数量会发生显着变化。 但是，我确实相信，如果你这样做，对外部存储的不同寻求的数量将会大大减少。 在任何时候，需要访问的B树中唯一的节点将是树的最右边界，而随机顺序，B树中的每个叶块以相同的概率访问每个文件。
链接地址: http://www.djcxy.com/p/40081.html