Hash表与B<sup>+</sup>树相结合的高效目录索引结构

刘贤焯 1; 王劲林 1; 2; 朱明 1; 邓峰 2; 孙鹏 2

doi:10.7652/xjtuxb201304018

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- Hash表与B⁺树相结合的高效目录索引结构
- An Effective Directory Index Framework Taking Advantages of Hash Table and B⁺-Tree
- 西安交通大学学报 2013年47卷第4期页码：105-111
- 作者机构：
  
  1. 中国科学技术大学自动化系,合肥,230027
  2. 中国科学院声学研究所网络新媒体中心,北京,100190
- 作者简介：
- 基金信息：
  
  : 2012-06-18。作者简介: 刘贤焯(1987—),男,博士生;王劲林(通信作者),男,研究员,博士生导师。基金项目: 国家“863计划”资助项目(2011AA01A102);国家科技支撑计划资助项目(2011BAH16B03);中国科学院重点部署项目(KGZD-EW-103-2)
- DOI：10.7652/xjtuxb201304018
  中图分类号： TP319
- 网络首发：2013-04-10，
  
  纸质出版：2013
- 稿件说明：
移动端阅览
刘贤焯 1, 王劲林 1, 2, 等. Hash表与B⁺树相结合的高效目录索引结构[J]. 西安交通大学学报, 2013,47(4):105-111. DOI: 10.7652/xjtuxb201304018.

An Effective Directory Index Framework Taking Advantages of Hash Table and B⁺-Tree[J]. 2013, 47(4): 105-111. DOI: 10.7652/xjtuxb201304018.
刘贤焯 1, 王劲林 1, 2, 等. Hash表与B⁺树相结合的高效目录索引结构[J]. 西安交通大学学报, 2013,47(4):105-111. DOI: 10.7652/xjtuxb201304018. DOI：

An Effective Directory Index Framework Taking Advantages of Hash Table and B⁺-Tree[J]. 2013, 47(4): 105-111. DOI: 10.7652/xjtuxb201304018. DOI：

摘要

针对目前文件系统目录结构在处理大量文件

尤其是单个大目录时文件创建、查找和删除速度较慢的问题

提出一种面向Web服务器存储系统的目录索引结构。该结构利用Hash函数对变长关键字的压缩特性和Hash表的O(1)查找复杂度进行文件名的快速查找

并使用B

树高效索引目录的子索引节点。测试结果表明

该结构能够快速地处理大量文件

单个大文件夹下的文件查找速度相比Ext3提高了40%

文件创建、删除速度比Ext3和Reiserfs加快了73%。

Abstract

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 direct

ory

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.

关键词

Keywords

references

AGRAWAL N, BOLOSKY W J, DOUCEUR J R, et al. A five-year study of file-system metadata [J]. ACM Transactions on Storage, 2007, 3(3): 1-32.

ZADOK E, BADULESCU I. Usenetfs: a stackable file system for large article directories [EB/OL].(2000-07-10)[2012-03-01]. http:∥www.cs.columbia.edu/～library/TR-repository/reports/reports-1998/ cucs-022-98.pdf.

PEARSON O. Squid: a user's guide [EB/OL]. [2012-03-05]. http:∥oss.org.cn/man/newsoft/squid/book-full-html/book-full.html.

Webmaster World. How to speed up directory reading? [EB/OL].(2008-03-05)[2012-03-06]. http:∥www.webmasterworld.com/apache/3592129.htm.

RÉMY C, THEODORE T, STEPHEN T. Design and implementation of the second extended file system [C]∥Proceedings of the First Dutch International Symposium on Linux. Amsterdam, Netherlands: State University of Groningen, 1994: 1-6.

PHILLIPS D. A directory index for Ext2 [C]∥Proceedings of the 5th annual Linux Showcase Conference. Oakland, California, USA: USENIX Association, 2001: 173-182.

BUCHHOLZ F. The structure of the Reiser file system [EB/OL].(2006-01-26)[2012-03-01]. http:∥homes.cerias.purdue.edu/florian/reiser/reiserfs.php.

Btrfs Project Group. Btrfs design [EB/OL]. [2012-03-01]. https:∥btrfs.wiki.kernel.org/index.php/Btrfs_design.

吴丽彬. 面向高清媒体的嵌入式存储系统MSFS关键技术的研究 [D]. 北京: 中国科学院研究生院, 2009.

BAEZA-YATES R A. Expected behaviour of B+-trees under random insertions [J]. Acta Informatica, 1989, 26(5): 439-471.

CHRISTIAN H, CARSTEN S, TANJA Z. Empirical evaluation of hash functions for multipoint measurements [J]. SIGCOMM Computer Communication Review, 2008, 38(3): 39-50.

COKER R. Bonnie++1.03e [EB/OL].(2008-12-10)[2012-03-04]. http:∥www.coker.com.au/bonnie++/.

MORREALE P W, VAN RIEL R. Linux documentation for/proc/sys/vm/* [EB/OL]. [2012-03-08]. http:∥www.kernel.org/doc/Documentation/sysctl/vm.txt.

浏览量

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

多工况下离心压气机叶轮-机匣一体联合设计优化

融合物理信息与深度算子网络的变压器绕组热-流场快速计算方法

采用试验设计方法的第三代CO2气体箔轴承箔片几何参数敏感性分析

采用机器学习的大规模并行程序I/O性能建模与预测方法

电动车辆间接热系统快速除湿响应迟滞机理及优化控制策略

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

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

DOI：10.7652/xjtuxb201304018

摘要

Abstract

关键词

Keywords

references

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

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