An Effective Directory Index Framework Taking Advantages of Hash Table and B<sup>+</sup>-Tree

doi:10.7652/xjtuxb201304018

您当前的位置：

首页 >

文章列表页 >

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

更新时间：2025-07-09

- An Effective Directory Index Framework Taking Advantages of Hash Table and B⁺-Tree
- Vol. 47, Issue 4, Pages: 105-111(2013)
- 作者机构：
  
  1. 中国科学技术大学自动化系,合肥,230027
  2. 中国科学院声学研究所网络新媒体中心,北京,100190
- 作者简介：
- 基金信息：
- DOI：10.7652/xjtuxb201304018
  CLC： TP319
- Online First：10 April 2013，
  
  Published：2013
- 稿件说明：
移动端阅览
An Effective Directory Index Framework Taking Advantages of Hash Table and B⁺-Tree[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.

Views

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Bi-Level Multi-Obj ective Optimization of a Wind-Solar Coupled Hydrogen Production System Based on the Synergy of Hybrid Electrolyzer Arrays

Diffusion Characteristics and Influencing Factors in Case of Hydrogen Leakage from Fuel Cell Vehicles Running in Tunnels

Knowledge Graph Representation Learning Driven by Semantic Discrimination and Subgraph Integration

Windage Loss and Flow Characteristics in Impeller Back Gaps of sCO2 Radial Inflow Turbines

Sensitivity Analysis of Foil Geometrical Parameters for the Third-Generation CO2 Gas Foil Bearings Based on Design of Experiments Method

Related Author

No data

Related Institution

No data

⁰

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

DOI：10.7652/xjtuxb201304018

摘要

Abstract

关键词

Keywords

references

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