키 정렬과 인덱싱

앞선 포스팅에서 이진탐색을 위해서 키를 정렬해야하는데, 정렬된 레코드 파일을 생성할 때까지 디스크 I/O를 두번 수행하게 됩니다. 하지만, 이렇게 정렬해 두어도 Random Access 방식에서는 클러스터를 무작위로 찍어서 접근하므로, 실린더를 누비는 상황이 생길 수 있습니다. 이 경우 탐색 시간이 증가하는 문제가 발생합니다.

 

따라서, RAM에 가져온 RRN과 탐색을 위한 레코드 일부를 인덱스 파일로 RAM에 저장해둡니다. 이 때, 베이스가 되는 파일은 정렬이 되지 않아도 되지만, 인덱스 파일은 정렬상태로 유지합니다. 이렇게 할 경우, RAM에 있는 인덱스 파일의 정렬은 O(N log N)이 소요되지만 RAM은 충분히 빠르기 때문에 이 상태로 RAM에서 선형 탐색을 통해 빠르게 접근할 수 있습니다. 그러므로 HDD의 베이스 파일은 정렬될 필요가 없습니다.

 

이처럼 레코드의 참조가 다른곳에 저장되어 가리키는 것을 Pinned Record라고 합니다. 하지만 Pinned Record가 변경되는 경우, 인덱스 파일의 RRN이 이상한 곳을 가리키는 현상이 발생할 수 있습니다. 이를 Dangling Pointer라고 합니다. 따라서, Pinned Record의 이동과 같은 작업은 처리할게 많아집니다.

 

인덱스란, 파일의 레코드 순서를 재배열 하지 않고 임의의 순서로 접근할 수 있게하는 수단입니다.

 

단순 인덱스(Simple Index)의 예로는 앞서 서술한 Index File이 대표적인 예시입니다.

 

단순 인덱스의 장점으로는 작은 크기의 인덱스에 대한 정렬과 관리에 적합하다는 점과 입력순 데이터 파일에 대한 Pinned Record 관리에 용이함, 가변길이 레코드에 대한 이진탐색을 통해 키 탐색을 지원하는 점이 있습니다.

 

하지만 인덱스 사용과 관리는 디스크 상에서 진행되기 때문에, 이진탐색을 수행하기엔 많은 탐색 시간을 요구합니다. 따라서, 해쉬 테이블을 사용하거나 트리 구조 등의 방법을 사용합니다.

 

다중키로 인덱스를 검색하는 경우, 보조 인덱스를 사용합니다. 보조 키처럼, 중복이 가능하고 따로 조건이 없습니다.

키 : 참조 구조의 인덱스 파일은 동일하나 참조자리에 주 키가 올 수 도있습니다. (Indirect Addressing) 즉, 이 방법의 경우 Direct Addressing과 Indirect Addressing 둘다 가능합니다.

 

Direct Addressing의 경우 접근 속도가 빠르다는 장점이 있지만 Dangling Pointer 문제가 생길 수 있고, Indirect Addressing의 경우 삭제된 레코드가 있을 경우 탐색시간이 증가한다는 단점이 있습니다. 더욱이 보조 키가 변경되는 경우 보조 인덱스의 재배열이 필요하여 I/O 시간이 생깁니다. Indirect Addressing의 경우 주 키가 변경될 때 모든 보조 인덱스의 참조 필드를 함께 변경해야하므로 재배열이 필요합니다.

 

위의 문제들을 해결하기 위해서 Inverted List를 사용하게 됩니다. 이 방법을 사용하게 되면 새 항목에 대해서 재배열이 불필요(Entry Sequenced)하고 참조 필드의 수가 가변이라는 장점과 내부 단편화가 발생하지 않는다는 점이 있습니다. 하지만, 이 방법에도 문제점이 있는데 참조 필드들의 리스트가 긴 경우 디스크에 대한 접근이 늘어나서 참조값 검색에 불리합니다.

 

어떠한 방법을 쓰든 키는 연관된 레코드의 실제 주소에 연관되는데 그 시점을 Binding Time 이라고 합니다. 바인딩은 다음 두가지로 갈라집니다.

 

• Tightly Binding
• Loosely Binding

Tightly Binding은 직접 주소지정 방식을 사용하며 비유연성(Inflexible)이고, 빠른 속도를 보여줍니다.

Loosely Binding은 반대로 간접 주소지정 방식을 사용하며 유연성이 있고, 느린 속도지만 안전성이 보장됩니다.