kfs 文件管理系统.ppt

KFS 文件管理树陈学全 1、文件树的视图 2、B、B*树的定义 3、B*树的插入 4、B*树的查找 5、B*树的删除 1、文件树的视图?假设当前有以下文件 :?/ fid = 2 ( 根目录) ?/A fid = 3 ( 目录)?/B fid = 4 ( 普通文件) ?以 (d, pid, fid) 描述 fid 文件, d: 表示文件, pid: 表示父目录的文件 id, fid: 表示文件 id ;以 (a, fid, 0) 描述文件 fid 的属性, a: 表示文件属性, fid: 表示文件 id。其中 d < a 。?根目录的父目录的文件 id 为本身?目录“.”的 pid 、 fid 为所在目录的文件 id; 目录“..”的 pid 为所在目录的文件 id, fid 为上一层目录的文件 id ?树的比较键只取前面两个值 ((d, pid) 或者 (a, fid)) ?空树如图 1 – 1、插入目录“/”、”/A”、文件“/B”如图 1 – 2、 1 – 3、 1 – 4。此文件树节点的子节点数最小不能小于 3,最大不能大于 6。 1、文件树的视图 1、文件树的视图 1、文件树的视图 1、文件树的视图?已知父目录的 fid 进行文件查找的方式如下: ? a)、根据父目录的 fid 定位到树上的节点? b)、遍历目录下的所有文件,与查找的文件名进行比较?步骤 a) 的复杂度为 O(log2(t) * logt(n)) ,其中 t 为树的度, n 为总节点树,具体证明见第 4 节。?步骤 b) 的复杂度为 O(K) ,其中 K 为目录下的文件总数。?所以搜索的复杂度为 O(Max(K, log2(t) * logt(n))) 1、文件树的视图? KFS 文件树的 Key 是文件父目录的 fid ,所以需要一个路径到 fid 的映射关系。 KFS 具体实现里缓存了部分的 (路径, fid) ,如果缓存里不命中则再进行分级查找。?例如:要查找 /usr/local/home/kfs/ 的 fid , 如果缓存不命中,则根据 "/" 的 fid = 2 ( 固定值) 查 /usr 的 fid ,然后根据 /usr 的 fid 查/usr/local 的 fid ,依次查出/usr/local/home/kfs 的 fid 。?假设要进行路径 --> fid 转化的路径的深度为 D,则需要进行 D次搜索,所以转化的复杂度为: O(Max(D * K, D * log2(t) * logt(n))) ,因为在文件总数 n 一定的情况下 D 与 K 成简单的对数关系: K = logD(n) ,所以适当的增大 D 可大幅度的降低转化的复杂度。? KFS 文件管理树是 B树的一个变体 --- B *树。 2、B、B*树的定义? B 树的定义如下(见<<算法导论>> p265) : ?1、每个节点能包含的关键字数有一个上界和下界,这些界用整数 t (t >= 2) 来表示,这个值称作 B树的最小度数? a) 、每个非根节点至少包含有 t – 1 个关键字,非根的内节点至少有 t 个子女,根节点则不受限制。? b) 、每个节点至多包含 2t – 1 个关键字, 内节点之多可有 2t 个子女。当一个节点包含 2t – 1 个关键字时成它为满的节点。 2、B、B*树的定义?2、节点内的关键字按有序存放;假设内节点第 i个子女为 c[i] ,则子女节点 c[i] 的关键字的值在 key[i-1] 、 key[i] 之间?3、叶子节点的高度相同,都为 h ?当 t = 2 时的 B树最简单如图 2 – 1,也就是一棵 2- 3- 4 树,经过适当的转化可变成红黑树 (见 <<C 算法>> -- Sedgewick Robert p421) 2、B、B*树的定义图 2-1 一棵 t = 2 的 B 树