此處的KFS是指Kosmos distributed file system，代碼位于http://sourceforge.net/projects/kosmosfs/，之后會寫幾篇相關(guān)的文章，以供后來者參考。
KFS里Meta的內(nèi)存結(jié)構(gòu)主要是一棵B+樹，保存在內(nèi)存里，具體分析如下：
B-樹，B+樹的定義
關(guān)于這些樹的定義，最好還是參考算法導(dǎo)論等經(jīng)典書，網(wǎng)路上的信息有些不是很準(zhǔn)確，為了方便大家還是貼一個(gè)鏈接：
http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
KFS為何選用B+樹而非B樹？
這是我個(gè)人的理解：
雖然B樹可以在非葉子節(jié)點(diǎn)命中，會縮短一些平均查找長度，但是B+樹在這種應(yīng)用一個(gè)優(yōu)勢就是每個(gè)節(jié)點(diǎn)都有指向next節(jié)點(diǎn)的指針，對于范圍查詢或者遍歷操作很適合。對于文件系統(tǒng)的一個(gè)ls某個(gè)子目錄的需求，用B+樹可以較高效的解決。
KFS里B+樹的類圖
MetaNode：base class for both internal and leaf nodes
Meta：base class for data objects (leaf nodes)
Node：an internal node in the KFS search tree
MetaChunkInfo：chunk information for a given file offset
MetaDentry ：Directory entry, mapping a file name to a file id
MetaFattr：File or directory attributes
各節(jié)點(diǎn)的介紹
（1）Meta類是子節(jié)點(diǎn)的父類，其最主要的成員變量是fid
有三個(gè)葉子節(jié)點(diǎn)：MetaChunkInfo，MetaDentry，MetaFattr
（2）MetaDentry：實(shí)現(xiàn)從文件名到fid的映射，對于每個(gè)文件（目錄）都擁有1個(gè)MetaDentry
成員變量包括：
dir：文件父目錄的fid
name：dentry的名稱，實(shí)際就是文件名
（3）MetaFattr：實(shí)現(xiàn)從fid到文件屬性的映射，對于每個(gè)文件（目錄）都擁有一個(gè)MetaFattr。
成員變量包括：
Type：文件還是目錄
numReplicas：文件有幾份副本
mtime：修改時(shí)間
ctime：屬性修改時(shí)間
crtime：文件創(chuàng)建時(shí)間
chunkcount：連續(xù)的chunk數(shù)目
filesize：文件大小
nextChunkOffset：最后一個(gè)chunk在文件的所處的offset
mode_t mode：文件屬性（rwx位）
key：由KFS_FATTR，fid來構(gòu)成，可以通過fid直接找到保存文件屬性的節(jié)點(diǎn)。
（4）MetaChunkInfo：標(biāo)志某個(gè)文件對應(yīng)的chunk信息，如果一個(gè)文件包含多個(gè)chunk，那么需要有多個(gè)MetaChunkInfo。
成員變量包括：
offset：chunk在文件中的偏移量，因?yàn)橐粋€(gè)文件可能由多個(gè)chunk組成
chunkId：chunk的id號
chunkVersion：chunk的version值
（5）Node：實(shí)現(xiàn)的是B+樹的內(nèi)部節(jié)點(diǎn)，這種節(jié)點(diǎn)僅僅作為索引用途，存儲實(shí)際元數(shù)據(jù)信息的節(jié)點(diǎn)位于最底部的葉子節(jié)點(diǎn)。
成員變量包括：
NKEY = 32：每個(gè)節(jié)點(diǎn)最多擁有的關(guān)鍵字?jǐn)?shù)目，實(shí)際上也就是最多擁有的子節(jié)點(diǎn)數(shù)目，如果多余這個(gè)值節(jié)點(diǎn)進(jìn)行分裂
NSPLIT = NKEY / 2：分裂之后每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目
NFEWEST = NKEY - NSPLIT：每個(gè)節(jié)點(diǎn)最少擁有的關(guān)鍵字?jǐn)?shù)目，如果少于這個(gè)值兩個(gè)節(jié)點(diǎn)進(jìn)行合并
count：節(jié)點(diǎn)實(shí)際擁有的關(guān)鍵字?jǐn)?shù)目
Key childKey[NKEY]：節(jié)點(diǎn)存儲的關(guān)鍵字列表
MetaNode *childNode[NKEY]：節(jié)點(diǎn)指向子節(jié)點(diǎn)的指針列表
Node *next：指向下一個(gè)同級節(jié)點(diǎn)的指針
實(shí)際上每個(gè)內(nèi)部節(jié)點(diǎn)的階數(shù)為32，可以有32個(gè)子節(jié)點(diǎn)，而每個(gè)葉子節(jié)點(diǎn)只保存一個(gè)key值。
三類子節(jié)點(diǎn)在B+樹中如何分布？
可以想象，必定是將同一類的節(jié)點(diǎn)聚集在一起。因此對于排序函數(shù)就是先比較節(jié)點(diǎn)類型，然后再對節(jié)點(diǎn)內(nèi)部的成員變量進(jìn)行比較。MetaDentry是根據(jù)dir（父目錄的id），MetaFattr是根據(jù)fid，MetaChunkInfo是根據(jù)id和chunkId來排序。
一個(gè)不太相關(guān)的思考
看上面的三類子節(jié)點(diǎn)，我們可以發(fā)現(xiàn)chunk的位置信息并沒有保存在B+樹里，它是單獨(dú)保存在一個(gè)Map數(shù)據(jù)結(jié)構(gòu)里的，也不會在meta server里進(jìn)行持久化，而是每次chunk啟動時(shí)向meta server來報(bào)告。之所以不做持久化，可以這樣來理解：
只有Chunk服務(wù)器才能最終確定一個(gè)Chunk是否在它的硬盤上。Chunk服務(wù)器的錯(cuò)誤可能會導(dǎo)致Chunk自動消失(比如，硬盤損壞了或者無法訪問了)，亦或者操作人員可能會重命名一個(gè)Chunk服務(wù)器，還是由chunk server來報(bào)告比較靠譜。