动态散列目录扩展算法的研究  

Research on Index Expanding Algorithm in Dynamic Hash

作　　者：陈慧杰[1] 李建伟[1] 

机构地区：[1]太原科技大学计算机科学与技术学院,太原030024

出　　处：《太原科技大学学报》2013年第5期321-324,共4页Journal of Taiyuan University of Science and Technology

基　　金：山西省自然科学基金(2012011027-3)

摘　　要：为了分析分裂条件(桶溢出和存储利用率)和数据偏斜性对线性散列、可扩展散列、改进的动态散列目录增长的影响,对三种动态散列的目录扩展算法进行了研究。实验结果表明,在数据分布均匀的情况下,采用桶溢出分裂与采用存储利用率分裂相比较,三种动态散列目录增长速度较快,溢出桶数目较少;当采用存储利用率作为分裂条件时,三种数据分布偏斜情况对线性散列与可扩展散列的目录增长的影响相同。当采用桶溢出作为分裂条件时,数据分布越靠后端,线性散列目录增长越慢,改进的动态散列目录增长越快。In order to analyze the impact of split condition （bucket overflow and storage utilization）and data skew on the index size of the linear hash, the extendible hash and an improved dynamic hash, this paper studies the index extendible algorithm of the above dynamic hash. The experimental results show that the dynamic hash with bucket overflowing as the split condition has larger index size and fewer overflows bucket than that with storage utilization as the split condition in the case of data distribution uniform. Besides, when using the storage utilization as the split condition, the impacts of data skew on the linear hash and extendible hash are the same. When using the bucket overflow as split condition, the more data are in the back end of index, the linear hash has fewer index sizes and the improved dynamic hash has larger index size.

关 键 词：动态散列 数据偏斜性 分裂条件 目录尺寸 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]