컴퓨터공학, 컴활, 컴공 등 데이터베이스 과목 핵심 요점 정리 1. Hashing(1)

1. Hashing(1)

1. 직접파일의 개념

 

직접파일은 레코드의 주소를 이용하여 원하는 레코드를 직접접근 하는 파일입니다. 여기에서는 우선 어떻게 주소를 결정할 수 있고, 그 과정에서 발생할 수 있는 문제점은 무엇인지 생각해 봅시다.

 

⑴ 키를 이용하여 레코드를 액세스하는 방법

① 함수 계산에 의한 방법

→ 키를 정해진 함수에 입력하여 주소를 계산한다.

함수 계산에 의한 방법

② 인덱스를 사용하는 방

→ 인덱스 내에서 액세스하려는 키 값에 대한 항목을 검색하여 액세스할 데이터

파일의 주소를 찾는다.

→ 인덱스 : 키 값과 해당 키 값을 갖는 레코드가 저장된 주소를 모아 놓은 자료구조

인덱스를 사용하는 방법

※ 함수 계산 방법은 인덱스를 사용하는 방법과는 달리 레코드의 주소를 구하기 위해 별도의 파일을 액세스 하지 않는 이점이 있어 직접파일은 함수 계산에 의해 레코드 주소를 구하여 데이터 파일을 액세스하는 방식을 사용한다.

 

⑵ 직접파일의 특성

직접파일은 함수 계산에 의해 레코드 주소를 구하여 데이터 파일을 액세스하는 방식이다.

→ 직접접근이란 주소를 지정하여 해당되는 위치만을 접근하는 방식을 말한다.

그러므로 직접파일이란 레코드의 주소를 지칭하여 원하는 레코드를 직접 접근하는 파일을 의미한다.

→ 이와 같이 주소를 이용하여 레코드를 직접접근 함으로써 레코드를 검색하는 알고리즘의 시간 복잡도는 O(1)이 되도록 하는 것을 목표로 한다.

→ 주소가 레코드의 키라면 이 주소를 이용하여 레코드를 바로 접근할 수 있지만, 일반적으로 주소와 키는 다르다. 직접파일에서는 레코드의 키를 주소로 사상(mapping)하는 함수를 정의하여 주소를 계산하도록 한다.

 

⑶ 직접파일의 예

레코드의 키를 정해진 함수에 넣어 계산된 결과를 주소로 사용하여 레코드를 액세스한다.

① 키 값이 ‘이민수’인 레코드를 저장하려면 먼저 키를 미리 정의한 함수에 넣어 계산한다.

② 계산된 결과인 3을 레코드의 주소로 사용한다.

③ 이와 같이 정해진 함수를 통해 계산된 주소를 그 레코드의 홈 어드레스라고 한다.

④ 모든 레코드를 홈 어드레스에 저장하였다면, 어느 레코드든 키가 주어지면 단 한번의 액세스로 검색할 수 있다.

직접파일의 예

(4) <키 → 주소> 사상에서의 충돌 문제

① 레코드의 키를 주소로 사용하면 주소를 계산하는 과정이 필요하지 않겠지만, 실제 응용서 이와 같은 상황은 발생하지 않는다. 키는 응용에 따라 다양한 형태의 값이 될 수 있다. 일반적으로 주소 공간은 파일에 저장하려는 데이터의 양에 따라 결정하게 되는 유한한 크기의 연 속적인 정수의 집합이다.

mapping에서의 충돌 문제

② 실제 레코드 어커런스들에서 사용되는 값들의 집합은 전체집합, 즉, 유효한 키 값의 집합의 부분집합이다. 일반적으로는 사용된 값들의 집합은 전체집합의 크기에 비해 매우 작다.

③ 주소 공간은 대상 레코드들을 모두 저장하기에 충분하게 정하므로 실제로 사용된 키 값의 집합은 주소의 집합에 비해 작지만, 키의 전체집합 중 어느 것이 사용되었는지에 대한 정보가 사전에 제공되는 것이 아니기 때문에 키의 전체집합이 함수의 정의역이 된다.

④ 정의역의 원소 수가 치역의 원소 수보다 크므로 사상함수는 단사함수(1:1 함수)가 될 수 없다.

⑤ 단사함수가 아니라면 정의역의 서로 다른 원소(즉, 서로 다른 키 값)이 동일한 치역의 원소(즉, 주소)에 사상될 수 있음을 의미한다.(즉, 서로 다른 키 값이 하나의 주소와 연결될 수 있다.)

충돌(Collision)	직접파일에서 서로 다른 키 값을 가지고 있는 2개 이상의 레코드가 동일한 주소로 사상되는 현상
동의어(synonym)	동일한 주소에 사상된 서로 다른 키를 갖는 레코드들

 

(5) 충돌 발생의 예

주민등록번호를 키로 하여 최대 1,000명에 대한 레코드를 저장하기 위한 직접파일을 구성하는 경우

①

키의 공간 : O O O O O O - O O O O O O O

충돌 발생의 예1

⇒ 각 자리에 0~9 중 하나의 숫자가 나올 수 있다고 가정할 때, 정의역은 1013개의 값으로 구성된 집합이지만, 그 중 1,000개 이내의 값만이 실제로 레코드 어커런스의 키로 사용될 것이다. 그러나 1013개의 값 중 어느 값들이 사용될지는 대상이 되는 사람들에 따라 결정되므로 파일을 설계할 때 미리 알 수 있다.

② 주소 공간 : 1,000개(0부터 999번지까지)

⇒ 1013개의 원소를 1,000개의 원소에 사상하는 함수를 설계

⇒ 1013개의 원소로 구성된 집합을 1,000개의 파티션으로 분할하는 것으로 볼 수 있다. 하나 하나의 파티션은 각각 0, 1, 2, …, 999번지로 사상되는 키들의 집합이라 볼 수 있다.

③ 만일 하나의 파티션에서 하나씩만 실제 레코드 어커런스로 생성되어 파일에 저장된다면 모든 레코드 어커런스들은 자기 자신의 홈 어드레스에 사상될 것이다.

④ 그러나 파티션을 분할할 때(즉, 주소계산 함수를 설계할 때) 어떠한 레코드 어커런스가 발생하게 될 것인지 알 수 없는 상황에서 무작위로 분할하므로 한 파티션 내에 레코드 어커런스가 2개 이상 존재할 수 있다.

이와 같은 상황이 바로 충돌이다.