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;
//
創建時間
long
long
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,
long
long
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)
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
