多維元數據索引文件系統設計與實現

史軍勇 李文靜

摘要：容量龐大的磁盤外部存儲設備導致文件檢索性能下降，傳統的“按名檢索”方法已經無法滿足海量文件系統檢索需求，面向近些年流行的多維索引技術，應用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

【通聯編輯：王力】