多维元数据索引文件系统设计与实现

史军勇 李文静

摘要：容量庞大的磁盘外部存储设备导致文件检索性能下降，传统的“按名检索”方法已经无法满足海量文件系统检索需求，面向近些年流行的多维索引技术，应用R树设计和实现一个基于文件属性的多维元数据索引文件系统MIFS，分析了MIFS目录树多属性索引结构和插入、删除、分裂操作算法，阐述了MIFS索引结构的物理实现及其用户接口，最后，实验测试了MIFS和Ext 3文件系统用户接口的周转时间，结果表明MIFS文件检索性能得到了显著提高。

关键词：多维元数据索引;文件系统;R树;降维;用户接口

中图分类号：TP316        文献标识码：A

文章编号：1009-3044（2021）16-0026-04

开放科学（资源服务）标识码（OSID）：

Research and Implementation of Multi-dimensional Meta-data Indexing File System

SHI Jun-yong， LI Wen-jing

（Zhengzhou Institute of Aeronautical Industry Management， Zhengzhou 450046，China）

Abstract：Huge capacity of disk storage device descends the file searching performance and traditional method of searching by name couldnt satisfied the demand of file system. Combined with the popular multi-dimension indexing technology in recent years， a kind of multi-dimension meta-data indexing file system named MIFS is designed and realized based on R-tree. Multi-properties index structure of file system directory tree and operating algorithms which include insert， delete， split are analyzed. Physical realization of index structure and user interface are discussed. In the end， the turnaround time of MIFS user interface operations is compared with Ext3 file system user interface operations and the test result shows that the file searching performance of MIFS is substantially improved.

Key words：multi-dimension meta-data index; file syste; R-tree; dimension reduction; user interface

1 引言

为了满足海量信息存储，外存储设备容量在过去的10年得到显著提升，磁盘存储容量已经从GB数量级上升到TB数量级，基于外存储设备的文件检索已经成为系统软件设计者必须面临的一个问题。

外存储设备的信息存储结构相比于存储容量发展缓慢，依然以文件作为基本信息存储单元，采用多层树状目录结构，文件系统类型主要有FAT、NTFS和EXT2。FAT文件系统采用顺序检索，效率不高。为了改善“按名检索”的效率，NTFS文件系统采用B+树结构按文件名索引目录项[1]，Ext2/Ext3文件系统则将文件名和文件属性分开存储，引入索引结点概念。传统的“按名检索”仅能从一维空间区分文件，而无法从多维空间区分文件。Apple公司在Mac OS中实现的Spotlight基于文件属性存取允许从多维空间区分文件，但其封闭性无法得到广泛推广。近些年，多维索引技术不断被应用到文件系统中，如K-D树[2]、四叉树[3]。本文在Ext2/Ext3文件系统的基础上，提出了一种采用R树实现的多维元数据索引文件系统（Multi-dimensional Indexing File System， MIFS），能够对多维文件属性索引，实现多字段联合查询，提高文件检索效率。

2 R树

1984年，R[4]树由Guttman提出，它是目前最流行的动态空间索引结构之一，广泛应用于原型研究和商用空间数据库系统。R树是一棵平衡树，中间结点和叶子结点由M个结构为（I，Pointer）的单元组成，中间结点的Pointer指向子结点，叶子结点的Pointer指向索引对象。I定义为：

I=（I1， I2， I3， I4， … ， In）

式中，n是空间对象的维数，Ii是第i维上的坐标范围[a，b]。若结点是中间结点，则I是其所有子结点的最小包含矩形MBR;若结点是叶子结点，则I是索引对象的最小包含矩形MBR。

R树上定义的操作有初始化、檢索、插入、删除和分裂。

Initialize（R） 初始化操作，设置一个空的R树。

Search（R， S） 检索操作，在R树中查找位于S超几何体域中的空间对象，S超几何体的空间维数等同于R树索引对象维数。

Insert（R， Obj） 插入操作，在R树中插入Obj空间对象。

Delete（R， Obj） 删除操作，在R树中删除Obj空间对象。

Split（R， Node） 分裂操作，当R树的中间结点或叶子结点达到最大单元个数时，执行此操作。Node指向R树的中间结点或叶子结点。

R树是一种动态查找结构，插入、删除和检索可以同时进行，不需要周期性地重组查找结构。R树兄弟结点索引区域重叠，存在多路径查询问题，如图1所示。为了提高R树的检索性能，Selis等人于1987年提出了R+树[5]，通过对象分割，解决多路径查询问题。而Beckmann等人认为区域重叠并不会导致更坏的检索性能，于1990年设计了R*树[6]，通过优化R树结点分裂方法，使得目录矩形（某一查询路径的所有MBR）更近似于正方形。另外，R樹的优化还在于提高结点存储利用率，如Hilbert R树[7]、Compact R树[8]等。

3 MIFS文件系统设计

3.1 多维文件属性索引

异构文件系统设有不同数量的文件属性，但通常都包含基本文件管理信息、文件安全管理信息和文件存储结构信息。基本文件管理信息如文件名、文件主、关键字、摘要、文件访问时间等。文件安全管理信息用于文件存取访问控制，实现文件的安全管理，如文件主访问控制列表、文件主组访问控制列表等。文件存储结构信息包含文件的物理结构和逻辑结构信息，描述文件信息的组织方式。文件系统用户接口大多基于基本文件管理信息，如文件创建、删除、检索等操作。表1列出了Ext2/Ext3文件系统支持的基本文件管理信息[9]。

MIFS文件系统对多维文件属性采用R树索引结构。R树的索引空间通常都会选择3～4维，随着维数的增加，R树结点间重叠区域快速增长，检索性能也急剧恶化，最终会陷入维数危机[10]。MIFS按文件属性类型及其相关性分为k个组，每一个组定义为一个属性组（G）。Ext2/Ext3文件系统基本文件管理信息可以分为4个组，即文件名组、用户标识符组，尺寸组和时间组，文件名组只包含name，用户标识符组包含i_uid和i_gid，尺寸组包含i_size和i_blocks，时间组包含i_atime、i_ctime、i_mtime和i_dtime。设每个属性组包含有di个文件属性θ，定义第i个属性组Gi定义为一个二维向量，如公式（1）。

[Gi=α，βα=MINθ1，θ2，...，θdiβ=MAXθ1，θ2，...，θdi]                      （1）

MIFS按属性组索引，由先前的文件点对象索引转换成对超几何体对象的索引，R树结点中的任一个单元描述一个超几何体，父结点的超几何体包含所有子结点的超几何体，索引维数从[i=1kdi]维降低到k维。文件检索算法首先是用超几何体对象圈定一个文件存在的粗糙范围，然后再精确匹配文件，具体过程可描述为：

step 1：将以多维完全或非完全属性检索的文件对象按公式（1）转换为k维超几何体Obj。未指定属性取值范围设定为正负无穷;属性组内属性取值范围逻辑关系始终为或，取最小值与最大值作为范围;属性组间属性取值逻辑关系若为且，则检索的k维超几何体只有一个，若为或，则检索的k维超几何体有多个，每一个或因子即为一个被检索超几何体。

step 2：从R树的根结点L开始。如果L不是叶子结点，遍历L中的所有单元，判断每一个单元I与Obj的关系，如果I与Obj相交，则令单元所指的子结点为根结点L，递归调用直到L是叶子结点。

step 3：判断L结点中的空间对象是否满足多维属性检索要求，如果满足，则输出该文件对象，否则，略过。

3.2 插入文件算法

插入文件算法描述为：

step 1： 按公式（1）将文件对象转换为k维超几何体Obj。

step 2： 寻找一个合适的叶子结点L存放文件对象。如果L中没有空闲单元，则分裂L结点，生成新的L和L”结点，将文件点对象存入L结点中，更新L父结点P的MBR使其包含L，令L=P，Obj=L”;否则，在L中存入文件对象，退出。

step 3： 在L中存入超几何体Obj。如果L中没有空闲单元，则分裂L结点，生成新的L和L”结点，在L中存放Obj，更新L父结点P的MBR使其包含L，令L=P，Obj=L”，重复step 3，直到L中有空闲单元或者L为根结点。

step 4 如果L中有空闲单元，则存入Obj;否则，分裂L生成新的根结点，存入原根结点和Obj。

3.3 删除文件操作

删除文件算法描述为：

step 1：按公式（1）将文件对象转换为k维超几何体Obj。

step 2：用Obj检索文件对象所在的叶子结点L。删除L中文件对象所对应的单元，删除后若L中空闲单元数大于M/2，则删除L结点下的所有文件对象，并把删除的文件对象添加到T集合。

step 3：令Obj为L父结点单元所对应的超几何体，L为L结点的父结点，重复step 4在L中删除Obj，直到L中空闲单元数小于M/2或者L为根结点。

step 4：在L中删除超几何体Obj，并将T中的文件对象重新插入到R树中。

3.4 结点分裂操作

R树分裂算法要尽可能减少重复检索路径，分裂的优劣将影响到检索性能。Guttman以面积为计算标准，选取分裂后两组单元MBR面积和最小的分裂方法，划分M个单元为两组穷举会有[CM2M2]种，时间复杂度较高。为减小分裂算法时间复杂度，Guttman介绍了平方耗费算法（Quadratic-Cost Algorithm），通过选取两个种子单元，采取面积递增最小的方法分裂R树结点，种子选取的方法有[C2M]种。MIFS索引结构插入、删除、检索算法参照降维后的超几何体，分裂时以超几何体体积最小增长为标准，超几何体的体积定义为：

V（I）=LI1*LI2*LI3*…*LIn

其中，LIi表示超几何体每一维的取值范围。结点分裂思想适用于插入算法中寻找合适叶子结点的过程，寻找到的叶子结点要使得插入文件对象后的超几何体体积增长最小。

4 MIFS文件系统的实现

4.1 MIFS的实现

Ext2/Ext3文件系统文件名与文件属性分开存储，节约了读取的数据量，提高了“按名检索”的效率，但检索只能采用遍历目录树的方法。MIFS文件系统在Ext2/Ext3的基础上，在目录树的顶层增加一个R树文件，对目录树中的所有文件对象（包括目录文件）进行索引。R树叶子结点指针指向文件对象，文件对象用i结点描述。另外，为了快速定位文件的位置，再增加一个i结点到文件位置的映射文件，通过对R树的检索，既可以快速获取检索文件的位置信息，也可以通过直接读取i结点得到文件属性的详细列表。

R树文件是一个定长记录文件，记录定义为：

struct r_file_rec{

int deleted;

int flag;

int num;

struct r_node n;

int pnum;

};

其中deleted域表示该记录是否被删除;flag域表示该记录是R树叶子结点，还是中间结点;num域是R树的结点号，结点号按记录在文件中的位置顺序编排;n域表示R树的结点，结点的大小由R树的度决定;pnum域指向该结点的父结点。

映射文件采用索引顺序文件结构，如图2所示。索引文件记录i结点号及其路径在路径文件中的偏移，Del是记录删除标记，i记录文件结点号，len是路径的长度，off记录路径存储偏移量。路径文件由不定长的绝对路径顺序存放组成。

R树文件和映射文件上定义记录分配、删除、压缩等操作，实现记录存储空间的管理，为用户层文件对象創建、删除等操作服务，实现R树结点插入、删除、分裂等任务。

4.2  MIFS用户接口

系统调用是操作系统提供给用户的程序接口，用户层软件通过系统调用实现。POSIX.1标准规定了操作系统内核提供给用户的标准程序集，其中文件操作函数如open、create、lseek、read、write、truncate等，目录操作函数如mkdir、rmdir、chown、fchown、lchown、link、unlink、remove、rename、symlink、utime等。Linux平台下，用户层软件（如shell命令）提供的文件操作命令如vi，目录操作如mkdir、rmdir、chown、mv等，目录检索操作如ls、locate、find等。MIFS不改变操作系统原有内核结构，重定义操作系统用户层软件，本质上可视为一种新的操作系统接口，与Ext2/Ext3文件系统文件/目录操作相仿。在Linux平台上，MIFS用户接口用shell脚本语言编程，包含测试文件/目录操作命令是否正确执行、转换相对路径为绝对路径、测试文件的属性、调用R树文件和索引文件操作函数等步骤。

5 性能测试

Linux系统中find命令从目录树结构指定结点开始，采用递归遍历的方法寻找目录树下与文件名通配字符模式匹配，或者具有给定属性的文件或目录。若查找以字符串libc开头、大小在200字节到300字节之间、用户名是root、修改时间在9年前与10年后的文件，命令描述为：

#find -name ‘libc* -a -size +200c -a -size -300c -a -user root -a -mtime -3660 -a -mtime +2928

在主频为2GHz、内存为2GB、磁盘容量8GB、文件系统为Ext3的Linux虚拟机上，对结点数量级不同的目录树用time工具比较find命令和MIFS检索命令的周转时间，实验结果如图3所示。横坐标代表目录树中文件的结点数，以万为单位，纵坐标代表周转时间，以秒为单位。

find对磁盘目录树结构递归遍历查找，随着目录树结点的增加，检索时间显著增长;而MIFS的检索时间增长相对缓慢，检索时间主要用于R树文件和映射文件检索，且R树文件、映射文件相对较小，就18万个结点的目录树，R树文件大约为50MB。另外，R树索引结构满足了文件系统多属性索引的要求。

MIFS用户接口其它操作周转时间与Ext3文件系统文件/目录操作周转时间比较结果如图4所示。由于MIFS用户接口在完成常规文件/目录操作后，还要即时修正R树文件及映射文件，故而时间耗费相对常规文件系统接口要多。为了改善该问题，可以引入日志操作，对R树文件及映射文件进行批量修改。

6 结束语

本文采用近些年流行的R树多维索引结构，通过研究R树的查找、插入、删除和分裂操作，就当前磁盘空间容量日益庞大，检索时间过长问题，提出并实现了一种多维文件属性元数据索引的文件系统，对文件属性分类降低索引维数，重定义R树的查找、插入、删除和分裂操作，在现有Ext3文件系统的基础上，用shell脚本语言在原有文件/目录操作的基础上重新定义多维元数据索引文件系统操作，实验结果表明该方法能够有效提高检索效率，而对文件系统接口其他操作时间影响有限。

参考文献：

[1] 吴伟民，卢琦，王振华，苏庆. NTFS目录下索引B+树结构动态解析[J]. 计算机工程与设计，2010（22）：4843-4846.

[2] Andrew W. Leung， Minglong Shao， Timothy Bisson， Shankar Pasupathy， Ethan L. Miller. Spyglass： Fast， Scalable Metadata Search for Large-Scale Storage Systems[EB/OL]. [2013-7-28]. http：//static.usenix.org/events/fast09/tech/full_papers/leung/leung_html/.

[3] 王柏，胡谷雨，罗健欣. 一种高效的海量数据储存方案[J]. 计算机工程，2012，38（18）：65-67.

[4] Guttman A. R-trees： A dynamic index structure for spatial searching[C]. In： Processdings of ACM SIGMOD， Boston， MA， 1984， 47-57

[5] Selis T. K.， Roussopoulos N.， Faloutsos C.. The R+-tree： A dynamic index for multi-dimensional objects [C]. In： Proceedings of the 13th VLDB， Brighton， England， 1987， 507-518

[6] Beckmann N.， Kriegel H.P.， Schneider R.， Seeger B.. The R*-tree： An efficient and robust access method for points and rectangles [C]. In： Proceedings of SIGMOD， Atlantic City， New Jersey， 1990， 322-331

[7] Kamel I.， Faloutsos C.. Helbert R-tree： An improved R-tree using fractals [C]. In： Proceedings of the 20th VLDB， Santiago Chile， 1994， 500-509

[8] Huang P. W.， Lin P. L.， Lin H. Y.. Optimizing storage utilization in R-tree dynamic index structure for spatial databases [J]. Journal of Systems and Software， 2001， 55（3）：291-299

[9] Bovet， D.P.， Cesati， M.. Understanding the Linux Kernel， Second Edition [M]. OReilly Media， Inc.， 2003

[10] 夏宇，朱欣焰. 高維空间数据索引技术研究[J]. 测绘科学. 2009，34（1）：60-62

【通联编辑：王力】