[데이터베이스] 저장 구조 - 해싱 방법, 저장 구조의 비교

해싱 방법

• 해시 함수를 이용해서 키 값 input에 대한 목표 레코드의 주소로 한 번에 찾아가는 방법이다.
• 직접 탐색에는 힙이나 B+tree에 비해서 훨씬 빠를 것이다.
• 여러 해싱 방법 중에서 버킷 해싱이라는 방법이 있다. 여기서 버킷은 하나의 주소를 가지면서 하나 이상의 레코드를 저장할 수 있는 파일의 한 구역을 지칭한다. 각 버킷은 연결 리스트와 같은 자료 구조로 구현된다.
• 버킷 해싱은 키를 넣으면 해시 함수를 거쳐서 버킷 주소를 알려주는 구조다.
• 만약 해시 함수가 출력 값을 고르게 분포하지 않을 경우, 서로 다른 데이터가 같은 버킷에 할당되는 충돌 현상이 발생한다.

해시 충돌(hash collision)

• 해시 충돌은 어쩔 수 없이 벌어지는 현상이다. 해시 함수의 출력 값이 무한하지 않기 때문이다.
• 이러면 특정 버킷이 오버플로우 될 수 있고, 오버플로우될 때 그만큼 새로운 버킷 접근에 대한 Disk I/O가 추가되어 overhead가 발생한다. 그래서 버킷 해싱이라는 방법은 잘 안 쓰고, 충돌 문제에 대비하기 위한 확장성 해싱이라는 방법을 사용한다.

 

확장성 해싱(coherent hashing)

• 확장성 해싱 함수에는 키 값을 넣으면 일정 길이의 비트 스트링(모조키, psuedo key)가 나온다.
• 모조키의 처음 d 비트를 디렉토리라는 논리적 그룹에 대한 인덱스로 사용한다.
• 디렉토리 헤더에는 정수값 d를 저장하고, 이를 전역 깊이(depth)로 사용한다.
• 각각의 디렉토리에는 버킷들을 지시하는 2^d개의 포인터가 존재할 것이다.
• 디렉토리는 디스크에 저장된다.

예시

• 버킷에는 정수 값 p(<= d)가 저장된 헤더가 존재한다.
• p는 지역 깊이(local depth)라고 부르고, 버킷에 저장된 레코드들의 모조키들이 처음부터 p 비트까지 모두 동일하다는 뜻이다.
• 위 그림 예시) p가 3인 첫 번째 버킷은 레코드의 모조키가 시작하고 있는 비트 스트링이 000 이라는 뜻이다.
• 위 그림 예시) p가 3인 두 번째 버킷은 레코드의 모조키가 시작하고 있는 비트 스트링이 001 이라는 뜻이다.
• 모조키의 처음 d 비트를 디렉토리에 대한 인덱스로 사용한다.

예시

1) 키 값 k가 모조키 110110000010으로 나왔다.
2) d가 3이니 모조키의 처음 3비트를 사용한다. 디렉토리를 보니 7번째 엔트리인 110에 접근하면 되겠다.
3) 110엔트리는 4번째 버킷에 대한 포인터를 담고 있다.
4) 이는 키 값 k를 가지고 있는 레코드가 4번째 버킷에 저장되어 있다는 뜻이다.
5) 4번째 버킷에 접근하여 원하는 레코드를 찾는다.

 

확장성 해싱의 저장

• 모조키의 d비트를 이용하여 디렉토리에 접근하고, 디렉토리의 포인터가 지시하는 버킷에 데이터를 저장하면 된다.
• 만약 버킷에 자리가 없으면(overflow) 분할을 해야 할 수도 있다.
• 분할 시 버킷의 로컬 뎁스에 1을 더해주고, 새로운 버킷과 기존 버킷에 데이터를 적절히 분산시킨다.
• 기존 버킷과 새로 할당된 버킷의 p값은 모두 p+1이 되는데, 만약 d < (p+1)이 될 경우, d값도 증가시켜 준다.
• 이처럼 디렉토리가 확장될 시에는 디렉토리 헤더와 버킷 헤더에 할당된 깊이 값이 모두 증가하고, 포인터가 새롭게 할당된다.

 

-- 해시 컬럼을 users 테이블에 추가
ALTER TABLE users ADD COLUMN email_hash BINARY(16);

-- 레코드 삽입에 해시 값도 포함하기, MD5는 해쉬 함수의 종류 이름.
INSERT INTO users (email, email_hash, other_columns)
VALUES ('user@example.com', UNHEX(MD5('user@example.com')), 'other values');

-- users 테이블에 해쉬 속성에 대한 인덱스 만들기
CREATE INDEX ix_email_hash ON users (email_hash);

 

해시 왜 써요?

• 직접 검색이 가장 빠르다. 사실상 상수 시간 O(1)이다.
• B+Tree는 O(log N)만큼 리프 노드까지 무조건 찾아가야 한다. B+Tree도 충분히 빠르지만, 해시가 더 빠르다.
• 해시는 동등 비교 조건을 처리할 때 비교적 유용하다. ( =, IN, IS, IS NOT..)
• 범위 혹은 부정 비교 조건에는 인덱스를 사용하는 것이 더 좋을 수 있다. ( >=, LIKE, <>..)

 

저장 구조의 비교

• 저번 글과 이번 글로써 3가지 DB 파일 저장 구조를 알아봤다. 순차 방법, 인덱스 방법, 해시 방법이다.
• 1) 정렬된 모든 레코드에 대한 순차 탐색이 제일 빠른 구조는 B+Tree를 이용한 인덱스 방법이다.
• 2) 만약 where 절에 동등 조건이 주어졌을 때 직접 탐색은 해시가 가장 빠르고,그다음은 B-Tree가 좀 더 빠르다. 운이 좋으면 리프 노드까지 탐색 안 해서 B+Tree보다 더 빠르다.
• 3) 범위 검색은 B+Tree가 유리하다.
• 4) 모든 레코드들을 항상 업데이트하고 전체적으로 읽어서 특정한 처리를 할 때는 힙 구조를 사용하는 것이 좋다. 어차피 다 읽을 거면 힙이 좋고, 차선책으로 둘 수 있는 구조는 B+Tree겠다.
• 5) 삽입 연산이 가장 빠른 구조는 힙 구조다. O(1) 걸린다. 파일 끝으로 가면 되니깐, 그다음에 빠른 구조는 해시다. 얘도 한 번에 찾아가는 편이니깐(Function -> Directory -> Bucket). B나 B+는 O(log N) 걸린다.
• 6) 삭제 연산이 가장 빠른 구조는 해시 구조다.

위 질문에 대한 대답이 항상 정답은 아니겠지만, 저장 구조들에 대한 도식을 머릿 속에 담고 있으면, 상황에 맞춰 사용할 수 있을 것이다.