ovg*_*vin 28 filesystems algorithm b-tree delete-file
前段时间我学会了rsync删除文件比许多其他工具快得多.
几天前,我在Serverfault上遇到了这个精彩的答案,这解释了为什么rsync删除文件非常好.
从那个答案的报价:
我今天重访了这个,因为大多数文件系统以btree格式存储它们的目录结构,删除文件的顺序也很重要.当您执行取消链接时,需要避免重新平衡btree.因此我在删除之前添加了一个排序.
你能解释一下如何按顺序删除文件来阻止或减少btree重新计算的数量？
我期望答案显示如何删除以增加删除速度,详细说明btree级别发生的事情.写作的rsync人和另一个程序(参见问题中的链接)使用这些知识来创建更好的程序.我认为让其他程序员有这种理解能够写出更好的软件是很重要的.
Yas*_*oji 11
这不重要,也不是b-tree问题.这只是一个巧合.
首先,这非常依赖于实现,而且非常具体.这就是为什么我说它并不重要(一般用途).否则,请输入ext3标记或编辑摘要行.
所有第二,Ext3并没有使用B树的目录项指标.它使用Htree.Htree类似于b-tree但不同且不需要平衡.在fs/ext3/dir.c中搜索"htree" .
由于基于htree的索引,a)ext3与ext2相比具有更快的查找速度,但b)readdir()以散列值顺序返回条目.哈希值顺序相对于文件创建时间或数据的物理布局是随机的.众所周知,随机访问比旋转媒体上的顺序访问要慢得多.
一篇关于ext3的论文,由Mingming Cao等人发表于OLS 2005.建议(强调我的):
按顺序编号对 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
在这种情况下实现最佳去除将更容易,因为我们可以利用我们对事物如何分类的知识.在任何一种情况下都是可能的,事实上两者都是相同的,在这一情况下逻辑只是更容易理解,因为对于给定的场景,排序更加人性化.在任何一种情况下,有序被定义为"首先移除最远的叶子",在这种情况下恰好是最远的叶子也是最小的数字,这是我们可以利用它甚至一点点的事实更优化,但这个事实不一定适用于所呈现的文件系统示例(尽管它可能是).