Hash表与B^+树相结合的高效目录索引结构  

An Effective Directory Index Framework Taking Advantages of Hash Table and B^+-Tree

作　　者：刘贤焯[1,2] 王劲林[1,2] 朱明[1] 邓峰[2] 孙鹏[2] 

机构地区：[1]中国科学技术大学自动化系,合肥230027 [2]中国科学院声学研究所网络新媒体中心,北京100190

出　　处：《西安交通大学学报》2013年第4期105-111,共7页Journal of Xi'an Jiaotong University

基　　金：国家"863计划"资助项目(2011AA01A102);国家科技支撑计划资助项目(2011BAH16B03);中国科学院重点部署项目(KGZD-EW-103-2)

摘　　要：针对目前文件系统目录结构在处理大量文件,尤其是单个大目录时文件创建、查找和删除速度较慢的问题,提出一种面向Web服务器存储系统的目录索引结构。该结构利用Hash函数对变长关键字的压缩特性和Hash表的O(1)查找复杂度进行文件名的快速查找,并使用B+树高效索引目录的子索引节点。测试结果表明,该结构能够快速地处理大量文件,单个大文件夹下的文件查找速度相比Ext3提高了40%,文件创建、删除速度比Ext3和Reiserfs加快了73%。A new directory index framework that takes the advantages of both hash functions and B＋-tree is proposed for storage system of Web server to solve the problem that existing directory indexing structures in file systems result in significant delays when they are used to process a large number of files or directories,especially when there are over hundreds of thousands of files in a single directory.The framework adopts hash functions to normalize file names with variable length to integers,thus file names can be found through a hash table in O（1） complexity.On the other hand,inode numbers of files in a directory are indexed by a B＋-tree with high fanout to support fast insertion or removing operations.Benchmark of a simple implementation reveals that the proposed framework can easily hand up to half a million files in a single directory,and can significantly improve performance,that is,its speed in searching entries is faster by at least 40% than Ext3,and in creating or deleting files is faster by at least 73% than Ext3 or Reiserfs.

关 键 词：文件系统 目录索引 哈希表 B+树 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论]