多維元數(shù)據(jù)索引文件系統(tǒng)設(shè)計與實現(xiàn)

史軍勇 李文靜

摘要：容量龐大的磁盤外部存儲設(shè)備導(dǎo)致文件檢索性能下降，傳統(tǒng)的“按名檢索”方法已經(jīng)無法滿足海量文件系統(tǒng)檢索需求，面向近些年流行的多維索引技術(shù)，應(yīng)用R樹設(shè)計和實現(xiàn)一個基于文件屬性的多維元數(shù)據(jù)索引文件系統(tǒng)MIFS，分析了MIFS目錄樹多屬性索引結(jié)構(gòu)和插入、刪除、分裂操作算法，闡述了MIFS索引結(jié)構(gòu)的物理實現(xiàn)及其用戶接口，最后，實驗測試了MIFS和Ext 3文件系統(tǒng)用戶接口的周轉(zhuǎn)時間，結(jié)果表明MIFS文件檢索性能得到了顯著提高。

關(guān)鍵詞：多維元數(shù)據(jù)索引;文件系統(tǒng);R樹;降維;用戶接口

中圖分類號：TP316? ? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）16-0026-04

開放科學（資源服務(wù)）標識碼（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 引言

為了滿足海量信息存儲，外存儲設(shè)備容量在過去的10年得到顯著提升，磁盤存儲容量已經(jīng)從GB數(shù)量級上升到TB數(shù)量級，基于外存儲設(shè)備的文件檢索已經(jīng)成為系統(tǒng)軟件設(shè)計者必須面臨的一個問題。

外存儲設(shè)備的信息存儲結(jié)構(gòu)相比于存儲容量發(fā)展緩慢，依然以文件作為基本信息存儲單元，采用多層樹狀目錄結(jié)構(gòu)，文件系統(tǒng)類型主要有FAT、NTFS和EXT2。FAT文件系統(tǒng)采用順序檢索，效率不高。為了改善“按名檢索”的效率，NTFS文件系統(tǒng)采用B+樹結(jié)構(gòu)按文件名索引目錄項[1]，Ext2/Ext3文件系統(tǒng)則將文件名和文件屬性分開存儲，引入索引結(jié)點概念。傳統(tǒng)的“按名檢索”僅能從一維空間區(qū)分文件，而無法從多維空間區(qū)分文件。Apple公司在Mac OS中實現(xiàn)的Spotlight基于文件屬性存取允許從多維空間區(qū)分文件，但其封閉性無法得到廣泛推廣。近些年，多維索引技術(shù)不斷被應(yīng)用到文件系統(tǒng)中，如K-D樹[2]、四叉樹[3]。本文在Ext2/Ext3文件系統(tǒng)的基礎(chǔ)上，提出了一種采用R樹實現(xiàn)的多維元數(shù)據(jù)索引文件系統(tǒng)（Multi-dimensional Indexing File System， MIFS），能夠?qū)Χ嗑S文件屬性索引，實現(xiàn)多字段聯(lián)合查詢，提高文件檢索效率。

2 R樹

1984年，R[4]樹由Guttman提出，它是目前最流行的動態(tài)空間索引結(jié)構(gòu)之一，廣泛應(yīng)用于原型研究和商用空間數(shù)據(jù)庫系統(tǒng)。R樹是一棵平衡樹，中間結(jié)點和葉子結(jié)點由M個結(jié)構(gòu)為（I，Pointer）的單元組成，中間結(jié)點的Pointer指向子結(jié)點，葉子結(jié)點的Pointer指向索引對象。I定義為：

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

式中，n是空間對象的維數(shù)，Ii是第i維上的坐標范圍[a，b]。若結(jié)點是中間結(jié)點，則I是其所有子結(jié)點的最小包含矩形MBR;若結(jié)點是葉子結(jié)點，則I是索引對象的最小包含矩形MBR。

R樹上定義的操作有初始化、檢索、插入、刪除和分裂。

Initialize（R） 初始化操作，設(shè)置一個空的R樹。

Search（R， S） 檢索操作，在R樹中查找位于S超幾何體域中的空間對象，S超幾何體的空間維數(shù)等同于R樹索引對象維數(shù)。

Insert（R， Obj） 插入操作，在R樹中插入Obj空間對象。

Delete（R， Obj） 刪除操作，在R樹中刪除Obj空間對象。

Split（R， Node） 分裂操作，當R樹的中間結(jié)點或葉子結(jié)點達到最大單元個數(shù)時，執(zhí)行此操作。Node指向R樹的中間結(jié)點或葉子結(jié)點。

R樹是一種動態(tài)查找結(jié)構(gòu)，插入、刪除和檢索可以同時進行，不需要周期性地重組查找結(jié)構(gòu)。R樹兄弟結(jié)點索引區(qū)域重疊，存在多路徑查詢問題，如圖1所示。為了提高R樹的檢索性能，Selis等人于1987年提出了R+樹[5]，通過對象分割，解決多路徑查詢問題。而Beckmann等人認為區(qū)域重疊并不會導(dǎo)致更壞的檢索性能，于1990年設(shè)計了R*樹[6]，通過優(yōu)化R樹結(jié)點分裂方法，使得目錄矩形（某一查詢路徑的所有MBR）更近似于正方形。另外，R樹的優(yōu)化還在于提高結(jié)點存儲利用率，如Hilbert R樹[7]、Compact R樹[8]等。

3 MIFS文件系統(tǒng)設(shè)計

3.1 多維文件屬性索引

異構(gòu)文件系統(tǒng)設(shè)有不同數(shù)量的文件屬性，但通常都包含基本文件管理信息、文件安全管理信息和文件存儲結(jié)構(gòu)信息。基本文件管理信息如文件名、文件主、關(guān)鍵字、摘要、文件訪問時間等。文件安全管理信息用于文件存取訪問控制，實現(xiàn)文件的安全管理，如文件主訪問控制列表、文件主組訪問控制列表等。文件存儲結(jié)構(gòu)信息包含文件的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)信息，描述文件信息的組織方式。文件系統(tǒng)用戶接口大多基于基本文件管理信息，如文件創(chuàng)建、刪除、檢索等操作。表1列出了Ext2/Ext3文件系統(tǒng)支持的基本文件管理信息[9]。

MIFS文件系統(tǒng)對多維文件屬性采用R樹索引結(jié)構(gòu)。R樹的索引空間通常都會選擇3～4維，隨著維數(shù)的增加，R樹結(jié)點間重疊區(qū)域快速增長，檢索性能也急劇惡化，最終會陷入維數(shù)危機[10]。MIFS按文件屬性類型及其相關(guān)性分為k個組，每一個組定義為一個屬性組（G）。Ext2/Ext3文件系統(tǒng)基本文件管理信息可以分為4個組，即文件名組、用戶標識符組，尺寸組和時間組，文件名組只包含name，用戶標識符組包含i_uid和i_gid，尺寸組包含i_size和i_blocks，時間組包含i_atime、i_ctime、i_mtime和i_dtime。設(shè)每個屬性組包含有di個文件屬性θ，定義第i個屬性組Gi定義為一個二維向量，如公式（1）。

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

MIFS按屬性組索引，由先前的文件點對象索引轉(zhuǎn)換成對超幾何體對象的索引，R樹結(jié)點中的任一個單元描述一個超幾何體，父結(jié)點的超幾何體包含所有子結(jié)點的超幾何體，索引維數(shù)從[i=1kdi]維降低到k維。文件檢索算法首先是用超幾何體對象圈定一個文件存在的粗糙范圍，然后再精確匹配文件，具體過程可描述為：

step 1：將以多維完全或非完全屬性檢索的文件對象按公式（1）轉(zhuǎn)換為k維超幾何體Obj。未指定屬性取值范圍設(shè)定為正負無窮;屬性組內(nèi)屬性取值范圍邏輯關(guān)系始終為或，取最小值與最大值作為范圍;屬性組間屬性取值邏輯關(guān)系若為且，則檢索的k維超幾何體只有一個，若為或，則檢索的k維超幾何體有多個，每一個或因子即為一個被檢索超幾何體。

step 2：從R樹的根結(jié)點L開始。如果L不是葉子結(jié)點，遍歷L中的所有單元，判斷每一個單元I與Obj的關(guān)系，如果I與Obj相交，則令單元所指的子結(jié)點為根結(jié)點L，遞歸調(diào)用直到L是葉子結(jié)點。

step 3：判斷L結(jié)點中的空間對象是否滿足多維屬性檢索要求，如果滿足，則輸出該文件對象，否則，略過。

3.2 插入文件算法

插入文件算法描述為：

step 1： 按公式（1）將文件對象轉(zhuǎn)換為k維超幾何體Obj。

step 2： 尋找一個合適的葉子結(jié)點L存放文件對象。如果L中沒有空閑單元，則分裂L結(jié)點，生成新的L和L”結(jié)點，將文件點對象存入L結(jié)點中，更新L父結(jié)點P的MBR使其包含L，令L=P，Obj=L”;否則，在L中存入文件對象，退出。

step 3： 在L中存入超幾何體Obj。如果L中沒有空閑單元，則分裂L結(jié)點，生成新的L和L”結(jié)點，在L中存放Obj，更新L父結(jié)點P的MBR使其包含L，令L=P，Obj=L”，重復(fù)step 3，直到L中有空閑單元或者L為根結(jié)點。

step 4 如果L中有空閑單元，則存入Obj;否則，分裂L生成新的根結(jié)點，存入原根結(jié)點和Obj。

3.3 刪除文件操作

刪除文件算法描述為：

step 1：按公式（1）將文件對象轉(zhuǎn)換為k維超幾何體Obj。

step 2：用Obj檢索文件對象所在的葉子結(jié)點L。刪除L中文件對象所對應(yīng)的單元，刪除后若L中空閑單元數(shù)大于M/2，則刪除L結(jié)點下的所有文件對象，并把刪除的文件對象添加到T集合。

step 3：令Obj為L父結(jié)點單元所對應(yīng)的超幾何體，L為L結(jié)點的父結(jié)點，重復(fù)step 4在L中刪除Obj，直到L中空閑單元數(shù)小于M/2或者L為根結(jié)點。

step 4：在L中刪除超幾何體Obj，并將T中的文件對象重新插入到R樹中。

3.4 結(jié)點分裂操作

R樹分裂算法要盡可能減少重復(fù)檢索路徑，分裂的優(yōu)劣將影響到檢索性能。Guttman以面積為計算標準，選取分裂后兩組單元MBR面積和最小的分裂方法，劃分M個單元為兩組窮舉會有[CM2M2]種，時間復(fù)雜度較高。為減小分裂算法時間復(fù)雜度，Guttman介紹了平方耗費算法（Quadratic-Cost Algorithm），通過選取兩個種子單元，采取面積遞增最小的方法分裂R樹結(jié)點，種子選取的方法有[C2M]種。MIFS索引結(jié)構(gòu)插入、刪除、檢索算法參照降維后的超幾何體，分裂時以超幾何體體積最小增長為標準，超幾何體的體積定義為：

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

其中，LIi表示超幾何體每一維的取值范圍。結(jié)點分裂思想適用于插入算法中尋找合適葉子結(jié)點的過程，尋找到的葉子結(jié)點要使得插入文件對象后的超幾何體體積增長最小。

4 MIFS文件系統(tǒng)的實現(xiàn)

4.1 MIFS的實現(xiàn)

Ext2/Ext3文件系統(tǒng)文件名與文件屬性分開存儲，節(jié)約了讀取的數(shù)據(jù)量，提高了“按名檢索”的效率，但檢索只能采用遍歷目錄樹的方法。MIFS文件系統(tǒng)在Ext2/Ext3的基礎(chǔ)上，在目錄樹的頂層增加一個R樹文件，對目錄樹中的所有文件對象（包括目錄文件）進行索引。R樹葉子結(jié)點指針指向文件對象，文件對象用i結(jié)點描述。另外，為了快速定位文件的位置，再增加一個i結(jié)點到文件位置的映射文件，通過對R樹的檢索，既可以快速獲取檢索文件的位置信息，也可以通過直接讀取i結(jié)點得到文件屬性的詳細列表。

R樹文件是一個定長記錄文件，記錄定義為：

struct r_file_rec{

int deleted;

int flag;

int num;

struct r_node n;

int pnum;

};

其中deleted域表示該記錄是否被刪除;flag域表示該記錄是R樹葉子結(jié)點，還是中間結(jié)點;num域是R樹的結(jié)點號，結(jié)點號按記錄在文件中的位置順序編排;n域表示R樹的結(jié)點，結(jié)點的大小由R樹的度決定;pnum域指向該結(jié)點的父結(jié)點。

映射文件采用索引順序文件結(jié)構(gòu)，如圖2所示。索引文件記錄i結(jié)點號及其路徑在路徑文件中的偏移，Del是記錄刪除標記，i記錄文件結(jié)點號，len是路徑的長度，off記錄路徑存儲偏移量。路徑文件由不定長的絕對路徑順序存放組成。

R樹文件和映射文件上定義記錄分配、刪除、壓縮等操作，實現(xiàn)記錄存儲空間的管理，為用戶層文件對象創(chuàng)建、刪除等操作服務(wù)，實現(xiàn)R樹結(jié)點插入、刪除、分裂等任務(wù)。

4.2? MIFS用戶接口

系統(tǒng)調(diào)用是操作系統(tǒng)提供給用戶的程序接口，用戶層軟件通過系統(tǒng)調(diào)用實現(xiàn)。POSIX.1標準規(guī)定了操作系統(tǒng)內(nèi)核提供給用戶的標準程序集，其中文件操作函數(shù)如open、create、lseek、read、write、truncate等，目錄操作函數(shù)如mkdir、rmdir、chown、fchown、lchown、link、unlink、remove、rename、symlink、utime等。Linux平臺下，用戶層軟件（如shell命令）提供的文件操作命令如vi，目錄操作如mkdir、rmdir、chown、mv等，目錄檢索操作如ls、locate、find等。MIFS不改變操作系統(tǒng)原有內(nèi)核結(jié)構(gòu)，重定義操作系統(tǒng)用戶層軟件，本質(zhì)上可視為一種新的操作系統(tǒng)接口，與Ext2/Ext3文件系統(tǒng)文件/目錄操作相仿。在Linux平臺上，MIFS用戶接口用shell腳本語言編程，包含測試文件/目錄操作命令是否正確執(zhí)行、轉(zhuǎn)換相對路徑為絕對路徑、測試文件的屬性、調(diào)用R樹文件和索引文件操作函數(shù)等步驟。

5 性能測試

Linux系統(tǒng)中find命令從目錄樹結(jié)構(gòu)指定結(jié)點開始，采用遞歸遍歷的方法尋找目錄樹下與文件名通配字符模式匹配，或者具有給定屬性的文件或目錄。若查找以字符串libc開頭、大小在200字節(jié)到300字節(jié)之間、用戶名是root、修改時間在9年前與10年后的文件，命令描述為：

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

在主頻為2GHz、內(nèi)存為2GB、磁盤容量8GB、文件系統(tǒng)為Ext3的Linux虛擬機上，對結(jié)點數(shù)量級不同的目錄樹用time工具比較find命令和MIFS檢索命令的周轉(zhuǎn)時間，實驗結(jié)果如圖3所示。橫坐標代表目錄樹中文件的結(jié)點數(shù)，以萬為單位，縱坐標代表周轉(zhuǎn)時間，以秒為單位。

find對磁盤目錄樹結(jié)構(gòu)遞歸遍歷查找，隨著目錄樹結(jié)點的增加，檢索時間顯著增長;而MIFS的檢索時間增長相對緩慢，檢索時間主要用于R樹文件和映射文件檢索，且R樹文件、映射文件相對較小，就18萬個結(jié)點的目錄樹，R樹文件大約為50MB。另外，R樹索引結(jié)構(gòu)滿足了文件系統(tǒng)多屬性索引的要求。

MIFS用戶接口其它操作周轉(zhuǎn)時間與Ext3文件系統(tǒng)文件/目錄操作周轉(zhuǎn)時間比較結(jié)果如圖4所示。由于MIFS用戶接口在完成常規(guī)文件/目錄操作后，還要即時修正R樹文件及映射文件，故而時間耗費相對常規(guī)文件系統(tǒng)接口要多。為了改善該問題，可以引入日志操作，對R樹文件及映射文件進行批量修改。

6 結(jié)束語

本文采用近些年流行的R樹多維索引結(jié)構(gòu)，通過研究R樹的查找、插入、刪除和分裂操作，就當前磁盤空間容量日益龐大，檢索時間過長問題，提出并實現(xiàn)了一種多維文件屬性元數(shù)據(jù)索引的文件系統(tǒng)，對文件屬性分類降低索引維數(shù)，重定義R樹的查找、插入、刪除和分裂操作，在現(xiàn)有Ext3文件系統(tǒng)的基礎(chǔ)上，用shell腳本語言在原有文件/目錄操作的基礎(chǔ)上重新定義多維元數(shù)據(jù)索引文件系統(tǒng)操作，實驗結(jié)果表明該方法能夠有效提高檢索效率，而對文件系統(tǒng)接口其他操作時間影響有限。

參考文獻：

[1] 吳偉民，盧琦，王振華，蘇慶. NTFS目錄下索引B+樹結(jié)構(gòu)動態(tài)解析[J]. 計算機工程與設(shè)計，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] 王柏，胡谷雨，羅健欣. 一種高效的海量數(shù)據(jù)儲存方案[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] 夏宇，朱欣焰. 高維空間數(shù)據(jù)索引技術(shù)研究[J]. 測繪科學. 2009，34（1）：60-62

【通聯(lián)編輯：王力】