此处的KFS是指Kosmos distributed file system，代码位于http://sourceforge.net/projects/kosmosfs/，之后会写几篇相关的文章，以供后来者参考。
KFS里Meta的内存结构主要是一棵B+树，保存在内存里，具体分析如下：
B-树，B+树的定义
关于这些树的定义，最好还是参考算法导论等经典书，网路上的信息有些不是很准确，为了方便大家还是贴一个链接：
http://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
KFS为何选用B+树而非B树？
这是我个人的理解：
虽然B树可以在非叶子节点命中，会缩短一些平均查找长度，但是B+树在这种应用一个优势就是每个节点都有指向next节点的指针，对于范围查询或者遍历操作很适合。对于文件系统的一个ls某个子目录的需求，用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
各节点的介绍
（1）Meta类是子节点的父类，其最主要的成员变量是fid
有三个叶子节点：MetaChunkInfo，MetaDentry，MetaFattr
（2）MetaDentry：实现从文件名到fid的映射，对于每个文件（目录）都拥有1个MetaDentry
成员变量包括：
dir：文件父目录的fid
name：dentry的名称，实际就是文件名
（3）MetaFattr：实现从fid到文件属性的映射，对于每个文件（目录）都拥有一个MetaFattr。
成员变量包括：
Type：文件还是目录
numReplicas：文件有几份副本
mtime：修改时间
ctime：属性修改时间
crtime：文件创建时间
chunkcount：连续的chunk数目
filesize：文件大小
nextChunkOffset：最后一个chunk在文件的所处的offset
mode_t mode：文件属性（rwx位）
key：由KFS_FATTR，fid来构成，可以通过fid直接找到保存文件属性的节点。
（4）MetaChunkInfo：标志某个文件对应的chunk信息，如果一个文件包含多个chunk，那么需要有多个MetaChunkInfo。
成员变量包括：
offset：chunk在文件中的偏移量，因为一个文件可能由多个chunk组成
chunkId：chunk的id号
chunkVersion：chunk的version值
（5）Node：实现的是B+树的内部节点，这种节点仅仅作为索引用途，存储实际元数据信息的节点位于最底部的叶子节点。
成员变量包括：
NKEY = 32：每个节点最多拥有的关键字数目，实际上也就是最多拥有的子节点数目，如果多余这个值节点进行分裂
NSPLIT = NKEY / 2：分裂之后每个节点的关键字数目
NFEWEST = NKEY - NSPLIT：每个节点最少拥有的关键字数目，如果少于这个值两个节点进行合并
count：节点实际拥有的关键字数目
Key childKey[NKEY]：节点存储的关键字列表
MetaNode *childNode[NKEY]：节点指向子节点的指针列表
Node *next：指向下一个同级节点的指针
实际上每个内部节点的阶数为32，可以有32个子节点，而每个叶子节点只保存一个key值。
三类子节点在B+树中如何分布？
可以想象，必定是将同一类的节点聚集在一起。因此对于排序函数就是先比较节点类型，然后再对节点内部的成员变量进行比较。MetaDentry是根据dir（父目录的id），MetaFattr是根据fid，MetaChunkInfo是根据id和chunkId来排序。
一个不太相关的思考
看上面的三类子节点，我们可以发现chunk的位置信息并没有保存在B+树里，它是单独保存在一个Map数据结构里的，也不会在meta server里进行持久化，而是每次chunk启动时向meta server来报告。之所以不做持久化，可以这样来理解：
只有Chunk服务器才能最终确定一个Chunk是否在它的硬盘上。Chunk服务器的错误可能会导致Chunk自动消失(比如，硬盘损坏了或者无法访问了)，亦或者操作人员可能会重命名一个Chunk服务器，还是由chunk server来报告比较靠谱。