When a database system involves volumes of data too large to be stored in main memory, the database system suffers a well-known problem of I/O bottleneck. One of the promising solutions is to reduce search space and consequently the number of I/O requests. Hashing methods have been found to be one of the useful access methods for physical database systems implementation. In recent years, several methods have been proposed to extend the applicability of hashing methods to dynamic files. Particularly, linear hashing methods have better random access performance than any other methods. Also, it has an advantage over other dynamic methods in that it lacks a directory. But random accessing is possible but sequential accessing is not. By order preserving linear hashing, sequential accessing is possible but not always efficient. One difficulty is that if the natural order of each attribute field is to be preserved, the structure becomes dependent on the distribution of the keys in the key space.
We propose a variant of linear hashing which is weakly order preserving and less depends on data distribution, where ordered records are redistributed in a multi buckets. Our method called redistribution order preserving linear hashing (ROPLH) uses a multi bucket segment for the purpose of redistribution. The objective is the development of file organizations that, with reasonable insertion cost, keep their optimal performance characteristics for random access even when the file size increases. Also, the file organization must provide for efficient range search. It will efficiently support a random search that is a part of an ordered searchings.
데이타베이스 시스템이 다루는 정보의 양이 많아지면, I/O bottleneck 현상을 겪게 된다. 이러한 문제에 대한 해결책 가운데 하나는 데이타를 효율적으로 저장하여서 I/O 수를 줄이는 방법이다. 인덱스를 가지는 화일 구성을 할때, 해슁 방법은 실제 응용 분야에서 효율적으로 동작한다. 최근에 dynamic한 환경 하에서 잘 동작 하는 해슁 방법이 많이 개발되었는데, 그중에서도 선형 해슁 방법은 하나의 레코드를 탐색하는데는 가장 빠르며 디렉토리가 필요하지 않다는 장점이 있다. 하지만 순서화된 탐색을 하는데는 불합리하다. 순서화된 탐색을 가능하게 하는 방법으로는 순서화된 선형 해슁 방법이 있는데, 이는 레코드의 분포에 따라 심각한 비효율성을 보이기도 한다.
본 논문에서는 선형 해슁과 순서화된 선형 해슁을 일반화시켰다. 본 논문에서 제안된 방법은 재분배를 이용한 순서화된 선형 해슁이다. 순서화된 선형 햇슁에 의해 얻어진 순서화된 레코드를 인접한 다버켓 세그먼트에서 재분배하는 것이 이 방법의 기본적인 생각이다. 재분배에 의해 레코드의 분포에 무관하게 되고 따라서 낮은 update overhead로 화일을 유지할 수 있게 된다. 이 방법은 한 레코드의 탐색이나 순서화된 탐색을 가능하게 해준다.
