Chapter 11: Indexing and Hashing

Presentation on theme: "Chapter 11: Indexing and Hashing"— Presentation transcript:

1 Chapter 11: Indexing and Hashing

2 Chapter 12: 인덱싱과 해슁 기본 개념 순서 인덱스 B+ - 트리 인덱스 파일 B - 트리 인덱스 파일 정적 해슁
동적 해슁 순서 인덱싱과 해슁의 비교 SQL에서의 인덱스 정의 다중 키 액세스

3 기본 개념 원하는 데이터를 액세스하는데 속도를 증가 시키기 위해 사용하는 인덱싱 기법 예를 들어, 도서관에서의 저자 목록
검색 키 (Search Key ) - 파일내의 레코드를 탐색하는데 사용되는 애트리뷰트 또는 애트리뷰트의 집합 인덱스 파일은 다음과 같은 형식의 레코드 (인덱스 엔트리로 불리움) 로 구성된다. 인덱스 파일은 일반적으로 원래의 파일보다는 훨씬 작다. 두 가지 기본 인덱스의 종류 : 순서 인덱스 (Ordered indices) : 검색 키가 정렬된 순서로 저장된다. 해쉬 인덱스 (Hash indices) : 검색 키가 해쉬 함수를 사용해 버켓들에 균등하게 분산된다. search-key pointer

4 인덱스 평가 기법 다음을 근거로 하여 평가되는 인덱싱 기법 효율적으로 지원되는 액세스 유형. 예를 들어,
애트리뷰트에 특정 값을 가진 레코드들 (point query) 또는 특정 범위의 값에 속하는 애트리뷰트 값을 가진 레코드들 (range query) 액세스 시간 삽입 시간 삭제 시간 공간 비용

5 순서 인덱스 순서 인덱스 (ordered index) 에서는 인덱스 엔트리가 검색 키 값의 정렬된 순서에 따라 저장된다. 예를 들어, 도서관에서의 저자 목록 주 인덱스 (primary index) : 순차적으로 정렬된 파일에서는 검색 키 인덱스가 파일의 순차적인 순서를 지정한다. 또한 군집 인덱스 (clustering index) 라고 부른다. 주 인덱스의 검색 키는 일반적으로 그렇지만 반드시 주 키일 필요는 없다. 2차 인덱스 (secondary index) : 검색 키 인덱스가 파일의 순차적인 순서와는 다른 순서를 지정한다. 또한 비군집 인덱스 (non-clustering index) 라 하기도 한다. 인덱스 순차 파일 (Index-sequential file) : 주 인덱스로 정렬된 순차 파일

6 밀집 인덱스 파일(dense Index Files)
밀집 인덱스 - 인덱스 레코드가 파일내의 각 검색 키 값에 대해 나타난다. 예: instructor 릴레이션의 ID 애트리뷰트에 대한 인덱스

7 밀집 인덱스 파일 (계속) dept_name 애트리뷰트로 정렬된 instructor 릴레이션의 dept_name 애트리뷰트에 대한 밀집 인덱스

8 희소 인덱스 파일 (sparse index files)
희소 인덱스: 몇 개의 검색 키 값에 대한 인덱스 레코드만을 포함한다. 레코드들이 검색키 순서로 정렬된 경우에 적용 가능하다. 검색 키 값 K를 가진 레코드를 찾는 방법: K 보다 작은 것 중에서 가장 큰 검색 키 값을 가진 인덱스 레코드를 찾는다 인덱스 레코드가 가리키는 레코드에서 시작하여 순차적으로 파일을 검색한다.

9 희소 인덱스 파일 (계속) 밀집 인덱스와 비교: 공간이 적게 소요되고 삽입과 삭제를 위한 유지 비용이 덜 든다.
레코드를 찾는데는 일반적으로 밀집 인덱스보다 느리다. 좋은 손익 비교 (good tradeoff) : 블록에서 가장 작은 검색 키 값에 대응하는 파일 내 각 블록마다 하나의 인덱스 엔트리를 가진 희소인덱스를 구성한다.

10 2차 인덱스 예제 인덱스 레코드는 특정 검색 키 값을 가진 실제 레코드에 대한 포인터를 내포하는 버켓을 가리킨다.
Secondary index on salary field of instructor 인덱스 레코드는 특정 검색 키 값을 가진 실제 레코드에 대한 포인터를 내포하는 버켓을 가리킨다. 2차 인덱스는 밀집 인덱스이어야 한다. 10

11 주 인덱스와 2차 인덱스 인덱스는 레코드를 검색할 때 실질적인 이점을 제공한다.
그러나: 인덱스 갱신은 데이터베이스 수정에 추가 비용을 부과시킨다 -- 파일 수정 시 파일상의 각 인덱스가 갱신되어야 한다. 주 인덱스를 이용한 순차 검색은 효율적이지만, 2차 인덱스를 이용한 순차 검색은 비용이 많이 든다 각 레코드 액세스는 디스크로부터 새로운 블록을 가져 올 경우가 발생할 수 있다 메모리 액세스 (about 100 nanoseconds)에 비하여 블록 액세스는 시간이 많이 든다 (about 5 to 10 milliseconds). 11

12 다단계 인덱스 (multilevel index)
주 인덱스가 메모리에 들어 가지 않으면, 액세스하는데 비용이 많이 든다. 해결법: 인덱스 레코드에의 디스크 액세스 횟수를 줄이려면, 디스크에 저장된 주 인덱스를 순차 파일로 취급하여 그에 대해 희소 인덱스를 구축한다. 외부 인덱스 (outer index)– 주 인덱스의 희소 인덱스 내부 인덱스 (inner index ) – 주 인덱스 파일 외부 인덱스 조차 너무 커서 메인 메모리에 들어가지 않는다면, 또 다른 인덱스 계층이 생성 될 수 있다. 모든 계층의 인덱스는 파일에 삽입 또는 삭제 시 갱신되어야 한다.

13 다단계 인덱스 (계속)

14 인덱스 갱신 : 삭제 삭제한 레코드가 파일 내에서 특정 검색 키 값을 가진 유일한 레코드라면, 검색 키 또한 인덱스로부터 삭제된다. 단일 계층 인덱스 삭제 : 밀집 인덱스 – 검색 키의 삭제는 파일 레코드 삭제와 유사하다. 희소 인덱스 – 검색 키의 엔트리가 인덱스 내에 존재하면, 그 엔트리를 파일내의 다음 검색 키 값(검색 키 순으로)으로 대치함으로써 삭제한다. 다음 검색 키 값이 이미 인덱스 엔트리를 가지고 있으면, 그 엔트리는 대치되는 대신 삭제된다.

15 인덱스 갱신 : 삽입 단일 계층 인덱스 삽입 삽입할 레코드에 있는 검색 키를 사용해 탐색을 수행한다.
밀집 인덱스 – 검색 키 값이 인덱스에 없으면, 그것을 삽입한다. 희소 인덱스 – 인덱스에 파일 각 블록에 대한 엔트리를 저장하면, 새로운 블록이 생성되지 않는 한 인덱스가 변할 필요가 없다. 이 경우, 새로운 블록에 나타나는 첫번째 검색 키 값이 인덱스에 삽입 된다. 다단계 삽입(삭제도 마찬가지) 알고리즘은 단일 계층 알고리즘의 단순한 확장이다.

16 2차 인덱스 (secondary indices)
흔히, 어떤 필드(주 인덱스의 검색 키가 아닌)의 값이 어떤 조건을 만족하는 모든 레코드를 찾고자 할 때가 있다. Example 1: ID 순서로 저장된instructor 릴레이션에서 특정 학과(department)의 모든 강사(instructor) 정보를 찾고자 할 수 있다. Example 2: 위와 같은 릴레이션에서 특정 급여 또는 특정 범위의 급여를 받는 모든 강사(instructor) 정보를 찾고자 할 수 있다. 각 검색 키 값에 대해 하나의 인덱스 레코드를 가진 2차 인덱스를 가질 수 있다.

17 B+ - 트리 인덱스는 인덱스 순차 파일의 다른 방법이다.
인덱스 순차 파일의 단점 : 많은 오버플로 블록이 생성되므로, 파일이 커질 때 성능이 저하된다. 전체 파일의 주기적인 재구성이 필요하다. B+ - 트리 인덱스 파일의 장점 : 삽입과 삭제의 부분적 작은 부분의 변화만으로 전체 파일이 자동으로 재구성된다. 성능 유지를 위한 전체 파일의 재구성이 필요하지 않다. B+ - 트리 의 소수 단점 : 별도의 삽입과 삭제 부담과 공간 부담이 있다. B+ - 트리 의 장점이 단점을 능가하므로, 광범위하게 사용된다.

18 Example of B+-Tree

19 B+- 트리 인덱스 파일 (계속) B+ - 트리는 다음과 같은 속성을 만족하는 뿌리를 가진 트리이다:
뿌리로 부터 잎 까지의 모든 경로는 같은 길이를 갖는다. 뿌리 또는 잎이 아닌 각 노드는 2/n ~ n의 자식을 갖는다. 잎 노드는 (n-1)/2 ~ n-1 값을 갖는다. 특수한 경우 : 뿌리가 잎이 아니면, 최소한 2개의 자식을 갖는다. 뿌리가 잎이면(즉, 트리내에 다른 노드가 없으면),0 ~ (n-1) 값을 가질 수 있다.

20 B+- 트리 노드 구조 전형적인 노드 구조 노드 내의 검색 키는 다음과 같은 순서이다.
Ki는 검색 키 값이다. Pi는 잎이 아닌 노드에 대해서는 자식 노드로의 포인터를 나타내고, 잎 노드에 대해서는 레코드 또는 레코드의 버켓으로의 포인터를 나타낸다. 노드 내의 검색 키는 다음과 같은 순서이다. K1 < K2 < K3 < < Kn–1

21 B+ - 트리 내의 잎 노드 잎 노드의 속성 : i = 1, 2, …, n-1에 대해, 포인터 P i는 검색 키 값 K i를 가진 파일 레코드 또는 각 레코드가 검색 키 값 K i를 가진 파일 레코드들의 포인터 버켓을 가리킨다. L i와 L j가 잎 노드이고 i < j이면, L i의 검색 키 값은 L j의 검색 키 값보다 작다. P n은 검색 키 순으로 다음 잎 노드를 가리킨다.

22 B+ - 트리 내의 잎이 아닌 노드 잎이 아닌 노드는 잎 노드에 대해 다단계 희소 인덱스를 이룬다.
n개의 포인터를 가진 잎이 아닌 노드에 대해 : P1이 가리키는 부 트리내의 모든 검색 키는 K1 보다 작다. 2  i  n-1에 대해, Pi 가 가리키는 부 트리내의 모든 검색 키는 Ki-1 보다 크거나 같고 Ki 보다 작은 값을 갖는다. Pn 이 가리키는 부 트리내의 모든 검색 키는 Kn-1 보다 크거나 같다.

23 B+-tree for instructor file (n = 6)
Example of B+-tree B+-tree for instructor file (n = 6) 잎 노드는 3 ~ 5개의 값을 가져야 한다 ((n–1)/2 and n –1, with n = 6). 뿌리 이외의 잎이 아닌 노드는 3 ~ 6개의 자식을 가져야 한다 ((n/2 and n with n =6). 뿌리는 적어도 2개의 자식을 가져야 한다.

24 B+ - 트리에 관한 유의 사항 내부 노드 연결은 포인터로 이루어지므로, B+ - 트리에서는 논리적으로 근접한 블록이 물리적으로 근접해야 할 필요가 없다. B+ - 트리의 잎이 아닌 계층은 희소 인덱스 계층을 이룬다. B+ - 트리는 비교적 적은 수의 계층을 내포한다. 뿌리 노드 아래 계층은 최소한 2* n/2 개의 값을 갖는다. 그 다음 계층은 최소한 2* n/2 * n/2 개의 값을 갖는다. .. 등등. 파일내에 K개의 검색 키 값이 있으면, 트리 높이는 log n/2(K) 보다는 크지 않다. 따라서 검색이 효율적으로 수행될 수 있다. 파일에의 삽입과 삭제는 인덱스가 로그 시간 내에 재구성될 수 있으므로 효율적으로 처리될 수 있다.

25 B+ - 트리에의 질의 검색 키 값이 k인 모든 레코드를 찾아라. C=root
While C is not a leaf node { Let i be least value s.t. V  Ki. If no such exists, set C = last non-null pointer in C Else { if (V= Ki ) Set C = Pi +1 else set C = Pi} } Let i be least value s.t. Ki = V If there is such a value i, follow pointer Pi to the desired record. Else no record with search-key value k exists.

26 B+ - 트리에의 질의 (계속) 파일내에 K개의 검색 키 값이 있으면, 트리 높이는 log n/2(K) 보다는 크지 않다.
노드는 일반적으로 디스크 블록과 같은 크기인 4KB이며, n은 100정도이다 (인덱스 엔트리당 40 바이트). 100만개의 검색 키 값이 있고 n = 100인 경우, 최대 log50(1,000,000) = 4 개의 노드가 탐색에서 액세스 된다. 이것을 100만개의 검색 키 값을 가진 균형 이진 트리와 비교해 보라 – 대략 20개의 노드가 탐색에서 액세스 된다. 각 노드의 액세스에는 대략 20ms가 걸리는 디스크 입출력이 필요 하게 되므로, 위와 같은 차이는 중요한 의미를 갖는다.

27 B+ - 트리에의 갱신 : 삽입 검색 키가 나타날 잎 노드를 찾는다. 검색 키 값이 잎 노드에 이미 존재하면,
레코드를 파일에 추가한다. 필요한 경우, 포인터가 버켓에 삽입된다. 검색 키 값이 없으면, 레코드를 주 파일에 추가한다 (필요하면 버켓을 생성한다). 잎 노드에 공간이 있으면, 적당한 위치의 잎 노드에 (검색 키 값, 레코드/버켓 포인터) 쌍을 삽입한다. 잎 노드에 공간이 없으면, 노드를 분할하고 다음 페이지에서 설명하는 대로 (검색 키 값, 레코드/버켓 포인터) 쌍을 삽입한다.

28 B+ - 트리에의 갱신 : 삽입 (계속) 노드의 분할:
n개의 (검색 키 값, 포인터) 쌍을 정렬된 순으로 취한다 (삽입 되 는 것 포함). 처음 n/2 개를 원래의 노드에 넣고, 나머지를 새로운 노드에 넣는다. 새로운 노드를 p라 하고, k를 p내의 가장 작은 키 값이라 하자. (k, p)를 분할되고 있는 노드의 부모에 삽입한다. 부모 노드가 꽉 차면, 그것을 분할하고 위로 계속 분할해 나간다. 노드의 분할은 꽉 차지 않은 노드가 발견될 때 까지 위로 진행한다. 최악의 경우에는 트리의 높이를 하나 더 증가 시키면서 뿌리 노드가 분할될 수도 있다. Result of splitting node containing Brandt, Califieri and Crick on inserting Adams Next step: insert entry with (Califieri,pointer-to-new-node) into parent

29 B+-Tree Insertion “Adams” 삽입 전과 후의 B+ - 트리

30 “Lamport” 삽입 전과 후의 B+ - 트리
B+-Tree Insertion “Lamport” 삽입 전과 후의 B+ - 트리

31 Insertion in B+-Trees (Cont.)
뿌리가 아닌 노드 분할: 이미 꽉 찬 내부 노드 N에 (k,p) 를 삽입하려고 하는 경우 n+1개의 포이터와 n개의 키 값을 갖는 메모리 영역 M에 N을 복사하시오. (k,p) 를 M에 삽입하시오. M으로부터 P1,K1, …, K n/2-1,P n/2 을 N 노드에 복사하시오. M으로부터 Pn/2+1,K n/2+1,…,Kn,Pn+1 을 새로이 할당받은 노드 N’에 복사하시오. (K n/2,N’) 을 N의 부모 노드에 삽입하시오. Read pseudocode in book! Califieri Adams Brandt Califieri Crick Adams Brandt Crick

32 B+ - 트리에의 갱신 : 삭제 삭제할 레코드를 찾아 주 파일과 버켓(있으면)에서 그것을 제거한다.
버켓이 없거나 버켓이 비게 되면, 잎 노드에서 (검색 키 값, 포인터)를 제거한다. 삭제로 인해 노드가 너무 적은 엔트리를 가지게 되고, 그 노드와 형제 노드의 엔트리들이 하나의 노드에 들어가게 되면, 형제 노드들을 머지하라. 두 노드의 모든 검색 키 값들을 하나의 노드(왼쪽에 있는 것)에 삽입 하고, 다른 노드를 삭제한다. 위의 절차를 이용하여 반복적으로 그의 부모로부터 (K i-1, P i)를 삭제한다. 여기에서 P i는 삭제될 노드의 포인터를 나타낸다.

33 B+ - 트리에의 갱신 : 삭제 그렇지 않고 삭제로 인해 노드가 너무 적은 엔트리를 가지게 되고, 그 노드와 형제 노드의 엔트리들이 하나의 노드에 들어가지 않으면, 포인터 재분배를 수행하라. 양쪽 모두 엔트리의 최소 수보다 더 많이 가지도록 그 노드와 형제 노드간의 포인터를 재분배한다. 그 노드의 부모 노드내의 상응하는 검색 키 값을 갱신한다. n/2 또는 그 이상의 포인터를 가진 노드를 발견할 때까지 노드 삭제가 위로 연쇄적으로 발생할 수 있다. 삭제 후 뿌리 노드가 하나의 포인터만 가진다면, 그것은 삭제되고 유일한 자식이 뿌리가 된다.

34 “Srinivasan” 삭제 전과 후의 B+ - 트리

35 이전 예제의 결과에 대하여 “Singh” 과 “Wu” 를 삭제한 결과
B+- 트리 삭제 예제 (계속) 이전 예제의 결과에 대하여 “Singh” 과 “Wu” 를 삭제한 결과 “Singh” 과 “Wu” 를 포함하는 노드가 반 이하를 채우지 못하였으므로, 왼쪽 형제 노드로부터 의 “Kim”의 값을 빌려 온다. 부모 노드에서 검색키 값이 역시 바뀌고 있다.

36 B+- 트리 삭제 예제 (계속) 이전 예제에서 “Gold” 삭제 전과 후의 B+ - 트리
Katz 이전 예제에서 “Gold” 삭제 전과 후의 B+ - 트리 “Gold ” 와 “Katz” 를 포함하는 노드가 반 이하를 채우지 못하였으므로, 해당 노드는 형제 노드와 머지된다. 부모 노드도 반이하를 채우지 못하였으므로 형제 노드와 머지된다. 머지 단계에서 두 노드를 분리 시키던 값 (부모 노드에서) 이 내려온다. 뿌리 노드가 하나의 자식을 갖게되어 삭제된다.

37 B+ - 트리 파일 구조 인덱스 파일 성능 저하 문제는 B+ - 트리 인덱스를 사용해 해결한다.
잎 노드에는 여전히 반 이상이 차야 한다. 레코드는 포인터보다 크기 때문에, 잎 노드에 저장될 수 있는 레코드의 최대 수는 잎이 아닌 노드내 포인터의 수보다 적다. 삽입과 삭제는 B+ - 트리 인덱스 엔트리의 삽입 및 삭제와 같은 방법으로 처리된다.

38 B+ - 트리 파일 구조 (계속) Example of B+-tree File Organization
레코드는 포인터보다 많은 공간을 사용하므로, 공간 활용도가 중요하다. 공간 활용도를 증가 시키려면, 분할 및 머지를 수행을 하는 동안 재분배에서 더 많은 형제 노드를 참여시킨다. 재분배에 2개의 형제 노드를 참여시켜, 그 결과 각 노드는 최소한 개의 엔트리를 갖게 한다.

39 인덱싱에 따른 고려 사항 레코드 위치 변경 과 2차 인덱스
레코드가 이동하면, 해당 레코드에 대한 포인터 정보를 저장하고 있는 2차 인덱스가 이에 따라 갱신되어야 한다. B+- 트리 파일 구조에서 노드 분할에 따른 오버헤드가 매우 커진다. 해결 방법 : 2차 인덱스에서 레코드 포인터 대신에 주 인덱스 검색키를 사용한다. 해당 레코드 검색을 위하여 주 인덱스를 부가적으로 탐색하여야 한다. 질의 처리를 위한 비용이 증가하지만, 노드 분할에 따른 오버 헤드는 작아진다. 주 인덱스의 검색키가 유일 값 특성을 갖지 못하면 (non-unique) record-id 값을 추가하라. 39

40 B - 트리 인덱스 파일 B+ - 트리와 유사하지만, B - 트리는 검색 키 값이 단 한번만 나타나도록 하여 검색 키의 중복 저장을 제거한다. 잎이 아닌 노드내 검색 키는 B - 트리내 어디에도 나타나지 않는다 ; 잎이 아닌 노드내 각 검색 키에 대해 추가의 포인터가 내포되어야 한다. 일반적인 B - 트리 잎 노드의 구조 잎이 아닌 노드 - 포인터 B i는 버켓 또는 파일 레코드 포인터이다.

41 B- 트리 인덱스 파일 예제 동일 데이터에 대한 B-tree (위) 와 B+-tree (아래) 구조

42 B - 트리 인덱스 파일 (계속) B - 트리 인덱스의 장점 : 동등한 B+ - 트리보다 적은 트리 노드를 사용한다.
때로는 잎 노드에 도달하기 전에 검색 키 값을 찾을 수 있다. B - 트리 인덱스의 단점 : 모든 검색 키 값 중의 극히 일부만이 조기에 찾을 수 있다. 잎이 아닌 노드가 더 크므로, 전개(fan-out)가 감소한다. 따라서, B -트리는 동등한 B+ - 트리보다 일반적으로 높이가 더 높다. B+ - 트리보다 삽입과 삭제가 더 복잡하다. B+ - 트리보다 구현이 더 어렵다. 일반적으로, B - 트리의 장점이 단점을 능가하지는 못한다.

43 다중 키 액세스 특정 유형의 질의에 여러개의 인덱스를 사용한다. Example: select ID from instructor
where dept_name = “Finance” and salary = 80000 단일 애트리뷰트상의 인덱스를 사용해 질의를 처리하는 전략: 1. Finance 레코드를 찾기 위해 dept_name 상의 인덱스를 사용하고, salary = 인가를 테스트한다. 2. $80000 의 급여를 받는 강사를 찾기 위해 salary 상의 인덱스를 사용하고 dept_name = “Finance”인가를 테스트한다. 3. Finance 학과에 속한 모든 레코드를 가리키는 포인터를 찾기 위해 dept_name 인덱스를 사용한다. 이와 유사하게 salary 인덱스를 사용한다. 구한 양 포인터 집합의 공통 집합을 취한다.

44 다중 키 인덱스 복합 검색 키 (Composite search keys)는 하나 이상의 애트리뷰트를 포함하는 검색키를 말한다.
E.g. (dept_name, salary) 논리적 순서 : 다음 조건 중 하나를 만족시키면 (a1, a2) < (b1, b2) 이다 a1 < b1, or a1=b1 and a2 < b2

45 다중 애트리뷰트상의 인덱스 다음과 같은 결합 검색 키상의 인덱스를 가지고 있다 하자. (dept_name, salary).
다음과 같은 where 절의 질의 경우, where dept_name = “Finance” and salary = 80000 (dept_name, salary) 의 다중 애트리뷰트에 대한 인덱스를 사용하면 두 조건을 만족하는 레코드를 효율적으로 찾을 수 있다. 각각의 인덱스를 사용하는 것이 비효율적이다 – 조건중의 하나만을 만족하는 많은 레코드(또는 포인터)를 가져올 수 있다. 또한 다음과 같은 경우도 효율적으로 처리할 수 있다. where dept_name = “Finance” and salary < 80000 그러나 다음과 같은 경우 효율적으로 처리할 수 없다. where dept_name < “Finance” and balance = 80000 첫 번째 조건은 만족하지만 두 번째 조건은 만족하지 않는 많은 레코드를 가져 올 수 있다.

46 Hashing

47 정적 해슁 버켓 (bucket)은 하나 이상의 레코드를 내포하는 저장 단위이다 (일반적으로, 버켓은 디스크 블록이다).
해쉬 파일 구조(hash file organization )에서는 해쉬 함수를 사용해 검색 키 값으로부터 직접 레코드의 버켓을 얻는다. 해쉬 함수 h는 모든 검색 키 값 K의 집합으로부터 모든 버켓 주소 B의 집합으로 대응시키는 함수이다. 해쉬 함수는 삽입과 삭제 및 액세스를 위해 레코드를 찾는데 사용된다. 서로 다른 탐색 키 값을 가진 레코드들이 동일한 버켓에 대응할 수도 있다 ; 따라서, 레코드를 찾으려면 버켓 전체를 순차적으로 검색해야 한다.

48 해쉬 파일 구조의 예 키로서 dept_name 을 사용한 instructor 파일의 해쉬 파일 구조(다음 페이지의 그림 참조). 10개의 버켓이 있다. i번째 문자의 이진 표현은 정수 i로 가정한다. 해쉬 함수는 문자들의 이진 표현의 합을 10으로 나누어 남는 값을 돌려준다. E.g. h(Music) = h(History) = h(Physics) = 3 h(Elec. Eng.) = 3

49 해쉬 파일 구조의 예 dept_name 을 키로 사용한 instructor 파일의 해쉬파일구조

50 해쉬 함수 최악의 해쉬 함수는 모든 검색 키 값을 같은 버켓에 대응시킨다 ; 이것은 파일내 검색 키 값의 수에 비례한 액세스 시간이 걸리도록 한다. 이상적인 해쉬 함수는 균등 (uniform)하다. 즉, 각 버켓에는 모든 가능한 값의 집합으로부터 같은 수의 검색 키 값이 할당된다. 이상적인 해쉬 함수는 무작위(random)하다. 즉, 각 버케에는 파일내 검색 키 값의 실질적인 분포에는 관계없이 같은 수의 레코드가 할당된다. 전형적인 해쉬 함수는 검색 키의 내부 이진 표현에 계산을 수행한다. 예를 들어, 문자열의 검색 키에 대해 문자열 내의 모든 문자의 이진 표현을 합한 값을 버켓의 수로 나눈 나머지 값을 반환할 수 있다.

51 버켓 오버플로의 처리 버켓 오버플로는 다음과 같은 이유로 발생할 수 있다. 버켓이 불충분하다.
레코드의 분산이 치우친다(skewed). 치우침은 다음과 같은 두 가지 이유로 발생할 수 있다 : 여러 레코드가 같은 검색 키 값을 갖는다. 선택한 해쉬 함수가 키 값의 불균등 분포를 생성한다. 버켓 오버플로의 확률은 줄일 수는 있지만, 제거할 수는 없다 ; 이 때는 오버플로 버켓(overflow buckets)을 사용해 처리한다.

52 버켓 오버플로의 처리 (계속) 오버플로 체인 (Overflow chaining) – 주어진 버켓의 오버플로 버켓들이 연결 리스트로 함께 연결된다. 위와 같은 기법을 폐쇄 해슁(closed hashing)이라 한다. 개방 해슁(open hashing)이라는 대안이 있는데, 데이터베이스 어플리케이션에는 부적합하다.

53 해쉬 인덱스 해슁은 파일 구조에 뿐만 아니라, 인덱스 구조 생성에도 또한 사용될 수 있다.
해쉬 인덱스(hash index )는 해쉬 파일 구조 내에 관련 레코드 포인터와 함께 검색 키를 구성한다. 해쉬 인덱스는 항상 2차 인덱스이다 파일 자체가 해슁을 이용해 구성되면, 동일한 검색 키를 사용해 파일상의 별도의 주 해쉬 인덱스는 불필요하다. 그러나, 2차 인덱스 구조와 해쉬 구성 파일이라 하지 않고 해쉬 인덱스라는 용어를 사용한다.

54 해쉬 인덱스의 예 hash index on instructor, on attribute ID

55 정적 해슁의 결함 정적 해슁에서, 함수 h는 검색 키 값들을 고정된 버켓 주소의 B에 대응시킨다. 데이터베이스는 시간에 따라 커지거나 작아진다. 초기 버켓의 수가 너무 적거나, 데이터베이스가 커지면 오버플로가 많아지므로 성능이 저하될 것이다. 미래의 어떤 시점에서의 파일 크기를 예측하여 그에 따라 버켓의 수를 할당하면, 처음에 상당한 양의 공간이 낭비될 것이다 (대부분의 버켓이 차지 못한다). 데이터베이스가 축소하면, 또 다시 공간이 낭비될 것이다. 한가지 방법은 새로운 해쉬 함수로 파일을 주기적으로 재구성하는 것이다. 비용이 너무 많이 들고 정상 동작을 방해한다. 이러한 문제점은 버켓의 수가 동적으로 수정되도록 하는 기법을 사용해 해결할 수 있다.

56 동적 해슁 크기가 늘어나고 줄어드는 데이터베이스에 좋다. 해쉬 함수가 동적으로 수정되도록 한다.
확장 해슁 (Extendable hashing )– 동적 해슁의 한가지 유형 해쉬 함수는 큰 범위에 걸친 값들을 생성한다 – 일반적으로 b = 32인 b-비트의 정수 어떤 시점에서 버켓 주소의 테이블에 인덱스하기 위해 해쉬 함수의 접두부만을 사용한다. 접두부의 길이를 0  i  32인 i 비트라 하자 . 처음에 i = 0, 버켓 주소 테이블(Bucket address table size ) 사이즈 = 2i. 데이터베이스의 크기가 늘어나고 줄어듬에 따라 i의 값이 커지고 작아진다. 버켓 주소 테이블의 다수의 엔트리가 같은 버켓을 포인트할 수 있다. 따라서 버켓의 실제 수는 2i 보다 작다. 이것은 또한 버켓이 합쳐지고 분할함에 따라 동적으로 변한다.

57 이 구조에서, i2 = i3 = i,이다. 한편 i1 = i – 1 이다.
일반적인 확장 해쉬 구조 이 구조에서, i2 = i3 = i,이다. 한편 i1 = i – 1 이다. (자세한 사항은 다음 페이지를 참조)

58 확장 해쉬 구조의 이용 버켓 주소 테이블내 여러 엔트리들이 한 버켓을 가리킬 수 있다. 각 버켓 j는 값 i j를 저장한다.
검색 키 Kj를 내포한 버켓을 찾으려면 : 1. Compute h(K j) = X 2. X의 처음 상위 i 비트를 버켓 주소 테이블 내로의 변위로 사용해 포인터를 따라 적합한 버켓으로 간다. 검색 키 값 K j을 가진 레코드를 삽입하려면, j라는 버켓을 탐색하여 그 위치를 찾는 동일한 절차를 따른다. 버켓 j에 공간이 있으면, 그 버켓에 레코드를 삽입한다. 그렇지 않으면, 버켓을 분할하고 삽입을 재시도 해야 한다(다음 페이지를 참조하라). 어떤 경우에는 오버플로 버켓이 사용된다 (후에 설명)

59 확장 해쉬 구조에서의 삽입(계속) 검색 키 값 Kj 를 가진 레코드를 삽입할 때 버켓 j를 분할하려면 :
i > i j 이면 (버켓 j로 둘 이상의 포인터가 있는 경우) 새로운 버켓 z를 할당하고, i j와 i z 에 i j + 1을 설정한다. j를 가리키고 있는 버켓 주소 테이블 엔트리들의 다음 반이 z를 가리키도록 한다. 버켓 j내의 각 레코드를 제거하고 재삽입 한다. K j에 대한 새로운 버켓을 다시 계산하고, 버켓에 레코드를 삽입한다 (버켓이 여전히 차게 되면 분할이 더욱 요구된다). i = i j 이면 (버켓 j로 하나의 포인터만 있는 경우) i값이 임의의 제한 값 b에 이르거나, 해당 삽입 연산에 너무 많은 버켓 분할이 발생했다면, 오버플로 버켓을 생성한다. 그렇지 않으면 i를 증가 시키고 버켓 주소 테이블의 크기를 두 배로 한다. 테이블내 각 엔트리를 같은 버켓을 가리키는 두 개의 엔트리로 대치한다. K j에 대한 새로운 버켓 주소 테이블 엔트리를 다시 계산한다. 이제 i > i j의 조건이 만족되어, 위의 첫번째 경우를 사용한다.

60 확장 해쉬 구조에서의 삭제 임의 키 값을 삭제하기 위하여, 버켓 내 레코드를 검색하여 삭제한다.
금번 레코드 삭제로 해당 버켓이 비게되면 버켓도 삭제된다 (적절한 버켓 주소 테이블 갱신이 수반되어야 한다). 버켓 합병이 발생할 수 있다 (같은 ij 의 값과 같은 ij –1 의 접두어를 갖는 친구 (buddy)버켓이 존재하는 경우) 버켓 주소 테이블의 사이즈도 줄어들 수 있다. 주의: 버켓 주소 테이블의 사이즈 축소는 비용이 많이 드는 연산이다. 따라서 총 버켓 수가 버켓 주소 테이블 의 사이즈보다 훨씬 작은 경우에만 발생한다.

61 확장 해쉬 구조의 사용 : 예제

62 예제 (계속) 초기 해쉬 구조; bucket size = 2

63 예제 (계속) “Mozart”, “Srinivasan”, “Wu” 레코드를 삽입한 후의 해쉬 구조

64 예제 (계속) Einstein 레코드를 삽입한 후의 해쉬 구조

65 예제 (계속) “Gold”, “El Said” 레코드를 삽입한 후의 해쉬 구조

66 예제 (계속) Katz 레코드를 삽입한 후의 해쉬 구조

67 예제 (계속) 1 11개 레코드를 모두 삽입한 후의 구조

68 예제 (계속) 앞 페이지의 해쉬 구조에 Kim 레코드를 삽입한 후의 해쉬 구조

69 확장 해슁과 다른 구조 비교 확장 해슁의 장점: 파일 사이즈가 증가해도 해쉬 성능이 감소하지 않는다. 최소한의 공간 오버 헤드
확장 해슁의 단점: 해당 레코드 검색을 위하여 부가적인 포인터 추적이 필요하다. 버켓 주소 테이블이 매우 커질 수 있다 (메모리 사이즈보다 커짐) 디스크 상에 매우 큰 연속 디스크 공간을 할당할 수 없다. 해법: 버켓 주소 테이블 상의 해당 레코드 검색을 위하여 B+- 트리 구조를 사용할 수 있다. 버켓 주소 테이블 사이즈를 바꾸는 일은 비용이 많이 드는 연산이다. 다른 대안으로 선형 해슁 (linear hashing) 이 있다. 디렉토리의 점진적 증대를 허용한다 (버켓 주소 테이블과 유사함). 단, 버켓 오버 플로우를 더 많이 사용함.

70 순서 인덱싱과 해슁의 비교 고려할 사항 : 주기적인 재구성 비용 삽입과 삭제의 상대적인 빈도
최악의 경우의 액세스 시간의 비용으로 평균 액세스 시간을 최적화하는 것이 바람직한가? 예상되는 질의의 유형 특정한 키 값을 가진 레코드를 검색하는 데는 해슁이 일반적으로 유리하다. 범위 질의(range query)가 보통이면, 순서 인덱스를 사용하는 것이 유리하다. 실제로는: PostgreSQL 는 해쉬 인덱스 구조를 제공하지만 성능이 좋지 않아 사용하는 것을 권하지 않는다. Oracle은 정적 해쉬 파일 구조는 제공하지만 해쉬 인덱스 구조는 제공하지 않는다. SQLServer 는 오직 B+- 트리 구조만을 지원한다.

71 SQL에서의 인덱스 정의 인덱스의 생성 create index <인덱스명> on <릴레이션명>
(<애트리뷰트–리스트>) 예 : create index b-index on branch(branch_name) 검색 키가 후보 키라는 조건을 간접적으로 명시하고 시행하려면 create unique index를 사용한다. 인덱스를 제거하려면 drop index <인덱스명> 대부분의 데이터베이스 시스템은 사용되는 인덱스의 형태를 기술하는 방법을 제공한다 (B+-tree/Hashing). 또한 릴레이션의 인덱스 중 하나를 클러스터로 선언하는 것을 허용한다. 그러면 시스템은 클러스터 인덱스의 검색 키에 의하여 정렬된 릴레이션을 저장한다.

72 End of Chapter

73 Figure 11.01

74 Figure 11.15

75 Partitioned Hashing Hash values are split into segments that depend on each attribute of the search-key. (A1, A2, , An) for n attribute search-key Example: n = 2, for customer, search-key being (customer-street, customer-city) search-key value hash value (Main, Harrison) (Main, Brooklyn) (Park, Palo Alto) (Spring, Brooklyn) (Alma, Palo Alto) To answer equality query on single attribute, need to look up multiple buckets. Similar in effect to grid files.

76 Grid Files Structure used to speed the processing of general multiple search-key queries involving one or more comparison operators. The grid file has a single grid array and one linear scale for each search-key attribute. The grid array has number of dimensions equal to number of search-key attributes. Multiple cells of grid array can point to same bucket To find the bucket for a search-key value, locate the row and column of its cell using the linear scales and follow pointer

77 Example Grid File for account

78 Queries on a Grid File A grid file on two attributes A and B can handle queries of all following forms with reasonable efficiency (a1  A  a2) (b1  B  b2) (a1  A  a2  b1  B  b2),. E.g., to answer (a1  A  a2  b1  B  b2), use linear scales to find corresponding candidate grid array cells, and look up all the buckets pointed to from those cells.

79 Grid Files (Cont.) During insertion, if a bucket becomes full, new bucket can be created if more than one cell points to it. Idea similar to extendable hashing, but on multiple dimensions If only one cell points to it, either an overflow bucket must be created or the grid size must be increased Linear scales must be chosen to uniformly distribute records across cells. Otherwise there will be too many overflow buckets. Periodic re-organization to increase grid size will help. But reorganization can be very expensive. Space overhead of grid array can be high. R-trees (Chapter 23) are an alternative