다중키 인덱스

[ 다중키 인덱스 ]

▪ 애트리뷰트들의 어떤 조합이 자주 사용된다면 이런 애트리뷰트들의 조합에 의한 키 값을 이용하여 효율적인 접근을 제공할 수 있는 접근 구조를 생성하는 것이 효율적이다.

 

[ 다중 애트리뷰트의 순서 인덱스 ]

▪ 인덱스가 의 애트리뷰트에서 생성되었다면 탐색키 값은 의 n개의 값을 가 진 투플이다.

- 이런 투플값들의 사전적 순서를 이 복합 탐색키의 순서로 사용한다.

 

[ 분할 해싱 ]

▪ 다중키에 대한 접근을 허용하는 정적 외부 해싱을 확장한 것이다.

▪ 분할 해싱은 동등 비교에만 적합하며 범위 질의는 지원하지 않는다. 

▪ n개의 구성 요소로 이루어진 키에 대하여 해시 함수는 n개의 별도의 해시 주소를 생성하도록 설계된다. 버켓 주소는 이런 n개의 주소를 결합한 것이다. 관심 있는 주소의 일부와 부합되는 적절한 버켓을 탐색하 여 원하는 복합 탐색키에 대한 탐색을 할 수 있다.

▪ 애트리뷰트의 수를 쉽게 확장할 수 있다. 버켓 주소에서 상위의 비트들이 자주 접근되는 애트리뷰트들과 대응되도록 버켓 주소를 설계할 수 있다.

▪ 각 애트리뷰트를 위한 어떤 별도의 접근 구조를 유지할 필요가 없다. 분할 해싱의 중요한 단점은 어떠한 구성 애트리뷰트들에 대해서도 범위 질의를 지원하지 못한다는 것이다.

 

[ 그리드 파일 ]

▪ 두개의 키를 가지고 파일을 접근하려 한다면 각 탐색 애트리뷰트에 대해 하나의 선형 눈금(또는 차원)을 갖는 그리드 배열을 구성할 수 있다.

▪ 각 눈금은 해당 애트리뷰트에 대해 균등 분포를 갖도록 만들어 진다.

▪ 이 방법은 선형 눈금을 따라 여러 값의 그룹에 대응되는 셀들의 집합으로 사상되는 범위 질의에 특히 유 용하다.

▪ 만약 어떤 범위 질의가 몇몇 그리드 셀들에 대응한다면, 이들 그리드 셀들에 대한 버켓들을 정확하게 접 근하여 이 질의를 처리할 수 있다.

▪ 그리드 배열은 탐색키 애트리뷰트들의 차원에 따라 파일을 분할하고, 이런 차원들에 대한 값들의 조합에 의한 접근을 제공한다.

▪ 그리드 파일은 다중키 접근에 걸리는 시간을 줄일 수 있는 효율적인 방법이다.

▪ 그리드 파일은 그리드 배열 구조를 위해 많은 공간을 필요로 한다. 더욱이 동적 파일에서는 파일을 자주 재조직 해야 하므로 유지 보수 비용이 많이 증가한다는 단점이 있다.

 

댓글이나 공감 남겨주는 사람 착한사람