KFS文件系統的MetaServer元數據管理采用的是B+樹方式，下面將結合其源碼，對KFS MetaServer中元數據的組織形式及有關實現細節進行分析。

1. 相關源碼文件

KFS MetaServer元數據管理的代碼所在目錄為kfs-[version]/src/cc/meta，其中，相關的源碼文件有：

（1）meta/base.h：KFS元數據metadata中各節點的基礎類，包括的類：類Key、類MetaNode，它們分別代表B+樹種存儲的數據、所有B+樹節點的公共基礎信息。

（2）meta/meta.h和meta/meta.cc：封裝了metadata的基本數據定義，包括：類Meta、類MetaDentry、類MetaFattr和類MetaChunkInfo，它們分別代表文件系統中的目錄項、文件或目錄的屬性項、對于一個文件偏移（file offset）的Chunk信息。

（3）meta/kfstree.h和meta/kfstree.cc：封裝了對B+樹中內部節點Node的各種操作及Tree的基本操作（與文件系統無關，B+樹底層的實現），如插入節點、刪除節點等。

（4）meta/kfsops.cc：封裝了使用B+樹存儲KFS文件系統，實現的相關基本操作，如創建文件、刪除文件、創建目錄、刪除目錄等（作為Tree的實現）。

（5）meta/request.h和meta/request.cc：封裝了對ChunkServer或KfsClient發出的meta data請求的處理，通過Tree metatree執行相應的操作，實現對KFS文件系統各種基本操作的調用。

2. 為什么選用B+樹

KFS的文件系統采用的是B+樹，那么為什么選用B+樹而不是B-樹呢？這里做一個簡單的分析：

2.1 B-樹

B-樹的定義：

B-樹是一種平衡多路查找樹，一棵m階的B-樹，或者是一顆空樹，或者是滿足下列特征的m叉樹：

（1）樹中每個節點至多有m棵字數；

（2）若根節點不是葉子結點，則至少有2棵子樹；

（3）除根之外的所有非終端結點，則至少有[m/2]棵子樹；

（4）所有的非終端結點中包含下列信息數據：(n, p0, k1, p1, k2, p2, ..., kn, pn)，

其中：ki為關鍵字，且ki<ki+1；pi為指向子樹根結點的指針，且滿足pi所指子樹中所有結點的關鍵字均大于ki且小于ki+1，pn所指子樹中所有結點的關鍵字均大于kn；

（5）所有葉子結點均在同一層。

B-樹的檢索：

從根結點開始，對結點內的有序關鍵字序列進行二分查找，如果命中，則直接結束查找過程；否則，進入查詢關鍵字所屬范圍的兒子結點進行查找。重復以上過程，直到所對應的兒子指針為空，或已經是葉子結點。

B-樹的特性：

（1）關鍵字集合分布在整顆樹中；

（2）任何一個關鍵字出現且只出現在一個結點中；

（3）搜索有可能在非葉子結點結束；

（4）其搜索性能等價于在關鍵字全集內做一次二分查找；

（5）自動層次控制。

2.2 B+樹

B+樹的定義：

B+樹也是一種平衡多路查找樹，它是應文件系統所需而出的一種B-樹的變型樹。一顆B+樹滿足以下條件：

（1）每個非終端結點至多有m顆子樹；

（2）除根結點外，其他每個非終端結點至少有[(m+1)/2]顆子樹；

（3）根結點至少有2顆子樹；

（4）有n棵子樹的結點中含有n個關鍵字；

（5）所有的葉子結點中包含了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，且葉子結點本身依關鍵字的大小自小而大順序鏈接；

（6）所有的非終端結點可以看成是索引部分，僅包含其各個子結點中的最大關鍵字及指向子結點的指針。

通常來說，B+樹上有兩個頭指針，一個指向根結點，一個指向關鍵字最小的葉子結點。

B+樹的檢索：

B+樹的檢索方式分為兩種：

（1）一種是從指向關鍵字最小的葉子結點的頭指針開始，進行順序查找；

（2）一種是從指向根結點的頭指針開始，進行隨機查找：與B-樹基本相同，等價于在關鍵字全集做一次二分查找，區別是B+樹只有達到葉子結點才命中（B-樹可以在非葉子結點命中）。

B+樹的特性：

（1）所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；

（2）檢索時只有在葉子結點命中，不可能在非葉子結點命中；

（3）非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）數據的數據層；

（4）更適合文件索引系統。

2.3 B+樹與B-樹的比較

通過對B-樹和B+樹的定義及特性的了解，對兩者進行比較：

（1）占用空間大小方面：

• B-樹的非葉子節點中含有大量的關鍵字信息，占用的空間相對比較大；
• B+樹中只有葉子節點中才有關鍵字信息，非葉子節點并沒有指向關鍵字具體信息的指針，占用的空間相對比較小。

（2）檢索路徑長短方面：

• 由于B+樹的所有關鍵字都分布在葉子節點上，其他非葉子節點都是索引部分，因此樹階數（即樹高）要比B-大，檢索時要經過的路徑就多，運算時間相對長一些；
• 由于B-樹的關鍵字分布到各個節點上，相對于B+樹中完全分布到葉子節點上來說，分散分布的階數自然要小，因此B-樹的樹階數要比B+小，查找要經過的路徑相對比較少，運算時間相對短一些。

對于文件系統的設計來說，最關鍵的瓶頸在于磁盤IO操作，如果占用的磁盤空間少的話，IO操作耗時自然就少。而真正檢索內存中的數據結構（如B+樹、B-樹）的過程中，運算時間相對于磁盤IO操作來說要小的多，即內存的檢索時間不是主要的瓶頸之處。

因此，雖然對于同階的B-樹和B+樹，B+樹的樹高和平均檢索長度均大于B-樹 ，但實際上，檢索過程中，最耗時的操作是磁盤IO操作，而B-樹占用的空間相對較大，IO操作時劣勢明顯。由于B+樹的非葉子結點無記錄信息，只有索引，同樣大小磁盤空間就可以存放更多的索引信息，檢索訪盤次數反而少，速度也就比B-樹快。

2.4 選擇B+樹

B+樹比B-樹更適合實際應用中操作系統的文件索引和數據庫索引，原因在于：

（1）磁盤讀寫代價低：即使B-樹的運算時間相對于B+樹來說較短，但由于磁盤IO操作方面的劣勢，導致其總體上效率不如B+樹。

（2）查詢效率更穩定：B+樹中任何關鍵字的查找都必須經歷從根結點到葉子結點，因此所有關鍵字查詢的路徑長度相同，每一個數據的查詢效率相當。

3. 元數據組織結構

在KFS文件系統MetaServer元數據的實現中，有圖示幾種類型的B+樹節點：

（1）MetaNode: 所有葉節點和內部節點的公共基礎類，其中記錄了不同樹節點的類型信息。

（2）Node：表示內部節點，其中記錄了樹種內部節點的各種操作。

（3）Meta: 表示葉節點，而具體來說，不同的葉節點有：

• MetaDentry: 文件目錄項（Directory entry），實現從文件名到文件id的映射。
• MetaFattr: 文件或目錄屬性，相當于KFS中的一個inode節點。
• MetaChunkInfo: 對于一個文件偏移（file offset）的Chunk信息。

3.1 MetaNode

成員變量：

MetaType type;   //節點類型值
int flagbits;    //標志位

構造函數：

MetaNode(MetaType t)        //初始化type=t, flagbits=0
MetaNode(MetaType t, int f) //初始化type=t, flagbits=f

3.2 Node

成員變量：

int count;                       //孩子節點個數
Key childKey[NKEY];              //孩子的key
MetaNode *childNode[NKEY];       //孩子節點
Node *next;                      //下一個相鄰節點

構造函數：

Node(int f)    //初始化MetaNode中的節點類型type=KFS_INTERNAL，flagbits=f

3.3 Meta

成員變量：

fid_t fid;        //文件fid

構造函數：

Meta(MetaType t, fid_t id)  //初始化MetaNode中的節點類型信息type=t，及自身的fid=id

3.4 MetaDentry

成員變量：

fid_t dir;      //父目錄的fid
string name;    //目錄項的名稱
fid_t fid;      //目錄項的文件id

構造函數：

MetaDentry(fid_t parent, string fname, fid_t myID)

舉例說明：通過Dentry結構實現/root/1.txt的查找過程：

(1) 獲取”/”的fid=2

dir=2, name=“/”, fid=2

(2) 獲取”root”的fid=8

dir=2, name=“root”, fid=8

dir=2, name=“usr”, fid=6

(3) 獲取”1.txt”的fid=12

dir=8, name=”1.txt”, fid=12

dir=8, name=”2.txt”, fid=13

dir=8, name=”3.txt”, fid=14

由以上查找過程可知，/root/1.txt的fid為12。

3.5 MetaFattr

成員變量：

FileType type;          //類型（文件或目錄）
int16_t numReplicas;    //一個文件要求的備份數
struct timeval mtime;   //修改時間
struct timeval ctime;   //屬性變更時間
struct timeval crtime;  //創建時間
longlong chunkcount;   //chunk數目
off_t filesize;         //文件大小

構造函數：

MetaFattr(FileType t, fid_t id, int16_t n)
MetaFattr(FileType t, fid_t id, struct timeval mt, struct timeval ct, struct timeval crt, longlong c, int16_t n)

3.6 MetaChunkInfo

成員變量：

chunkOff_t offset;  //chunk在文件中的偏移
chunkId_t chunkId;  //chunk的標識符id
seq_t chunkVersion; //chunk的版本號

構造函數：

MetaChunkInfo(fid_t file, chunkOff_t off, chunkId_t id, seq_t v)
MetaChunkInfo(fid_t file, chunkOff_t off, chunkId_t id, seq_t v, CLVector &m)