[인덱스 시리즈1] 데이터베이스 Hash Index(해시 인덱스)

개요

 

해싱하는 방법에는 먼저 static hashing이 있다. 하지만 데이터베이스 분야에서는 static hashing 기법은 거의 사용하지 않는다.

 

 

그 이유로는, 만약 고정된 해싱 함수가 있을 때, 데이터베이스의 크기는 늘기도 하고 줄기도 한다.

처음부터 Bucket의 개수를 크게 잡으면 => 공간 낭비가 심하다.

처음부터 Bucket의 개수를 작게 잡으면 => Bucket Overflow가 너무 많이 발생한다.

 

 

따라서 버킷의 개수와 해시함수를 유동적으로 바꿀 수 있을까? 개발자들은 고민을 하였다.

 

 

첫 번째, 주기적으로 새로운 해싱함수로 파일들을 재조직하는 방법이 있다.

하지만 매번 새로운 해싱함수로 재조직하는 방법은 너무 비싼 연산이다.

두 번째는, bucket의 개수를 유동적으로 조절하는 방법이 있다.

 

 

이러한 방법을 Dynamic Hashing이라고 하고, 데이터베이스에선 이 방법을 사용한다.

 

 

Dynamic Hashing의 대표적인 예시로 Extendable Hashing이 있고 Extendable Hashing에 대해 살펴볼 것이다.

 

---

Extendable Hashing

Extendable Hashing 기법은 미리 Bucket을 다 생성하지 않고 동적으로 필요에 의해서만 생성하는 방법이다.

해싱함수의 결과값의 prefix를 사용해서 결과 주소 테이블을 찾아갈 수 있도록 하는 것이다.

아래 Extendable Hashing의 예시 사진을 보면 이해가 더 쉬울 수 있다.

 

이제 Extendable Hashing에서 데이터가 insert 되는 과정에 대해 더 자세히 살펴보자.

 

---

Extendable Hashing Insertion 예시 과정

먼저, 예시에 사용할 데이터이다.

dept_name으로 인덱스를 구성할 것이며, 아래는 hash function의 결과이다.

기본적인 원칙은 다음과 같다.

Bucket에 공간이 있다면, record를 bucket에 집어넣으면 된다.

만약 Bucket이 꽉 찼다면, bucket을 split하고 record를 재분배한다.

 

Split하는 과정

여기서 Bucket Address Table(BAT)라는 것이 등장하는데 BAT는 해시 자료구조의 해시테이블과 같이 어느 Bucket으로 갈지 주소를 저장하고 있는 테이블이다.

 

 

BAT의 prefix의 숫자를 나타내는 i가 Bucket의 i와 숫자가 같다면, BAT의 크기를 늘린다.

- BAT의 크기를 2배로 늘린다

- 새로운 bucket을 할당받고, 다시 해시 한다.

 

 

BAT의 prefix의 숫자를 나타내는 i가 Bucket의 i와 숫자보다 크다면, BAT의 크기를 늘리지 않고 bucket을 split한다.

- 새로운 bucket을 할당받는다, BAT의 포인터를 조정한다.

- 다시 해시한다.

---

이제 과정을 구체적으로 살펴보자

 

 

(Bucket Size는 2로 가정한다.)

1. 먼저 초기상태이다.

 

2. Srinivasan, Wu, Mozart record를 삽입한다.

 

 

위의 1번 상태에서 Srinivasan, Wu가 삽입되면 bucket1은 꽉 차게 된다. 따라서, Mozart를 삽입하려면, prefix가 0으로 같기 때문에 BAT의 크기를 두배로 늘리고, bucket을 늘리고 Mozart를 삽입한다.

 

 

 

3. Einstein을 삽입한다.

 

 

Einstein을 삽입하려고 보니, Finance, Physics, Comp.Sci의 해시함수 결과값이 모두 1로 같아서 Wu와 Srinivasan Bucket으로 삽입해야하는데 공간이 없다. 따라서, prefix가 1로 같기 때문에 BAT의 크기를 두배로 늘리고, bucket을 두 배로 늘리고 Einstein을 삽입한다. Einstein을 삽입할 때, Finance와 Physics의 해시함수 결과값을 보면 10으로 같고, Comp.Sci는 11이기 때문에 Wu와 Einstein을 같은 bucket에 넣고, Srinivasan은 다른 bucket에 넣는다.

4. 이러한 과정을 반복해서 6명을 삽입하면 아래와 같이 된다.

 

5. Katz를 삽입한다. 

 

 

Katz를 삽입할때, Katz는 Comp.Sci기 때문에,  Srinivasan과 El Said가 있는 bucket으로 들어가야 하는데 꽉 찼다.

BAT를 두 배로 늘려야 한다고 생각할 수 있다. 하지만 여기서는 BAT를 늘리지 않아도 된다. 왜냐하면 prefix를 나타내는 숫자를 보면, BAT의 숫자는 3이고 Srinivasan과 El Said가 있는 bucket은 2이기 때문이다.

따라서 BAT는 유지하고 bucket만 늘리면 된다.

 

6. Brandt를 삽입한다.

 

 

Brandt를 삽입할때 Srinivasan, Katz가 모두 Comp.Sci로 bucket이 꽉찼고 prefix를 나타내는 숫자가 모두 3이기 때문에,  BAT를 늘리고 bucket을 늘리는 과정을 하면 된다고 생각할 수 있다. 하지만 여기서는 그렇게 해결이 안 된다!

왜냐하면 다 같은 Comp.Sci기 때문에 bucket을 늘려도 해결이 되지 않는다.

따라서 여기서는 overflow bucket을 한다!

Extendable Hashing의 삽입과정은 위와 같이 일어난다.

 

---

Extendable Hashing의 장단점

 

이제 장단점을 살펴보자.

 

 

장점으로는, 파일이 커져도, 해싱 성능이 감소되지 않는다는 것이다!

또한, 딱 필요한 공간만 쓰기 때문에 space의 낭비가 적다.

 

 

단점으로는, BAT를 거쳐야 한다는 것이다.만약 BAT가 굉장히 크다면 BAT에서 찾는 시간이 걸릴 수 있다. 따라서 어떠한 경우에는 BAT 자체를 B+트리로 만드는 경우도 있다.또한, BAT의 크기를 바꾸는게 꽤나 비싼 연산이다.

 

 

이러한 Hashing 기법은 아래와 같이 특정 값을 찾는 동등 비교 SQL 쿼리일 때 효율적으로 동작할 수 있다.

select *
from example
where A=value;

 

 

하지만, 아래와 같은 range scan일 때 비효율적이다. 왜냐하면, Hash Index는 대다수의 데이터베이스에서 secondary index이기 때문에 원하는 대로 저장되어있지 않기 때문에 찾는데 시간이 매우 오래 걸리기 때문이다.

select *
from example
where A<big_value and A>small_value;

 

 

마지막으로 이러한 hash index를 PostgreSQL 15, MySQL 8.0에선 지원하고 있다.

하지만 Oracle 19c에선 지원하지 않고 있다.

 

 

더 알고 싶다면 아래 글을 참고하자!

https://durumiss.tistory.com/30

MySQL, Oracle, PostreSQL 비교 분석하기

 

 

 

참고 :

Database System Concepts 7th edition