[Database] Indexing-Hashing

static hashing

 

일반적으로 bucket이라고 부르는 storage space는 4KB입니다. *OS의 Page단위와 맞추기 위해서. hash function은 bucket의 위치를 가르키는데 사용됩니다. search key의 값을 hash function h에 넣어 bucket의 address를 가져옵니다. 서로 다른 search key를 h의 입력으로 넣어도 같은 bucket address를 가르킬 수도 있습니다. 따라서 bucket 안에서의 탐색 또한 필요합니다.

 

hash index는 bucket에 records들의 address(pointer)들이 있는 것을 말하며, hash file-organization은 bucket안에 실제 records들이 존재하는 것을 말합니다. *b+-tree index file과 b+-tree file organization의 차이를 생각하면 됩니다.

2025.05.14 - [[학교 수업]/[학교 수업] Database] - [Database] Indexing - B+-tree

[Database] Indexing - B+-tree

 

이때 static hashing은 # of bucket이 고정된 것을 말합니다. 한 번 할당된 bucket은 다시 할당되지 않습니다:

static hash example

 

Handling of bucket overflows

 

bucket이 가득 차는 경우를 bucket overflow라고 부르며, bucket overflow는 (1) 충분히 많지 않은 # of bucket, (2) # of bucket은 충분하지만 records들이 불균형한 저장때문일 수 있습니다. 이런 skewness의 이유로는 (1) 같은 search key를 갖는 records들이 많을 수도 있고, (2) 불균형한 분포를 만들어내는 hash function 때문일 수 있습니다.

 

bucket overflow가 발생할 수 있는 확률을 줄일 수는 있지만, 아에 제거할 수는 없습니다. 따라서 이를 overflow buckets을 이용하여 handling할 수 있습니다.

 

Overflow chaining

 

먼저 closed addressing(closed hashing) 방법은 hash function의 결과값을 바꾸지 않고(그래서 closed라고 부름) 결과에 해당하는 bucket에 데이터를 넣어주기는 합니다. 그러나 bucket의 공간이 가득 찬 경우 새로 bucket을 만들어 뒤에 Linked list와 같이 붙여서 운용합니다. 하지만 이 방법은 해당 bucket의 뒤에 달린 bucket들이 많아지면 많아질수록 성능이 O(1)에서 O(N)으로 늘어날 수 있습니다.

 

또 다른 대안으로 open hashing 방법이 있습니다. 이는 Linear probing 방법이 대표적인데, cyclic order로 바로 다음의 bucket에 저장하는 것입니다. 이 방법은 closed addressing방법과 마찬가지로 bucket overflow가 많아지면 많아질수록 성능이 떨어진다는 단점이 있습니다.

closed addressing (closed hashing)

 

Example of Hash file organization

 

example of hash file organization

 

Deficiencies of static hashing

 

이런 static hashing의 hash function h는 고정된 수의 bucket address와 search key를 서로 mapping합니다. 하지만 database의 크기가 시간이 지남에 따라 늘어나거나 줄어드는 경우, (1) 초기 bucket의 수를 작게 했을 때, overflow로 인한 성능 저하가 발생할 수 있고, (2) 초기 bucket의 수를 크게 했을 때는 bucket에 공간을 충분히 활용하지 못하고 많은 공간이 죽을 것입니다. *bad memory utilization.

 

이를 Rehashing을 통해 해결할 수 있습니다. 주기적으로 hash function을 교체해주어서 skewness등의 문제들을 해결하는 것입니다. 하지만 hash function이 교체될 때마다 이에 해당하는 모든 records들의 정보 또한 이동해야하기 때문에 비용이 비싸다는 단점이 존재합니다.

 

더 나은 해결책으로는 dynamic하게 bucket의 크기를 조정하는 것입니다. 그리고 이를 dynamic hashing이라고 합니다.

 

Dynamic Hashing

 

dynamic hashing에는 두 가지 방법이 존재합니다. 우선 기본적인 dynamic hashing의 아이디어는 bucket의 수를 두 배씩 늘리는 것입니다. 이를 directory를 이용하면 (1) Extendible Hasing, 그게 아니라 순차적(Linear)으로 진행하면 (2) Linear Hashing 이라고 부릅니다.

 

Extendible hashing

 

Extendible hashing은 hash key의 postfix 혹은 prefix만을 사용합니다. 예시를 들며 설명하겠습니다:

우선 postfix의 길이를 i bits로 설정합니다. 그렇다면 bucket address를 담는 directory의 크기는 2^i이 됩니다. *hash key의 2진수 표현의 뒤 i개의 bits를 이용합니다. 따라서 directory의 크기가 2^i입니다. 처음에는 i=0에서 시작하며, i는 database의 크기에 따라 줄어들거나 커질 수 있습니다.

 

여러개의 directory entries들이 하나의 bucket을 가르킬 수 있습니다. 즉 실제 bucket의 수는 2^i보다 작습니다.

general extendible hash structure

 

이때 global depth는 hash key의 몇 번째 postfix까지를 참고하는 지를, local depth는 bucket에 records들을 담을 때 몇 번째 postfix까지를 참고하는 지를 나타냅니다.

Extendible Hashing - How it works

 

만약 search key로 7이 들어오는 경우, Global depth가 2이기 때문에, 뒤에서 두 번째 bits만을 참고하여 directory entry를 통해 bucket을 찾습니다. 이때 local depth가 1인 bucket에 경우 두 개의 directory entry들이 참조하고 있음을 확인할 수 있습니다. *여러개의 directory entries들이 하나의 bucket을 가르킬 수 있습니다. 어쨋든 bucket을 찾고 거기에 insert해주면 됩니다.

 

Extendible Hashing - How it works

 

여기에 13을 insert하는 경우 directory entry를 따라 가운데 bucket에 들어오는데, bucket overflow가 발생했습니다. 이런 경우 bucket split을 진행합니다. bucket split은 overflow가 발생한 bucket의 local depth가 global depth보다 작은 경우 진행합니다. local depth의 수를 1개 증가시키며, 새로운 bucket을 만들어 overflow에 대응합니다:

Extendible Hashing - How it works

 

*하나의 bucket을 참조했던 두 개의 directory entries가 나눠졌습니다.

 

만약 G=L인 상황에서 bucket overflow가 발생하면 어떡할까요?

Extendible Hashing - How it works

 

위 그림과 같이 29가 insert되는 경우 왼쪽에서 두 번째에 있는 bucket에 들어가야합니다. 하지만 해당 bucket은 꽉 차있으므로, overflow가 발생하고 G=L이기에 bucket split도 불가능합니다. 이때는 directory doubling을 진행합니다:

Extendible Hashing - How it works

 

Global depth를 1 늘리고, directory의 크기를 두 배로 늘립니다. 이렇게 한 후 bucket split을 진행하면 됩니다.

 

Extendible Hashing vs. Other Schemes

 

Extendible hashing은 다른 방법들에 비해 database의 크기가 커지면서 발생하는 성능저하가 발생하지 않습니다. *closed addressing의 경우 overflow가 발생하면 할 수록 성능이 O(1) 에서 O(N)으로 감소하는데 비해 이는 그렇지 않습니다. 또한 memory공간의 효율성, space overhead가 적습니다.

 

하지만 directory를 경유하면서 추가적인 level이 생겼고, bucket address table(directory)가 점점 커지면 memory공간에 들어가지 않을 수도 있습니다. *크기가 2배씩 커지므로 overflow가 잦아지면 그럴 수 있습니다. 이는 B+-tree로 directory를 관리하면 해결할 수 있긴 합니다. 마지막으로 bucket address table을 두 배로 늘리면서 발생하는 비용이 큽니다. 

 

이에 대한 대안으로 Linear Hashing이 존재합니다.

 

Linear hashing - a lazy approach

 

이 방법은 long overflow chain 문제를 directory없이 해결할 수 있습니다. Temporary overflow page를 이용하면 됩니다. 이는 round-robin 방법을 이용하여 bucket을 split합니다. Linear hashing은 선형적으로 미리 미리 bucket split을 진행함으로써 overflow chain이 길어지는 것을 방지합니다.

 

Linear hashing - algorithm

 

Linear hashing 알고리즘은 round, 혹은 level을 기준으로 진행됩니다. 각 level에 해당하는 bucket의 수는 초기 bucket의 수 N에 대하여 N * 2^level 입니다. Next는 일종의 pointer로 해당 level에서 split이 진행되는 bucket을 가르킵니다. 즉 0부터 Next-1 번째 bucket은 이미 split이 진행되었으며, Next부터 나머지 bucket들은 split이 진행되어야하는 bucket들 입니다.

 

Next는 다음 bucket으로 향하며, 모든 bucket을 선형적으로 한 바퀴 돌았으면 다음 라운드로 넘어갑니다. 이때 level = level + 1이 되며, Next는 다시 0이 됩니다.

 

Linear hashing - insert

 

Insert의 경우 bucket을 찾았을때, 공간이 남아있으면 그냥 삽입합니다. 만약 공간이 없다면, temporay overflow page를 만들어 해당 데이터를 넣어줍니다. 그리고 Next가 가르키고 있는 bucket을 split합니다. temporay overflow page로 인해 생긴 overflow chain은 round-robin에 의해 돌아가고 있는 Next에 의해 알아서 split되며, 더 이상 길어지지 않습니다.

Linear hashing - Overview

 

split image bucket은 이번 round에서 Next에 해당하는 bucket이 split되어 새롭게 생성된 bucket들이 저장되어있는 공간을 말합니다.

 

Linear hashing - How it works

 

Linear hashing - how it works

 

우선 insert되는 데이터 43을 해당 hash key에 맞는 bucket에 넣어줍니다. 이때 hash key는 11로, 이에 해당하는 bucket은 이미 가득차서 overflow가 발생합니다. 그렇다면 temporary overflow page를 달아주어 데이터를 저장합니다. 그 후 Next에 해당하는 bucket은 split을 진행합니다. *새롭게 생성된 bucket은 split image bucket에 넣어줍니다.

 

 

Linear hashing - how it works

Linear hashing - how it works

 

Linear Hashing Search Algorithm

 

만약 데이터를 찾고 싶은 경우, 찾고 싶은 데이터의 hash key가 Next가 가르키고 있는 hash key의 값보다 큰지 작은지를 알아야합니다. 만약 search key의 hash 값이 Next보다 작다면 이는 이미 split되었다는 것이므로, 원래 hash key가 가르키는 bucket 뿐만 아니라 split image bucket에 들어있는 h(r) + N_level 번째 bucket또한 탐색해봐야 합니다.

 

만약 hash key가 Next보다 크거나 같다면 split이 아직 진행되지 않았다는 것이므로, hash key에 해당하는 bucket만 탐색하면 됩니다.

Linear hashing - how it works

 

Comparison of ordered indexing and hashing

 

이 둘을 비교할 때는 (1) 주기적인 re-organization의 비용, (2) insertion과 deletion의 상대적인 빈도, (3) worst-case에 대한 access time의 average time의 최적화가 필요한지, (4) 기대되는 query의 종류가 무엇인지(예를 들어: point query vs. range query) 등을 비교해야합니다.

 

Multiple-Key Access and Bitmap Index

 

만약 두 개 이상의 key에 대해 접근하는 경우 Bitmap index를 고려해볼 수 있습니다.

example

 

다음과 같이 dept_name과 salary에 대한 key 두 개에 대해 검색을 하고싶은 경우가 있습니다. 이는 하나의 attr.에 대해 검색을 진행한 후, 그 결과 record들에 대해 나머지 attr.에 대한 검색을 진행하는 방법으로 조건에 맞는 records들을 찾을 수 있습니다. 하지만 bitmap index를 사용하면 한 번에 찾을 수 있습니다.

 

Bitmap index는 multiple key에 대한 query에 강점을 보입니다. 이는 고정된 길이의 records들에 대해 사용하며(*고정된 양의 records N에 대해 수행하는 것이 훨씬 적용하기 편합니다), 적은 수의 구분되는 값을 갖는 attr.에 대해 사용할 수 있습니다. 만약 salary와 같인 연속된 숫자 domain의 경우는 구간을 나눠서 관리해야합니다.

 

bitmap은 그냥 간단한 bit array로 구성됩니다.

다음과 같은 table이 존재하는 경우 각 attr.에 대한 record들은 다음과 같이 관리됩니다:

Bitmap indices

 

이를 이용하면 and나 or, not등을 사용하는 multiple key query에 대해 효율적으로 대응할 수 있습니다:

Bitmap indices

 

*만약 record의 길이가 매우 길거나, 자주 변한다면 해당 bitmap을 관리하기 힘듭니다. 또한 각 구분되는 attr.에 대해서 0, 1로 구분하기 때문에 연속된 값을 갖는 attr.에 대해서는 부적절할 수 있습니다.

 

이는 relation size에 비해 매우 작은 공간으로 relation들을 표현할 수 있다는 장점이 있습니다: