[Database] 인덱스 (Index) 4장 : Hash Index

https://kghworks.tistory.com/151

[Database] 인덱스 (Index) 3장 : B+-Tree Index 기본

인덱스 분류

앞 포스팅까지 Ordered Index (정렬된 인덱스)를 알아보았고 또 다른 종류 Hash Index에 대해 알아본다. 지금까지 정렬되어 있는 인덱스였으니 Hash Index의 가장 구별되는 특징은 정렬되어있지 않다는 것이다.

 

목차

• Hash Index
• In-memory Hash Index
• Disk-based Hash Index

---

Hash Index

 주로 메인 메모리에 인덱스를 생성하는데 사용되는 기법으로 Join 연산 시 사용을 위해 임시로 생성되는 인덱스로 사용된다. 영구적으로 main memory에 생성되는 인덱스에도 사용하기도 한다. 거의 사용되지는 않지만, record file을 구성할 때도 사용할 수 있다. (hash file organization)

크게 In-memory hash Index, Disk-based hash Index로 구분된다. 

 

Bucket

 1개 이상의 record를 저장할 수 있는 storage 단위다. In-memory hash index에서는 index entry (혹은 record)로 구성된 linked list로 구현되고, Disk-based index에서는 disk block으로 이루어진 linked list로 구현된다. hash file organization에서는 bucket에 실제 record를 저장한다. 

---

In-memory Hash Index

  

구조

• K : search-key value 집합
• B : Bucket 주소 집합
• h : Hash Function (h: K->B)

 search key K를 함수 h로 연산하여 Bucket B 결과를 얻는 구조이다. 함수랑 비슷하다.  In-memory hash index에서는 B가 단순 pointer로 이루어진 배열이다. 배열의 각 pointer의 head에는 같은 bucket의 다른 원소들을 가리키는 형태로 저장되어 있다. 

 이와 같이 2개 이상의 record를 하나의 Bucket에 저장하는 방식을 Overflow chaining (closed addressing, closed hashing)이라고 한다.

 

INSERTION

 만약 search key Ki를 삽입한다면, h(Ki)를 계산해서 그 결과 Bucket에 Index entry를 저장한다.

 

Lookup (탐색)

 Hash Index는 각 search key에 대한 동등한 query 성능을 보장한다. search key Ki를 찾기 위해 h(Ki)를 계산하여 그 결과 Bucket에서 원하는 record를 찾는다. B+-Tree index와 다르게 range query (범위 검색)은 지원하지 않는다. 

 

DELETION

삭제 또한 탐색과 똑같은 방식으로 hash 함수 h를 계산하여 삭제 대상 record를 찾는다. 

 

---

Disk-based Hash Index

 기본적인 동작은 앞에서 본 In-memory와 비슷하게 동작한다. 그러나  Disk-based 에서는 Bucket이 disk block으로 이루어져 있다는 점 때문에 조금 다른 부분들이 있다.

 

Bucket Overflow

 

Disk-based hash index의 bucket overflow

 삽입 (INSERTION) 시 bucket의 공간이 부족하면 bucket overflow가 발생한다.

 

 만약 해당 bucket에 반드시 삽입되어야한다면 overflow bucket을 제공한다. overflow bucket은 기존 bucket과 linked list로 연결된다. (위 그림에서 bucket 1) 나중에 Lookup (탐색) 시 bucket1에 접근한 뒤 순차적으로 overflow bucket까지 탐색해 나간다.

  

Skew : Bucket이 고르게 분포하지 않는 경우

 위처럼 overflow bucket이 쌓이게 되면 발생할 수 있다. 뿐만 아니라 search key 중복이 많거나, Hash의 결과가 균일하게 분포되지 못하고 한쪽으로 몰리면 Bucket이 고르게 분포되지 못할 수 있다. 이 역시 인덱스 성능을 떨어뜨리는 요인이 된다.

 

 

해결방안 1 : 동적으로 bucket 수 유지하기

• nr : record 수
• fr : bucket당 record 수
• d : fudge factor (보통 0.2)

일 때 bucket 수 = (nr/fr) * (1+d)으로 유지시키는 방법이다. d가 0.2일 때 bucket의 20%가 비어있게 된다.

 

 

해결방안 2 : Static hashing

 인덱스 생성 시 bucket 수를 고정하여 생성하는 방식이다. 미리 record 규모를 파악해야 하는 단점이 있다. 삽입 (INSERTION)이 많아질수록 bucket 수보다 record 수가 많아질 것이기 때문이다. 이렇게 되면 다시 overflow bucket이 많아지게 된다.

 극복방안으로 bucket 수를 증가하기 위해 인덱스를 재구성하는 방법이 있다. 당연 재구성 시간은 relation 크기에 비례하게 된다. 이때는 동적으로 bucket 수를 증가시키는 dynamic hashing (e.g. linear hashing, extendible hashing)을 사용하기도 한다.