基于访问频率的Hash树

A Hash Tree Based on Frequency of Data Accessed

Hash树是一种常用的数据结构。当Hash树不能完全装入内存时,会增加缺页中断次数,导致算法效率下降,为此本文研究并提出了根据项集的联合概率生成Hash树的方法。按访问频率将Hash树结点数据顺序地排放在线性空间中。这种数据存储方式既能适应操作系统中的程序局部性特征,又能达到减少I/O次数、提高数据存取效率的目的。

Hash tree is a data structure that is used frequently.But if the nodes of the tree are not fully loaded into the main memory,the hashbased algorithm becomes not effective due to the increasing of interrupts of paging faults.In this paper,a method for hash tree generation based on the joint probability of item set is presented.The data is arranged sequentially in linear space according to the access frequency.Such data storaging mode can either adapt the program local character feature of operating system or acheiving the objective for reducing the I/O operations and enhancing the data access efficiency.The result of experiments showed that the optimized hash tree performed better.