云计算环境中高效可扩展的元数据管理方法*

黄 斌，彭宇行

(1.贵州师范大学数学与计算机科学学院，贵州 贵阳 550001；2.武汉大学计算机学院，湖北 武汉 430072；3.国防科学技术大学计算机学院，湖南 长沙 410073)

云计算环境中高效可扩展的元数据管理方法*

黄 斌1,2，彭宇行3

(1.贵州师范大学数学与计算机科学学院，贵州 贵阳 550001；2.武汉大学计算机学院，湖北 武汉 430072；3.国防科学技术大学计算机学院，湖南 长沙 410073)

针对现有可扩展的元数据管理方法存在性能较低问题，提出一种高效可扩展的元数据管理方法，它首先采用动态二叉映射树来实现元数据服务器精确定位，然后采用延迟更新方法来动态更新二叉映射树，最后提出动态K叉编码树的元数据组织方法以提高元数据服务器扩展时选择迁移元数据的速度。实验结果表明，它有效提高了云计算环境中可扩展元数据管理方法的效率。

云计算；元数据；高效；可扩展

1 引言

随着互联网应用和数据密集型计算的流行，云计算环境中出现了许多新的应用系统。这些系统与传统分布式系统的不同之处是：系统中存储的文件数量巨大，有的甚至将要达到万亿(Trillions)级别[1～3]，并且还在以较快速度增加。据统计：截止2011年2月，Facebook[4]存有600亿张照片，Photobucket[5]存有90亿张照片，谷歌的Picasa[6]存有70亿张照片，Flickr[7]存有60亿张照片，并且这些系统中的文件数量增长非常迅速(如Facebook目前每天有上亿张图片上传，Photobucket目前每天有400万张图片上传)，因此不久的将来系统中的文件数将达到万亿级别[3]。一些地理信息系统存储了数十亿张卫星照片[3]，如美国的巡天项目(LSST)[8]目前存有9×1019张图片。如此海量的文件数导致可扩展性成为存储系统有效应用的一个瓶颈。元数据方式是实现海量存储系统的一种重要方法。云计算系统的海量文件造成其元数据也海量，解决的元数据可扩展性问题也就解决了海量存储系统的可扩展性问题，因此元数据的有效管理成为解决云计算环境中海量文件可扩展存储的关键技术。

现有的元数据管理方法分为查表法、子树分割法、静态哈希法和可扩展哈希法。查表法[9～11]在云计算系统中的典型应用是Google使用的单元数据服务器MDS(Meta Data Server)方法。该方法将元数据以表格形式存储在一台服务器的内存中，适合文件数量不多的存储系统，其扩展能力不强，不适合文件数海量且快速增长的存储系统。子树分割法[12～16]将存储系统全局唯一的名字空间按照目录层次分割为独立的子树，元数据服务器集群中的每个元数据服务器负责管理其中的一个或多个子树。该方法可扩展性较好，但由于目录分布在多台元数据服务器中，需要跨多台元数据服务器进行目录遍历来定位文件的元数据，导致访问效率低效。静态哈希法[17～25]是对文件标识符(如文件全路径名)进行哈希来定位该文件的存储位置。该方法突破了单元数据服务器个数的限制，但它在扩展时需要重新分布所有元数据，使得元数据服务器不能随文件数目的增加而动态扩展。可扩展哈希法[1～3,26,27]把文件标识符分成标识元数据服务器字段和标识服务器内数据块字段，通过扩展元数据服务器字段来动态地增加元数据服务器，实现元数据系统动态可扩展，并且扩展时只迁移分裂元数据服务器一半左右的元数据。该方法在系统扩展时需要进行元数据迁移，其确定哪些数据迁移的速度较慢，并采用消息广播方式定位元数据，造成系统服务性能较低。

针对现有可扩展元数据管理方法存在性能较低问题，本文提出一种高效可扩展的元数据管理方法，它包括精确定位可扩展哈希方法、缓冲区延迟更新方法、高效确定迁移数据的元数据组织方法，有效解决了元数据管理高效可扩展问题。

本文贡献主要包括：(1)针对现有可扩展哈希方法定位数据时采用访问请求广播方式，容易造成网络拥挤这一问题，提出了精确定位可扩展哈希方法，有效降低了系统中的通信量，提高了访问性能；(2)针对精确定位可扩展哈希的特点，提出了基于元数据服务器分裂日志的缓冲区延迟更新方法，把总的更新开销分摊到各个操作中，避免缓冲区更新操作对系统性能产生较大波动；(3)针对现有可扩展哈希方法采用的元数据组织方法(如堆、线性哈希等)造成元数据服务器扩展时，选择迁移元数据速度慢这一问题，提出了动态K叉编码树元数据组织方法，有效地提高了选择迁移元数据速度。

2 精确定位可扩展哈希方法

可扩展哈希能较好地支持元数据存储系统动态扩展，其原理是把文件的标识符(记为FID)哈希成m位二进制值hash(FID)，hash(FID)的i位前缀值a0a1…ai-1相同的文件元数据被分布到同一台元数据服务器中(a0a1…ai-1称为该元数据服务器的数据标识符，i称为数据标识符长度)。当数据标识符为a0a1…ai-1的元数据服务器容量不够时，分裂该元数据服务器，分裂规则是：将hash(FID)前缀为a0a1…ai-11元数据迁移到新增的元数据服务器中，hash(FID)前缀为a0a1…ai-10元数据仍保留在原元数据服务器中，此时前者的数据标识符变为a0a1…ai-11，后者的数据标识符变为a0a1…ai-10，两者的数据标识符长度增加1。可扩展哈希原理如图1所示。

Figure 1 Extensible hash图1 可扩展哈希

访问一个文件元数据时,把文件的标识符(FID)哈希成m位二进制值hash(FID)，把访问请求广播到所有元数据服务器中，元数据服务器依据它的数据标识符长度i，取hash(FID)前i位值a0a1…ai-1与元数据服务器的数据标识符进行比对，如两者相同，说明要访问的元数据在该元数据服务器中，则做进一步访问，否则忽略该访问请求。

Figure 2 Extensible hash with precise location图2 精确定位可扩展哈希

在数据访问时，传统的可扩展哈希需要把访问请求广播到所有存储节点中，造成网络拥挤，因而影响系统性能。针对这一问题，我们提出精确定位可扩展哈希方法(如图2所示)，它在可扩展哈希中引入动态二叉映射树来实现访问请求的点对点通信，降低通信量，提高访问性能。

动态二叉映射树位于客户端，是元数据服务器地址的一棵编码树，它的每个左分支代表0，右分支代表1，每个叶子节点代表一台元数据服务器。从根节点到一个叶子节点的所有分支组成的编码就是一台元数据服务器的地址，对应于一个叶子节点的编号。在数据访问时，只需从hash(FID)第一位起，在二叉映射树中逐位向下搜索，搜索到叶子节点，就得到数据存储位置。

动态二叉映射树具有如下特点：(1)动态二叉映射树是随着元数据服务器的分裂而动态生成的。当一个元数据服务器a0a1…ai分裂为a0a1…ai0和a0a1…ai1时，动态二叉映射树中对应节点a0a1…ai也相应地产生a0a1…ai0和a0a1…ai1两个孩子节点。(2)通常元数据服务器数量较少，因此动态二叉映射树不高，定位元数据服务器效率也就比较高。

3 延迟更新方法

当一个元数据服务器分裂时，如果采用同步更新方法，更新操作对系统性能影响较大，因此我们采用延迟更新方法，把总的更新开销分摊到各个操作中，避免动态二叉映射树更新操作对系统性能产生较大波动。其具体方法是：

(1)给每一个元数据服务器赋予两个地址：物理地址和逻辑地址，物理地址在服务器生命周期内不变，如服务器的IP地址；而逻辑地址是随着元数据服务器分裂而改变的地址，动态二叉映射树分支编码构成的地址是逻辑地址。

(2)在动态二叉映射树中，每个叶子节点都记录了逻辑地址到物理地址的映射关系，以方便服务器的定位。

(3)在每个元数据服务器中设计一个分裂日志，记录该服务器的分裂历史，它是一个二维表，它的每行记录结构是〈逻辑地址，物理地址〉。例如，服务器a0a1…ap经过w次分裂后，它的分裂日志如图3所示。分裂日志的第j行表明以a0a1…apap+j为首部的元数据存放在物理地址为IPj的元数据服务器中，其逻辑地址为a0a1…apap+j。

分裂序号物理地址a0a1…apap+1IP1︙︙a0a1…ap+wIPw

Figure3Splittinglogofservera0a1…ap

图3 服务器a0a1…ap的分裂日志

(4)假设一个服务器的逻辑地址为a0a1…ax,物理地址为IPm。当一个访问请求q(将访问的元数据服务器逻辑地址a0a1…ai，物理地址为IPn)到达元数据服务器IPm时，如果x=i,则直接在该服务器完成操作；如果x>i，那么将访问该节点的分裂日志，将访问请求转交到相应的服务器中，并根据节点的分裂日志来更新客户端的动态二叉映射树。根据节点的分裂日志更新客户端的算法为：

对服务器端：

将〈IPi, IPi+1,…,IPn〉发给流出访问请求q的客户端;

对客户端:

p= a0a1…ai;

For:j从1到n

P.lchild.laddress=a0a1…ai0…0;//j 个0

P.lchild.paddress=IPm;

P.rchild.laddress=a0a1…ai1…1;//j个1

P.rchild.paddress=IPi+j-1;

P=a0a1…ai0…0;//j 个0

从算法中可以看出，在一客户端二次访问服务器x 期间，如果服务器x分裂w次，那么只需在该客户端对应的节点增加w层二叉树，因此更新成本较低。

4 元数据组织方法

随着元数据不断增长，当服务器容量不够时，每台元数据服务器分裂为两台元数据服务器(编号为a0a1…ai-1的元数据服务器分裂后编号变为a0a1…ai-10，新增加的元数据服务器编号为a0a1…ai-11)，同时每台元数据服务器选择hash(FID)的ai=1的文件元数据迁移到新增的元数据服务器中，单台服务器分裂示意图如图4所示，数据重分布如图5所示。

Figure 4 Splitting of MDS a0a1…ai-1图4 元数据服务器分裂

Figure 5 Distribution of directory metadata图5 目录元数据在元数据服务器的分布

随着数据的不断插入，服务器的分裂过程是以a0a1…ai-1为根的二叉树，数据分裂过程也是一个二叉树。因此，可以预先以每次分裂位的值(为0或为1)对hash(FID)构建二叉树索引(如图6所示)，减少数据选择时间。构造二叉树索引以后，在每次分裂时选择右分支迁移即可，执行速度快，但是查询数据时，查询访问的层次高，执行速度较慢。

Figure 6 Binary tree index图6 二叉树索引

针对这一缺点，我们对文件元数据索引树进行改进，提出动态K叉编码树方法，有效减少查询操作的树的遍历次数，同时仍保持选择迁移的文件元数据速度快的优点。其基本思想：

(1)在数据服务器中(设元数据服务器的编号为a0a1…ai-1)，将m位的hash(FID)的后m-i位分成h个分段(如图7所示)，第一段长度用n表示，其余各段长度为n0(n0是由系统配置的固定值)。n的值随服务器分裂而动态变化，其值n=m-i-(h-1)×n0，分段数h=(m-i/m0)，由此可见h也随i而动态变化。

Figure 7 Segmented diagram of hash(FID)图7 hash(FID)分段图

(2)对于一个具有n0位二进制数的编码段，它有k=2n0个值。因此，对于某一个编码段的一个值，在下一个编码段中有k=2n0个对应值，前后段值之间的对应关系形成了一个K叉编码树，如图8所示。树中的叶子节点的指针指向一个目录的文件元数据块；树中的分支节点的每个数组元素代表具有相同的二进制前缀目录。从树的根节点遍历到一个叶子节点得到的m-i位二进制代码，是一个文件标识符哈希值hash(FID)的后m-i位，加上服务器编码a0a1…ai-1得到m位二进制编码，它是一个文件标识符的hash(FID)。

文件元数据的动态K叉编码树组织方法具有如下特性：

(2)它预先按元数据服务器所有可能分裂过程对文件元数据进行分类，分裂执行速度快。因为在动态K叉编码树表示树根的指针数组中，以第2n-1个元素(1/2处)为界，它左边的所有数组元素的序号编码第一位是0，右边的所有数组元素的序号编码第一位是1，这个刚好是下一次分裂所需的数据划分；同样，在第2n-2、3*2n-2数组元素两边，元素编号编码左第二位是0，右第二位是1，这刚好是第二次分裂时所需的数据划分；以此类推。将数组对半分割后，由于每个数组元素数量减少一半，因此数组元素的序号编码减少一位，自然地去掉了前面一位。

Figure 8 Dynamic K-tree for code图8 动态K叉编码树

(3)数据偏斜不影响系统性能。在一个元数据系统，对于两个数据量相同的数据集来说，它们需要的元数据服务器数量一样，也就是说元数据服务器编址长度i值相同。另外，m是由选择的hash算法决定，n0由系统配置，二者都是固定值，因而它们的hash(FID)分段数h=(m-i)/n0也相同，即K叉编码树的高度相同，由此可知，不管数据偏斜与否，一个元数据在K叉编码树的搜索次数是相同的。

例如，有八个元素的数组如图9所示，在第四个元素左右两边第一位分别为0，在第二、六个元素左右二边第一位分别为0，经过两次分裂得到四个数组。

Figure 9 Splitting process of the array with 9 elements图9 含有九个元素的数组分裂过程

由于指针数组很自然地把数据块分类，每次分裂时只要选择指针数组中前一半或后一半数组元素所指的数据块即可。

5 实验与性能分析

5.1 实验环境

实验在四个机柜中的126台计算机中完成，这些机器通过吉比特以太交换机连接成网络，机柜内的对半带宽约为14 Gbps, 机柜之间的对半带宽约为6.5 Gbps。每台计算机有两个2.8 GHz英特尔至强CPU、4 GB内存、两个每分钟10 000转SCSI硬盘。所有计算机运行内核版本为2.6.9的Red Hat Enterprise Linux AS 4.0。

MDS和客户机均采用Java语言编写，并且分别运行在不同的机器中。系统初始时，每个MDS存有20万条元数据。

5.2 实验结果与分析

5.2.1 系统整体性能评估

在系统整体性能评估中，测试了系统在稳定状态和扩展状态的性能。测试系统在稳定状态性能以评估系统在不同规模下的性能变化情况；而测试系统在扩展状态下的性能，以评估系统扩展对性能的影响。为了强调我们方法在选择迁移数据方面的优越性，还进行了查找迁移数据效率实验。

(1)无MDS分裂的元数据操作性能。

这组实验中，客户端对MDS进行各种元数据操作，测试在没有元数据服务器分裂情况下元数据服务的性能。为了进行性能对比，我们同时实现了可扩展哈希方法(记为EH)和我们的高效可扩展的元数据管理方法(记为EEH)。实验过程中，所有客户机均运行四个线程并发访问MDS，测试不同服务器规模下单位时间内完成的元数据操作数。其结果如图10所示。

Figure 10 Operation performance of metadata图10 元数据操作性能

从图10中可以看出：①EEH的性能明显优于 EH，这是因为EEH采用精确定位方式，而EH采用广播式定位，较多广播消息影响系统性能。②随着MDS的增加，二者性能都增加，但二者的性能增长率均逐渐下降，这是因为MDS增加，系统服务客户的数量增加。但是，客户增加后，对EH来说，广播消息更多，每台MDS花费更多的处理能力来处理无用的广播消息，因而系统的有效服务能力下降；对EEH来说，MDS分裂加快，更新客户端缓冲区的速度加快，从而系统的有效服务能力也有所下降。③随着MDS的增加EH的性能增长率比EEH慢，这是因为较多的广播消息影响EH的性能。

(2) 查找迁移数据效率。

在该测试中，同时实现了线性哈希元数据组织方法，以用来与动态K叉编码树方法做可扩展性效率对比，选择线性哈希方法来与动态K叉编码树方法做性能对比的原因是因为现有很多系统都采用它来组织元数据[22,23]。因为两个方案的查找性能在每台元数据服务器上都很相近，因此我们测试二者在一台元数据服务器中不同对象(文件和目录)数的查找性能(测试的对象元数据按两种组织方式进行组织，并缓冲在内存中)，其测试结果如表1所示。从表1中可以看出，线性哈希法查找时间比较长，并且随目录数增加而增长，动态K叉编码树方法查找时间非常小，几乎为零，并且不随目录数而变化。

Table 1 Compare of extension efficiency表1 系统扩展效率对比

(3)MDS分裂对元数据操作性能影响。

该组实验测试MDS从四台变化为五台过程中系统的性能。同样，为了进行性能对比，我们同时实现了EH和EEH。实验过程中，所有客户机均运行四个线程并发访问MDS，测试不同时刻完成的元数据操作数。结果如图11所示。从图11中可以看出，在MDS分裂过程中，EH和EEH的性能均略有下降，这是因为MDS 分裂需要查找和迁移数据，从而引起系统性能下降，但EH受到的影响时间较长，这是因为在EH中查找迁移数据较长。

Figure 11 Effect of metadata operation performance by MDS splitting图11 MDS分裂对元数据操作性能影响

5.2.2 参数m和n0对系统性能的影响

(1)参数n0对系统性能的影响。

这一组实验测试m=128，n0取不同值时系统访问性能。n0每取一个不同值，数据就重新组织一次，然后测试查询数据的时间。在每次实验过程中，数据规模均为20万条，缓冲区设为600 MB。测试结果分别如图12所示。从图12中可以看出，随着n0逐渐增加，查询时间先逐渐减少，然后逐渐增加，这是因为：①在n0≤8时，K叉树节点均缓冲到缓冲区中，随着n0增加，树的高度逐渐减小，因而查询时间减少。②在n0>8时，一些节点数据存储在磁盘中，访问时要从磁盘读到缓冲区,n0越大，需要的存储量越大，读到内存时间就越多。

Figure 12 Effection of the system performance by n0图12 n0对系统性能影响

(2)参数m对系统性能的影响。

这一组实验中，测试n0=8、m取不同值时系统的性能，实验过程中，数据规模仍均为20万条，缓冲区设为600 MB。测试结果如图13所示。从图13中可以看出,在n0为固定值时，查询时间随着m的增加而逐渐增大。这是因为n0为固定值时，m增大，树的高度增加。

Figure 13 Effection of the system performance by m图13 m对系统性能影响

6 结束语

本文提出了一种高效可扩展的元数据管理方法，有效解决了云计算环境中元数据管理高效可扩展问题。它具有以下优点：(1)与查询表法和静态哈希方法相比，它实现了系统动态扩展；(2)与可扩展哈希方法相比，它能精确地进行数据定位和快速选择需要迁移的元数据，提高了系统性能和扩展效率。

[1] Patil S V, Gibson G. Giga+:Scalable directories for shared file systems[EB/OL].[2008-12-15].http://highscalability.com/flickr-architecture.

[2] Patil S V, Gibson G, Lang S,et al. Giga+:scalable directories for shared file systems[C]∥Proc of the 2nd International Workshop on Petascale Data Storage, 2007:26-29.

[3] Xing Jing,Xiong Jin,Sun Ning-hui,et al. Adaptive and scalable metadata management to support a trillion files[C]∥Proc of SC’09, 2009:1-11.

[4] Vajgel P. Needle in a haystack:Efficient storage of billions of photos[EB/OL].[2009-11-15].http://www.facebook.com/note.php?note_id=76191543919.

[5] http://www.photobucket.com/.

[6] http://picasa.google.com/.

[7] Hoff T. Flickr architecture[EB/OL].[2009-11-15].http://highscalability.com/flickr-architecture.

[8] Large synoptic survey telescope. http://www.lsst.org/lsst, 2008.

[9] Ghemawat S, Gobioff H,Leung S T.The Google file system[J].ACM SIGOPS Operating Systems Review,2003,37(5):29-43.

[10] Shvachko K, Kuang H, Radia S, et al. The Hadoop distributed file system [C]∥Proc of NASA/IEEE Conference on Mass Storage Systems and Technologies (MSST), 2010:6-16.

[11] Braam P J.The Lustre storage architecture[EB/OL].[2004-12-15].http://www.lustre.org/docs/lustre.pdf.

[12] Pawlowski B,Juszczak C,Staubach P,et al. NFS version 3:Design and implementation[C]∥Proc of the Summer 1994 USENIX Conference, 1994:137-151.

[13] Morris J H,Satyanarayanan M,Conner M H,et al. Andrew:A distributed personal computing environment[J].Communications of the ACM,1986,29(3):184-201.

[14] Satyanarayanan M, Kistler J J, Kumar P, et al. Coda:A highly available file system for a distributed workstation environment[J].IEEE Transactions on Computers,1990,39(4):447-459.

[15] Ousterhout J K,Cherenson A R,Douglis F,et al.The sprite network operating system[J].IEEE Computer,1988,21(2):23-36.

[16] Weil S A,Pollack K T,Brandt S A,et al. Dynamic metadata management for petabyte-scale file systems[C]∥Proc of the 2004 ACM/IEEE Conference on Supercomputing, 2004:523-534.

[17] Corbett P F,Feitelson D G.The Vesta parallel file system[J].ACM Transactions on Computer Systems,1996,14(3):225-264.

[18] Braam P J,Callahan M,Schwan P,et al.The InterMezzo file system[C]∥Proc of the 3rd Perl Conference,1999:1.

[19] Miller E L,Katz R H.RAMA:An easy-to-use,high-performance parallel file system[J].Parallel Computing,1997,23(4):419-446.

[20] Rodeh O,Teperman A.zFS—a scalable distributed file system using object disks[C]∥Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies, 2003:207-218.

[21] Brandt S A, Xue L, Miller E L, et al. Efficient metadata management in large distributed file systems[C]∥Proc of the 20th IEEE/11th NASA Goddard Conference on Mass Storage Sysetms and Technologies,2003:290-298.

[22] Liu Z. Research on scalable cluster storage system based on object storage architecture[D]. Changsha:National University of Defense Technology,2005.(in Chinese)

[23] Liu Z, Zhou X M. A metadata management method based on directory path[J]. Journal of Software, 2007, 18(2):236-245.(in Chinese)

[24] Wang Juan. Research on metadata management in object-based storage system[D]. Wuhan:Huazhong University of Science & Technology,2010.(in Chinese)

[25] Wang Juan,Feng Dan,Wang Fang, et al.MHS:A distributed metadata management strategy[J].The Journal of Systems and Software, 2009,82(12),2004-2011.

[26] Fagin R, Nievergelt J, Pippenger N, et al. Extendible hashing:A fast access method for dynamic files[J]. ACM Transactions Database System, 1979,4(3):315-344.

[27] Schmuck F, Haskin R. GPFS:A shared-disk file system for large computing clusters[C]∥Proc of the Conference on File and Storage Technologies, 2002:1.

附中文参考文献:

[22] 刘仲. 基于对象存储结构的可伸缩集群存储系统研究[D]. 长沙:国防科学技术大学, 2005.

[23] 刘仲，周兴铭.基于目录路径的元数据管理方法[J].软件学报,2007,18(2):236-245.

[24] 王娟. 对象存储系统中元数据管理研究[D]. 武汉：华中科

技大学, 2010.

HUANGBin,born in 1971,PhD,associate professor,his research interests include cloud computing, mass data storage, analysis and processing of large data.

彭宇行(1963-),男，湖南长沙人，博士，研究员，研究方向为多媒体信息处理、并行与分布式计算。E-mail:

PENGYu-xing,born in 1963,PhD,research fellow,his research interests include multimedia information processing, parallel and distributed computing.

Anefficientscalablemetadatamanagementmethodincloudcomputing

HUANG Bin1,2,PENG Yu-xing3

(1.School of Mathematics and Computer Science,Guizhou Normal University,Guiyang 550001；2.School of Computer,Wuhan University,Wuhan 430072；3.College of Computer,National University of Defense Technology,Changsha 410073,China)

Aiming at the lower performance problem of the existing metadata management methods in cloud computing,an efficient scalable metadata management method is proposed in cloud computing.Firstly,a dynamic binary mapping tree is used to achieve the precise positioning of the metadata server.Secondly,a lazy update technique is adopted to dynamically update the binary mapping tree.Finally,a dynamic K tree is proposed to improve the speed of selecting migrated metadata during MDS splitting.The experimental results show that the method can effectively improve the efficiency of the scalable metadata management method in cloud computing.

cloud computing;metadata;efficient;scalable

1007-130X(2014)08-1447-08

2013-12-12;

：2014-04-03

国家973 计划资助项目(2011CB302601)；国家863计划资助项目(2011AA01A202)；湖南省科技计划资助项目(2013FJ4335,2013FJ4295)

TP393

：A

10.3969/j.issn.1007-130X.2014.08.005

符时，我们才在K叉编码树中建立对应分支，否则它是一个空子树，不需要为它分配节点空间。例如，在图8中，根节点t的1…10值没有分支，节点q中除0…01值外，其余值都没有分支。当插入一个hash(FID)中ai…ai+n-1为1…10的文件元数据时，就会建立一个以1…10为根的子树。节点的分支数随文件元数据的插入而动态变化，因此，K叉编码树是一个动态树。

黄斌(1971-),男，湖南溆浦人，博士，副教授，研究方向为云计算、大规模数据存储、大数据分析与处理。E-mail:1059564040@qq.com

通信地址：550001 贵州省贵阳市贵州师范大学数学与计算机科学学院

Address:School of Mathematics and Computer Science,Guizhou Normal University,Guiyang 550001,Guizhou,P.R.China