👉

Indexing Structures for Files


Indexing structure는 파일이 이미 어떤 primary organization으로 존재한다고 가정한다.

'Indexes'(색인)은 특정 검색 조건에 대해 레코드를 빠르게 찾기 위해 사용한다.

'Index structures' 는 secondary access path(보조 접근 경로)를 제공해주는 디스크의 추가적인 파일로, primary 데이터 파일의 물리적인 위치에 영향을 주지않고 레코드에 접근할 수 있는 대체적인 방법을 제공한다.

Index structure는 indexing field에 대한 효율적인 레코드 접근을 가능하게 한다. 여기서 indexing field는 레코드의 어느 필드나 사용가능하다. Multiple field에 대한 index도 생성가능하다.

대부분의 index는 ordered file에 기반을 두고 트리 자료구조를 사용한다.

Single-Level Ordered Indexes

Ordered index(정렬 색인)은 중요한 조건을 순서대로 정렬해서 찾기 쉽게하는 것이 목표다. 중요한 조건을 'indexing field'라고 한다. Index field가 정렬되어 있기 때문에 binary search를 이용한 빠른 탐색이 가능하다.

Index file은 'Index field의 각 값 + 그 레코드를 가진 block에 대한 포인터'의 리스트를 보관한다. 그렇기 때문에 일반적으로 데이터 파일에 비해 크기가 훨씬 작다.

Primary Index (주요 색인)

레코드의 정렬된 파일들의 ordering key field에 대한 색인이다.

Primary index의 index record는 두 가지 field를 갖는다.

  • Primary key(block anchor): Block의 첫 레코드의 primary key field의 값
  • Pointer to disk block

Primary index는 데이터 파일보다 공간을 훨씬 적게 사용한다. 레코드 수보다 index entry의 수가 더 적고, entry의 사이즈가 더 작기 때문이다. 따라서 index file에 대한 binary search가 데이터 파일보다 더 적은 block 접근을 필요로 한다.

Primary Index

Dense index는 모든 key value에 대해 index entry를 주는 것이다. 즉, 모든 레코드에 대해 색인을 만든다.

Sparse index는 몇몇 값에 대해서만 entry를 만든다. 대부분 기본적으로 sparse index를 사용한다. Primary index도 sparse index이다.

Problems

Primary index의 큰 문제점은 새로운 레코드의 삽입과 삭제다. 삽입하려면 새 레코드를 넣기 위해 다른 레코드들을 옮겨줘야 할 뿐만 아니라 index entry도 변경해야한다. 삭제도 몇몇 block의 block anchor를 변경시킬 수 있다.

Insertion 문제는 'unordered overflow file'을 사용해서 해결할 수 있다. 각 block마다 overflow 레코드들의 연결 리스트를 사용한다.

Deletion 문제는 deletion marker로 해결할 수 있다.

Clustering Index (군집 색인)

Non-key field에 대한 색인이다. 데이터 파일이 non-key field에 대해 물리적으로 정렬된, 즉, 'clustered file'이면 사용할 수 있다.

Clustering index는 clustering field에 대해 같은 값을 가지는 레코드들을 빠르게 가져오기 위해 사용한다. 때문에 clustering index는 sparse index다.

Primary index의 index field는 unique한 값인 반면, clustering index는 중복되는 값이다.

두 가지 field를 가진 정렬된 파일을 가진다.

  • Clustering field of clustered file
  • Pointer to disk block(값이 최초로 나타나는 data block을 가리킨다)

Problems

Clustering index 또한 레코드를 삽입, 삭제할 때 문제가 발생한다.

이 문제를 해결하기 위해 block 하나를 통째로 clustering field의 각 값에 할당할 수 있다. Field에 대해 같은 값을 가지는 모든 레코드들이 같은 block에 있게 된다.

Clustering Index

Secondary Index (보조 색인)

데이터 파일에 접근할 수 있는 보조적인 수단을 제공한다. 보조적인 수단이기 때문에 데이터 레코드의 순서는 중요하지 않다.

중복되는 값을 가지는 field에도 생성할 수 있고, unique한 값을 가지는 field에도 생성할 수 있다. 또한, 같은 데이터 파일에 대해 여러 보조 색인을 생성할 수 있다. 말그대로 추가적인 수단이기 때문이다.

Secondary index 또한 두 가지 field를 가진다.

  • Indexing field
  • Pointer
    • to record
    • to block: 해당 index field의 값을 가지는 block을 가리킨다.

Secondary Index - dense

Summary

Summary

Multilevel Indexes

Search cost를 줄이기 위해 디자인됐다.

Multilevel index의 첫 번째 level은 index 파일 그 자체, 즉, block을 가리키는 포인터를 가진다. 두 번째 level은 첫 번째 level을 가리키는 index를 가지고, 이를 세 번째, 네 번째로 필요한 만큼 확장해서 사용할 수 있다.

아래는 정적인 구조(static structure)를 가지는 two-level primary index이다. (ISAM)

Multilvel Index

Dynamic Multilevel Indexes

위에서 봤던 정적인 구조, ISAM은 당연하게도 삽입과 삭제에 대한 문제가 발생한다. 모든 index level은 물리적인 파일이기 때문에 새로운 index가 추가됐을 때 구조를 바로바로 변경하기 쉽지않다. 이에 대한 대책으로 이전에 언급했던 overflow page를 사용할 수는 있지만, 성능이 좋지않다.

이를 해결하기 위한 방법으로는 각 index block마다 여분의 공간을 비워놓거나 적절한 삽입/삭제 알고리즘을 사용해서 index block을 생성/삭게하는 방법을 사용할 수 있다. 이 방법을 적용한 것이 dynamic multilevel index다.

Search Trees

어떤 특정한 값을 가진 레코드를 찾을 때 가이드 역할에 사용되는 트리이다. 트리의 값들은 파일의 search field 값을 가진다.

Fanout pp를 가진 search tree의 각 노드는 최대 p1p-1개의 값, pp개의 포인터를 가진다.

image

새로운 값이 삽입되거나 삭제될 때, 두 가지 제약조건이 지켜져야한다.

  • 트리의 각 노드가 disk block에 할당되어야 하고,
  • 새로운 레코드가 파일에 삽입되면 search field 값과 새로운 레코드를 가리키는 포인터를 포함한 tree entry도 삽입되어야 한다.

B+ Tree

삽입과 삭제가 logpNlog_pN 비용으로 수행될 수 있다. (pp = fanout, NN= # of leaf pages)

B+ tree는 트리의 높이를 통일(height-balanced)시킨다. 또한 모든 노드는 최소한 50% 이상 공간이 사용되어야 한다. 즉, 절반 이상이 차있어야 한다. 따라서 각 노드는 dn2dd\leq n\leq 2d entry를 갖는다(dd, order of tree).

Equality(tree의 높이 만큼만 방문) 와 효율적인 range search를 제공한다.

트리의 내부 노드는 검색을 지시하고 리프 노드(leaf node)는 실제 데이터가 저장된 곳을 가리킨다.

리프 노드는 search field의 각 값들과 연결된다. Search field 의 값이 key field라면 포인터는 레코드를 가리키고, non-key라면 데이터 파일 레코드에 대한 포인터를 가진 block을 가리킨다.

  • 삽입(Insertion)
    1. 삽입할 leaf LL을 찾는다.
    2. LL에 index entry를 넣는다.
      • LL에 충분한 공간이 있다면 끝
      • 공간이 부족하다면 LL을 쪼개야한다. Entry를 고르게 분포시키고 middle key를 'copy up'한다. 쪼개는 일은 부모 노드에게 전파될 수 있다. 부모 노드도 똑같이 동작하지만 middle key를 'push up'한다.

B+tree insertion

  • 삭제(Deletion)
    1. 삭제할 entry가 속한 leaf LL을 찾는다.
    2. Entry를 삭제한다.
      • LL이 적어도 절반 이상 차있다면 끝
      • d1d-1 entry를 갖게 된다면, sibling의 entry를 빌려서 재분배(re-distribute)를 시도한다. 만약 재분배가 실패하면 LL과 sibling을 merge한다. Merge 또한 부모 노드에게 전파될 수 있다.

B+tree deletion-redistribute

B+tree deletion-merge