Index Update

상위 문서: Indexing

개요

어떤 형태의 인덱스(index)가 사용되었든 관계없이, 파일에 레코드(record)가 삽입되거나 삭제될 때마다 인덱스는 반드시 갱신(update)되어야 한다. 또한, 파일 내의 레코드가 갱신되는 경우, 그 갱신이 검색 키 속성에 영향을 준다면, 해당 인덱스 역시 갱신되어야 한다. 예를 들어, instructor의 department가 바뀌면, dept_name 속성에 대한 인덱스도 그에 맞게 갱신되어야 한다.
이러한 레코드 갱신은 기존 레코드를 삭제하고, 새로운 값으로 레코드를 삽입하는 것으로 모델링할 수 있다. 이로 인해 인덱스에서도 삭제가 먼저 일어나고, 그 다음 삽입이 발생한다. 따라서 인덱스에서 삽입과 삭제만 고려하면 되고, 갱신 자체는 명시적으로 따로 고려할 필요가 없다.

다단계 인덱스(multilevel index)에 대한 삽입 및 삭제 알고리즘은 아래에서 설명할 방식의 단순한 확장이다. 삭제 또는 삽입이 발생하면, 시스템은 가장 하위 단계의 인덱스를 먼저 아래의 방식대로 갱신한다. 그 다음 단계에서 보면, 가장 하위 인덱스는 단지 레코드들로 이루어진 파일이므로, 그것이 변경될 때에만 상위 인덱스는 파일 갱신 방식 그대로 갱신하면 된다. 더 상위 단계가 있다면, 같은 방식으로 재귀적으로 갱신하면 된다.

Insertion

우선, 시스템은 삽입(insert)될 레코드에 들어 있는 검색 키 값을 사용하여 검색(lookup)을 수행한다. 그 다음에 취할 작업은 인덱스가 조밀(dense)에 속하는지 희소(sparse)에 속하는지에 따라 다르다.

Dense indices

먼저, 조밀 인덱스(dense index)의 경우에는 다음과 같이 처리한다:

• 삽입할 검색 키 값이 인덱스에 존재하지 않을 경우, 시스템은 해당 검색키(search key) 값을 갖는 인덱스 항목을 적절한 위치에 삽입한다.
• 이미 검색 키 값이 존재할 경우, 다음 중 하나를 수행한다:
  a. 인덱스 항목이 동일한 검색키 값을 갖는 모든 레코드에 대한 포인터들을 저장하고 있다면, 새 레코드에 대한 포인터를 해당 인덱스 항목에 추가한다.
  b. 인덱스 항목이 동일한 검색 키 값을 갖는 첫 번째 레코드에 대한 포인터만 저장하고 있다면, 기존 레코드들 뒤에 삽입할 레코드를 배치한다.

Sparse indices

희소 인덱스(Sparse index)의 경우에는 다음과 같이 처리한다:

• 시스템이 새로운 블록을 생성했다면, 그 블록 내에서 검색 키 순서 기준으로 첫 번째 검색키 값을 인덱스에 삽입한다.
• 새 레코드가 그 블록 내에서 가장 작은 검색 키 값일 경우, 시스템은 해당 블록을 가리키는 인덱스 항목을 갱신한다.
• 그렇지 않은 경우, 시스템은 인덱스를 변경하지 않는다.

Deletion

레코드를 삭제하려면, 시스템은 먼저 삭제할 레코드를 검색한다. 그 다음의 동작은 인덱스가 조밀에 속하는지, 희소에 속하는지에 따라 다르다.

Dense indices

먼저, 조밀 인덱스의 경우에는 다음과 같이 처리한다:

• 삭제할 레코드가 해당 검색 키 값을 가진 유일한 레코드였다면, 시스템은 해당 인덱스 항목을 삭제한다.
• 여러 레코드 중 하나일 경우, 다음 중 하나를 수행한다:
  a. 인덱스 항목이 동일한 검색 키 값을 갖는 모든 레코드에 대한 포인터들을 저장하고 있다면, 시스템은 삭제된 레코드에 대한 포인터만 제거한다.
  b. 인덱스 항목이 동일한 검색 키 값을 갖는 첫 번째 레코드에 대한 포인터만 저장하고 있고, 만약 삭제된 레코드가 그 첫 번째 레코드라면 인덱스 항목을 다음 레코드를 가리키도록 갱신한다.

Sparse indices

희소 인덱스의 경우에는 다음과 같이 처리한다:

• 삭제할 레코드의 검색 키 값을 가진 인덱스 항목이 없다면, 인덱스에는 아무런 조치도 필요 없다.
• 인덱스 항목이 존재할 경우, 시스템은 다음 중 하나를 수행한다:
  a. 삭제된 레코드가 그 검색 키 값을 가진 유일한 레코드였다면, 시스템은 그 인덱스 항목을 다음 검색 키 값에 대한 인덱스 항목으로 대체한다. 만약 다음 검색 키 값에 대한 인덱스 항목이 이미 존재한다면, 해당 항목을 삭제한다.
  b. 인덱스 항목이 삭제될 레코드를 가리키고 있다면, 시스템은 인덱스 항목이 다음 레코드를 가리키도록 갱신한다.