Index

Basic Concepts

Basic Concepts

• 인덱스는 원하는 데이터에 빠르게 접근하기 위해 사용된다.
• 인덱스 파일은 < search-key, pointer > 형태의 기록으로 구성된다.
  • search-key는 레코드를 찾기위해 사용되는 속성들의 집합니다.
  • 인덱스 파일은 보통 원래 파일보다 훨씬 작다.
• 두 종류의 인덱스가 있다.
  • 정렬 색인 (ordered index) : 색인 레코드가 탐색키 기준으로 정렬되어 있다.
  • 해쉬 색인 (hash index) : 색인 레코드가 탐색키 기준으로 정렬되어 있지 않다.

Index Evaluation Metrics

색인을 평가하는 요소를 말하며 이중 색인이 제공하는 질의 타입이 중요하다. 질의타입에는 다음 2가지의 경우가 있다.

• 일치 질의 형태 (Exact Match Query)
  속성의 특정 값과 일치하는 터플을 검색
• 범위 질의 형태 (Range Query)
  속성이 일정 범위에 속하는 터플을 검색

Ordered Index

• 정렬 색인에서, 색인 레코드는 탐색 키 기준으로 정렬되어 있다.
• Primary index (clustering Index)
  • 탐색키의 순서가 파일의 순차적인 순서와 같다.
  • 데이터 파일당 하나 존재한다.
  • primary index의 탐색 키는 반드시 주 키일 필요는 없다.
• Secondary Index (non-clustering index)
  • 탐색키의 순서가 파일의 순차적인 순서와 다른 인덱스이다.
  • 데이터 파일에 여러개가 존재하고 있다.

Dense Index (밀집색인)

• 밀집색인 (Dense Index)
  • 모든 탐색키 값에 대하여 레코드가 색인에 존재한다.
• Sparse Index (희소 색인)
  • 모든 탐색키 값에 대한 색인 엔트리가 없다.
  • 데이터가 탐색키 기준으로 정렬되어 있어야 한다.
  • 밀집 색인에 비하여 공간은 적게 차지하나 레코드를 검색하는데 더 많은 시간을 요구한다.
• 좋은 밀집 색인?
  • 데이터는 search key 속성에 따라 정렬되어야만 한다.
  • 블록에 속하는 레코드의 가장 적은 값으로 index entry를 구성한다.Multilevel Index
• 만약 primary index가 메모리에 맞지 않다면, 접근은 비싸진다.
• 다단계 색인
  • priamry index를 디스크에 두고 순차적인 파일로 취급하고, 그것에 대한 sparse index를 만든다.
  • Outer Index : primary key에 대한 spare index
  • Inner Index : primary key file
  • outer index가 너무 커서 메인 메모리에 들어갈 수 없더라도, 다른 레벨의 인덱스가 생성되어 일부를 넣을 수 있다.
• 모든 레벨에 있는 인덱스들은 파일의 insertion, deletion에 의해 갱신되어야 한다.

Index Update : Deletion

• 데이터 파일이 삭제되는 경우
• Single-Level 색인 엔트리 삭제
  • 밀집 색인 : search-key 삭제는 파일 레코드 삭제가 같다.
  • 희소 색인
    • 만약 search-key를 위한 엔트리가 인덱스에 존재한다면, 다음 search-key 값을 가지는 엔트리로 교체되어야 한다.
    • 만약 다음 search-key 값이 이미 인덱스 엔트리에 있다면, 엔트리는 교체되지 않고 그냥 삭제된다.Index Update : Insertion
• 데이터 레코드가 삽입되는 경우
• Single-level index insertion
  • 삽입될 레코드의 serach-key 값을 인덱스 파일에 있는지 본다.
  • 밀집 색인 : 인덱스에 serach-key 값이 없다면, 삽입한다.
  • 희소 색인
    • 인덱스가 파일의 각 블록을 위한 엔트리를 저장하고 있다면, 새로운 블록이 생기지 않는 한 갱신되지 않는다.
    • 만약 새로운 블록이 생성되면, 새로운 블록의 첫 search-key 값이 인덱스에 삽입된다.
• 다단계 색인의 삽입과 삭제도 비슷하게 처리된다.

Secondary Index

• 이차색인은 색인레코드 순서대로 데이터 레코드 순서를 정렬하지 않은 색인이다. (참고로 일차 색인이던 이차 색인이던 색인 레코드는 항상 정렬되어야 한다)
• 이차 색인은 동일 데이터 파일에 대하여 임의의 속성에 대하여 개수 제한 없이 생성할 수 있다.Priamry vs Secondary
• 일반적으로 색인을 사용하면 검색시간이 향상된다.
• 인덱스 갱신은 데이터베이스 갱신에 의해 오버헤드를 야기할 수 있다.
• 주 색인을 사용한 순차 탐색은 효율적이나, 이차 색인을 사용한 순차 색인은 비효율적이다.
  • 이차색인 레코드는 데이터 레코드 순서와 무관하기 때문이다.

B+-tree Index

B+-tree Index

• 대표적인 인덱스 색인 구조이다.
• B+-Tree의 장점은 단점을 상쇄한다.
  • insertion, deletion을 위한 작고 지엽적인 변화에 대해 스스로를 자동으로 재구성한다.
  • insertion, deletion overhead, space overhead
• B+-Tree는 주키로 정렬된 순차적인 파일에 대한 대안이다.
  • 블록이 엄청 커질 수 있기 때문에, 파일이 커지면서 성능이 저하된다.
  • 전체 파일에 대한 주기적인 재구성이 필요하다.

B+-tree Node Structure

• B+-tree는 다음의 규칙을 따르는 트리이다.
  • root에서 leaf까지의 모든 경로의 깊이가 같다 (Balanced).
  • root나 leaf가 아닌 각 노드는 N/2 ~ N개의 자식을 가진다. (올림)
  • leaf node는 N/2 ~ N-1 사이의 값을 가진다.
  • 예외의 경우
    • 만약 root가 leaf가 아니라면, 최소 2개의 자식을 가져야 한다.
    • 만약 root가 leaf라면, 0~(n-1)개의 값을 가질 수 있다.
• Typical node : [P1, K1, P2, K2, .., Pn-1, Pn-1, Pn]
  • Ki는 search-key 값이다.
  • Pi는 non-leaf 노드에서 자식을 위한 포인터이고, leaft 노드에서 레코드나 버킷으로의 포인터이다.
• 노드에 있는 Search-Key들은 정렬되어 있다.
  • K1 < K2 < K3 < ... < Kn-1
  • 중복되는 키가 없다고 가정한다.

Leaf Nodes in B+-tree

( 예시 )

• 리프노드의 마지막 포인터는 형제 노드를 point한다. 이러한 구조는 리프노드를 순차적으로 검색하는 것을 용이하게 한다.

None Leaf Nodes in B+-tree

• B+Tree의 내부노드는 leaf node에 대한 다단계 희소색인을 구현한 것이다.
• 내부 노드 : [P1, K1, P2, K2, ..., Pn-1, Kn-1, Pn]
  • P1이 가리키는 탐색키 subtree의 값들은 K1보다 작다.
  • 2 <= i <= n-1일 때, Pi가 가리키는 subtree의 모든 search-key들은 Ki-1의 값보다 크거나 같고, Ki 보다는 작다.
  • Pn이 가리키는 subtree의 모든 search-key들은 Kn-1의 값보다 크거나 같다.B+-Tree Search
    

    

• "El Said"를 찾는 과정이다.
  1. root node에서 (El Said < Mozart)이므로 두 번째 레벨의 첫 번째 노드를 방문한다.
  2. Einstein < El Said < Gold 이므로 세 번째 레벨의 세번째 노드를 방문한다.
  3. 현재 노드에 El Said가 있으므로 포인터를 탐색한다.

B+-Tree Insertion

• leaft노드에 탐색 키 값이 있는지 찾는다. 이미 있다면, 레코드를 데이터 파일에 넣는다.
• 만약 탐색 키 값이 없다면...
  • 레코드를 데이터 파일에 넣는다.
  • 만약 leaf node에 자리가 있다면 leaf node에 (key, pointer) 쌍을 넣는다.
  • 그렇지 않다면 노드를 2개의 새로운 노드로 나눈다. (Split)
• Splitting a leaf node
  • N개의 데이터가 되면 (꽉 차면), 노드 내부의 정렬된 데이터들을 이전의 노드, 새로운 노드로 나눈다.
  • 새로운 노드를 p라고 하고, p안의 최소 key 값을 k라고 하자. (k,P)를 나뉘어진 노드의 부모에 넣는다.
  • 만약 부모가 꽉 차면, split한다. 이는 split이 멈출 때 까지 부모에 계속 전파된다.
  • 최악의 경우, root 노드가 분리되면 트리의 높이가 1 증가한다.
• Splitting a non-leaf node : 이미 꽉찬 내부노드 N에 (k,p)를 넣게되면...
  • (k,p)를 N에 잠깐 넣는다.
  • N이 P1 ~ P(n/2) 까지 수용한다.
  • 새로운 노드 N'이 P(n/2 + 1) ~ P(n+1) 까지 수용한다.
  • (K(n/2), N')가 N의 부모노드로 삽입된다.
    

    

B+-Tree Deletion

• 삭제되어야할 레코드를 찾고, 데이터 파일과 인덱스 파일로부터 제거한다.
• 제거로 인한 underflow를 처리한다.

1. 만약 제거된 데이터의 노드와 형제 노드들이 하나의 노드로 합쳐질 수 있다면, 합친다. (merge, coalesce)
   1. 두 노드안의 모든 search-key 값을 하나의 노드에 넣고, 다른 노드를 제거한다.
   2. Pi이가 제거된 노드로의 포인터인 (Ki-1, Pi) 쌍을 모든 부모들로 부터 제거한다.
   3. 노드 삭제는 n/2개 이상의 포인터를 가진 노드가 나올 때 까지 위로 연쇄적으로 수행될 수 있다.
   4. 만약 부모 노드가 삭제후 오직 하나의 포인터를 가진다면, 그것은 삭제되고 하나의 자식이 루트가 된다.
2. 엔트리 공간이 부족하여 형제노드와 병합할 수 없다면, 포인터를 재분배한다.
   1. 노드와 형제노드 사이의 값의 포인터를 재분배하여 둘다 최소 갯수 이상의 엔트리를 가지게 한다.
   2. 노드의 부모에 있는 상응하는 search-key값을 갱신한다.
      

      

Non-Unique Search Key

• RID값을 key속성에 병기하여 모든 키 값을 유일하게 사용한다.B+-Tree File
• 리프노드에 탐색키-포인터 pair를 저장하는 대신 레코드 포인터를 저장
• data insert, delte, update에 의해 색인과 데이터파일이 불일치되는 데이터가 많아질 수 있는데, B+트리 파일 구성은 이러한 문제점을 근본적으로 해결Indices on Multiple Attributes
• 특정한 유형의 질의에 대해 여러 개의 인덱스를 사용한다.
• 단일 색인 만이 존재할 때 쓰일 수 있는 전략
  • 각 속성에 대한 인덱스를 통해 얻은 포인터 집합을 교집합한다. (가장 많이 쓰이는 방법)
• 다중색인은 하나 이상의 속성을 가지는 search key를 가진다.
  • 이때, 다중 색인의 처음에 나오는 속성에 대하여 exact match 형태가 적용되는 질의문에 효과적이다.Covering Indecies
• 색인 엔트리에 search key 속성외의 다른 속성 '값'을 같이 저장
• 실제 데이터를 ferch하지 않고도 질의를 위해 값을 내놓을 수 있다.
• 이차 색인에 특히 효과적임

Dynamic Hashing

Dynamic Hashing

• 데이터베이스 환경에서 데이터베이스 크기는 항상 변화한다.
• 이에 적합한 색인 구조는 동적 해쉬이다.

Extendable Hashing

• 확장 해쉬는 버킷 주소 테이블과 버킷 (실제 레코드가 위치하는 공간)의 두 자료구조를 운영
• 확장 해쉬에서느 해쉬함수가 동적으로 변하며, 일정 조건이 만족되면 해쉬 함수 치역이 2배로 확장되거나 1/2로 축소될 수 있다. 레코드가 위치하는 버킷이 2개로 분해되거나 2개가 1개로 병합되기도 한다.
• 해쉬 함수 값 중에서 앞에서 i개의 bit를 사용하여 버킷주소를 결정하며, 버킷 주소 테이블은 i 값을 유지하여야 한다. 버킷에서도 몇 개의 i개의 bit를 사용하여 버킷 주소를 유지하는지 명시하여야 한다.Extendable Hashing Structure
  

  

  - 각 버킷 j는 Ij값을 가진다.
  • 같은 버킷에 있는 엔트리들은 첫 Ij비트의 값이 같다.
• 탐색 키 K를 가지는 버킷을 찾기 위해...
  • H(K)=X를 계산한다.
  • X의 상위 i개의 비트를 bucket address table에서의 해당 버킷의 위치로 사용하고, 그 곳에 있는 버킷의 포인터를 따라간다.Insertion
• 탐색키 값 K를 넣기 위해...
  • 버킷 j를 찾는다.
  • 버킷 j에 공간이 있으면, 레코드를 버킷 안에 저장한다.
  • 공간이 없다면...
    • 버킷은 나누어 지고 다시 넣는다.
    • overflow 버킷이 사용되기도 한다.
• 탐색키 Kj를 넣을 때 버킷 j를 나누려면...
  • 만약 i > ij라면 (버킷 j로의 여러 개의 포인터가 있음)
    1. 새로운 버킷 z를 할당하고, ij = iz = ij+1 한다.
    2. bucket address table의 모든 엔트리들을 update 한다. 이때 이들을 j, 또는 z를 포인트하도록 한다.
    3. 버킷 j에 있는 레코드를 제거하고 j나 z에 다시 넣는다.
    4. Kj를 위한 버킷을 넣는다.
  • 만약 i = ij라면... (오직 하나의 포인터만이 buckt j를 가리킴)
    1. 만약, i가 한계에 도달하거나, 삽입에 의해 너무 많은 분할이 일어났다면, overflow bucket을 만든다.
    2. 그렇지 않으면...
       1. i를 증가하고 bucket address table의 크기를 2배로 늘린다.
       2. buckt address table의 엔트리를 2개로 나누고, 같은 버킷을 포인트 하도록 한다.
       3. Kj를 위한 새로운 bucket address table을 계산하고 삽입한다.Deletion
• key 값을 삭제하기 위해서..
  • 버킷을 삭자 삭제한다.
  • 버킷이 비어있게 되면 삭제할 수 있다.
  • 버킷의 병합이 가능하다. (단 buddy 버킷이 같은 ij값을 가지고 같은 ij-1 접두사를 가지고, 이것이 존재 할 경우에만 가능하다.)
  • bucket address table 크기를 줄이는 것 또한 가능하다.
    • 이것은 비용이 많이 드는 작업이다.Advantage & Disadvantage

Bitmap Index

bitmap Index

• 비트맵 인덱스는 여러개의 키에 효과적으로 질의하기 위해 설계된 인덱스이다.
• 도메인 크기가 적은 속성에 대해 적용할 수 있다.
• 데이터 테이블에 있는 레코드는 0번부터 번호메겨진다.
• 비트맵은 비트의 배열일 뿐이다.
  • 레코드 갯수 만큼의 비트를 가지고 있다.
  • 비트맵이 value v를 위할 때, 레코드가 그 속성에 대해 v값을 가지면 bit가 1이고 그렇지 않으면 0이다.
• 비트맵 색인은 여러 속성에 대해 질의할 때 유용하다.
  • 한 개 속성의 질의에 대해서는 딱히 유용하지 않다.
• 질의는 bitmap 연산을 통해 평가된다.
  • 각 연산은 같은 크기의 2개의 비트맵에 의해 행해지며 결과 비트맵을 결과로 내놓는다.
  • and, or, not

Storage Overhead

• 비트맵은 데이터 테이블에 비해 크기가 매우 작다.Deletion and Null Value
• Deletion은 적절하게 다뤄져야 한다.
  • 레코드 위치에 유효한 레코드가 있는지 표시하기 위해 existence bitmap이 있다.
    • 0은 deletion을 말한다.
  • exsistence bitmap과의 and 연산을 통해 유효한 레코드를 먼저 파악한다.
• Null Value도 적절하게 다뤄져야 한다.
  • 각 속성에 대해 null bitmap이 있어야한다.
    • 1은 null이다.
  • ~null bitmap와 and 연산하여 유효한 record를 먼저 파악한다.

출처

https://www.programiz.com/dsa/deletion-from-a-b-plus-tree