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)
