Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 제 11장 인덱싱과 해슁 기본 개념 순서 인덱스 B+ - 트리 인덱스 파일 B - 트리 인덱스 파일 정적 해슁 동적 해슁 순서 인덱싱과 해슁의 비교 SQL에서의 인덱스 정의 다중 키 액세스 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 기본 개념 원하는 데이터를 액세스하는데 속도를 증가 시키기 위해 사용하 는 인덱싱 기법 – 예를 들어, 도서관에서의 저자 목록 검색 키 - 파일내의 레코드를 탐색하는데 사용되는 애트리뷰트 또는 애트리뷰트의 집합 인덱스 파일은 다음과 같은 형식의 레코드(인덱스 엔트리라 한다) 로 구성된다. 인덱스 파일은 일반적으로 원래의 파일보다는 훨씬 작다. 두 가지 기본 인덱스의 종류 : – 순서 인덱스 : 검색 키가 정렬된 순서로 저장된다. – 해쉬 인덱스 : 검색 키가 해쉬 함수를 사용해 버켓들에 균 등하게 분산된다. 검색 키 포인터 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 인덱스 평가 기법 다음을 근거로 하여 평가되는 인덱싱 기법 효율적으로 지원되는 액세스 유형. 예를 들어, – 애트리뷰트에 특정 값을 가진 레코드들 – 또는 특정 범위의 값에 속하는 애트리뷰트 값을 가진 레코드들 액세스 시간 삽입 시간 삭제 시간 공간 비용 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 순서 인덱스 순서 인덱스에서는 인덱스 엔트리가 검색 키 값의 정렬된 순서에 따라 저장된다. 예를 들어, 도서관에서의 저자 목록 주 인덱스 : 순차적으로 정렬된 파일에서는 검색 키 인덱스가 파일의 순차적인 순서를 지정한다. - 또한 밀집 인덱스라 하기도 한다. - 주 인덱스의 검색 키는 일반적으로 그렇지만 반드시 주 키일 필 요는 없다. 2차 인덱스 : 검색 키 인덱스가 파일의 순차적인 순서와는 다른 순 서를 지정한다. 또한 비군집 인덱스라 하기도 한다. 인덱스 순차 파일 : 주 인덱스로 정렬된 순차 파일 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 밀집 인덱스 파일 밀집 인덱스 - 인덱스 레코드가 파일내의 각 검색 키 값 에 대해 나타난다. Brighton Downtown Mianus Perryridge Redwood Round Hill Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 700 Round Hill A-305 350 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 희소 인덱스 파일 몇 개의 검색 키 값에 대한 인덱스 레코드 검색 키 값 K를 가진 레코드를 찾으려면 다음과 같이 한다. - K보다 작은 것 중에서 가장 큰 검색 키 값을 가진 인덱스 레코드를 찾는다. - 인덱스 레코드가 가리키는 레코드에서 시작하여 순차적으로 파일을 검색한다. 공간이 적게 소요되고 삽입과 삭제를 위한 유지 비용이 덜 든다. 레코드를 찾는데는 일반적으로 밀집 인덱스보다 느리다. 좋은 손익 비교 : 블록에서 가장 작은 검색 키 값에 대응하는 파일 내 각 블록마다 하나의 인덱스 엔트리를 가진 희 소 인덱스 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 희소 인덱스 파일의 예 Brighton Mianus Redwood Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 700 Round Hill A-305 350 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 다단계 인덱스 주 인덱스가 메모리에 들어 가지 않으면, 액세스하는데 비용이 많이 든다. 인덱스 레코드에의 디스크 액세스 횟수를 줄이려면, 디스크에 저장된 주 인덱스를 순차 파일로 취급하여 그에 대해 희소 인덱스를 구축한다. - 외부 인덱스 – 주 인덱스의 희소 인덱스 - 내부 인덱스 – 주 인덱스 파일 외부 인덱스 조차 너무 커서 메인 메모리에 들어가지 않는다면, 또 다른 인덱스 계층이 생성 될 수 있다. 모든 계층이 인덱스는 파일에 삽입 또는 삭제시 갱신되어야 한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 다단계 인덱스 (계속) • 인덱스 블록 0 블록 1 데이터 외부 인덱스 내부 인덱스 데이터 블록 1 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

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

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

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 2차 인덱스 흔히, 어떤 필드(주 인덱스의 검색 키가 아닌)의 값이 어떤 조건을 만족하는 모든 레코드를 찾고자 할 때가 있다. - 예1 : 계좌 번호순으로 저장된 account 데이터베이스에 특정 지점 의 모든 계좌를 찾고자 할 수도 있다. - 예2 : 위와 같은 데이터베이스에서 특정 잔고 또는 범위 잔고를 가진 모든 계좌를 찾고자 할 수도 있다. 각 검색 키 값에 대해 하나의 인덱스 레코드를 가진 2차 인덱스를 가질 수 있다 ; 인덱스 레코드는 특정 검색 키 값을 가진 실제 레코드에 대한 포인터를 내포하는 버켓을 가리킨다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Account의 balance 필드에 대한 2차 인덱스 350 400 500 600 700 750 900 Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 700 Round Hill A-305 350 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 주 인덱스와 2차 인덱스 2차 인덱스는 밀집 인덱스이어야 한다. 인덱스는 레코드를 검색할 때 실질적인 이점을 제공한다. 파일 수정시 파일상의 각 인덱스가 갱신되어야 한다.인덱스 갱신은 데이터베이스 수정에 추가 비용을 부과한다. 주 인덱스를 이용한 순차 검색은 효율적이지만, 2차 인덱스를 이용한 순차 검색은 비용이 많이 든다 (각 레코드 액세스는 디스크로부터 새로운 블록을 가져 올 수 있다.) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

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

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

B+ - 트리 노드 구조 전형적인 노드 - Ki는 검색 키 값이다. P1 K1 P2 … P n-1 K n-1 P n - Pi는 잎이 아닌 노드에 대해서는 자식 노드로의 포인 터이거나 잎 노드에 대해서는 레코드 또는 레코드의 버켓으로의 포인터이다. 노드내의 검색 키는 다음과 같은 순서이다. K1 < K2 < K3 < … < K n-1 P1 K1 P2 … P n-1 K n-1 P n Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리 내의 잎 노드 잎 노드의 속성 : i = 1, 2, …, n-1에 대해, 포인터 P i는 검색 키 값 K i를 가진 파일 레코드 또는 각 레코드가 검색 키 값 K i를 가진 파일 레코드들의 포인터 버켓을 가리킨다. 검색 키가 주 키를 형성하지 않으면, 버켓 구조만이 필요하다. L i와 L j가 잎 노드이고 i < j이면, L i의 검색 키 값은 L j의 검색 키 값보다 작다. P n은 검색 키 순으로 다음 잎 노드를 가리킨다. Brighton Downtown Brighton A-212 750 Downtown A-101 500 Downtown A-110 600 • account 파일 leaf node Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리 내의 잎이 아닌 노드 잎이 아닌 노드는 잎 노드에 대해 다단계 희소 인덱스를 이룬다. m개의 포인터를 가진 잎이 아닌 노드에 대해 : - P1이 가리키는 부 트리내의 모든 검색 키는 K1보다 작다. - 2  i  n-1에 대해, Pi가 가리키는 부 트리내의 모든 검색 키는 K i-1보다 크거나 같고 K i보다 작은 값을 갖는다. - P m이 가리키는 부 트리내의 모든 검색 키는 K m-1보다 크거나 같다. P1 K1 P2 … P n-1 K n-1 P n Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

B+ - 트리의 예제 account 파일에 대한 B+ - 트리 (n = 3) Perryridge Mianus Redwood Brighton Downtown Redwood Round Hill account 파일에 대한 B+ - 트리 (n = 3) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

B+ - 트리의 예제 (계속) 잎 노드는 2 ~ 4개의 값을 가져야 한다(n = 5이므로 (5-1)/2 ~ 5-1). 뿌리 이외의 잎이 아닌 노드는 3 ~ 5개의 자식을 가져야 한다 (n = 5이므로 5/2 ~ 5). 뿌리는 적어도 2개의 자식을 가져야 한다. Perryridge Brighton Downtown Mianus Perryridge Redwood Round Hill account 파일에 대한 B+ - 트리 (n = 5) Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에 관한 유의 사항 내부 노드 연결은 포인터로 이루어지므로, B+ - 트리에서는 논리적으로 근접한 블록이 물리적으로 근접한다는 가정은 없다. B+ - 트리의 잎이 아닌 계층은 희소 인덱스 계층을 이룬다. B+ - 트리에는 비교적 적은 수의 계층을 내포(파일 크기의 로그) 하므로, 검색이 효율적으로 수행된다. 파일에의 삽입과 삭제는 인덱스가 로그 시간 내에 재구성될 수 있으므로 효율적으로 처리될 수 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에의 질의 검색 키 값이 k인 모든 레코드를 찾아라. - 뿌리 노드에서 시작한다. * k보다 큰 것 중에서 가장 작은 검색 키 값의 노드를 찾는다. * 그러한 값이 존재하면, 그것을 K i라 하자. 그리고 P i를 따라 자 식 노드를 찾는다. * 그렇지 않고 k  K m-1 이면, 노드에 m개의 포인터가 있다. P m을 따라 자식 포인터를 찾는다. - 위의 포인터를 따라 도달한 노드가 잎 노드가 아니면, 그 노드에 서 위의 절차를 반복하고 해당 포인터를 따른다. - 결국 잎 노드에 도달한다. 키 K i = k 이면, 포인터 P i를 따라 원하 는 레코드 또는 버켓을 찾는다. 그렇지 않으면 검색 키 k 값을 가 진 레코드가 존재하지 않는 것이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에의 질의 (계속) 질의 처리에서 뿌리로부터 어떤 잎 노드까지 트리내의 경로가 탐색 된다. 파일내에 K개의 검색 키 값이 있으면, 경로는 log n/2(K) 보다는 길지 않다. 노드는 일반적으로 디스크 블록과 같은 크기인 4KB이며, n은 100정도이다(인덱스 엔트리당 40 바이트). 100만개의 검색 키 값이 있고 n = 100인 경우, 기껏해야 log50(1,000,000) = 4 개의 노드가 탐색에서 액세스 된다. 이것을 100만개의 검색 키 값을 가진 균형 이진 트리와 비교해 보라 – 대략 20개의 노드가 탐색에서 액세스 된다. - 각 노드의 액세스에는 대략 30ms가 걸리는 디스크 입출력이 필요 하게 되므로, 위와 같은 차이는 중요하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에의 갱신 : 삽입 검색 키가 나타날 잎 노드를 찾는다. 검색 키 값이 잎 노드에 이미 존재하면, 레코드가 파일에 추가되고 필요한 포인터가 버켓에 삽입된다. 검색 키 값이 없으면, 레코드를 주 파일에 추가하고 필요하면 버켓을 생성한다. 그리고 : - 잎 노드에 공간이 있으면, 적당한 위치의 잎 노드에 (검색 키 값, 레코드/버켓 포인터) 쌍을 삽입한다. - 잎 노드에 공간이 없으면, 노드를 분할하고 다음 장에 서 설명하는 대로 (검색 키 값, 레코드/버켓 포인터) 쌍을 삽입한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에의 갱신 : 삽입 (계속) 노드의 분할 : - n개의 (검색 키 값, 포인터) 쌍을 정렬된 순으로 취한다 (삽입 되 는 것 포함). 처음 n/2 개를 원래의 노드에 넣고, 나머지를 새로 운 노드에 넣는다. - 새로운 노드를 p라 하고, k를 p내의 가장 작은 키 값이라 하자. (k, p)를 분할되고 있는 노드의 부모에 삽입한다. 부모가 꽉 차면, 그것을 분할하고 위로 계속 분할해 나간다. 노드의 분할은 꽉 차지 않은 노드가 발견될 때 까지 위로 진행한다. 최악의 경우에는 트리의 높이를 하나 더 증가 시키면서 뿌리 노드가 분할될 수도 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

B+ - 트리에의 갱신 : 삽입 (계속) “Clearview” 삽입 전과 후의 B+ - 트리 Perryridge Mianus Redwood Brighton Downtown Redwood Round Hill Perryridge Downtown Mianus Redwood Brighton Clearview Redwood Round Hill Mianus Downtown “Clearview” 삽입 전과 후의 B+ - 트리 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리에의 갱신 : 삭제 삭제할 레코드를 찾아 주 파일과 버켓(있으면)에서 그것을 제거한다. 버켓이 없거나 버켓이 비게 되면, 잎 노드에서 (검색 키 값, 포인터)를 제거한다. 삭제로 인해 노드가 너무 적은 엔트리를 가지게 되고, 그 노드와 형제 노드의 엔트리들이 하나의 노드에 들어가게 되면, - 두 노드의 모든 검색 키 값들을 하나의 노드(왼쪽에 있는 것)에 삽입 하고, 다른 노드를 삭제한다. - 위의 절차를 반복적으로 그의 부모로부터 P i가 삭제될 노드의 포인 터인 쌍 (K i-1, P i)를 삭제한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

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

B+ - 트리 삭제의 예 “Downtown”을 내포한 잎 노드의 제거로 그의 부모 노드가 너무 적은 포인터를 가지게 되는 결과를 내지는 않았다. 그래서 연쇄 삭제는 삭제된 잎 노드의 부모에서 중단되었다. Perryridge Mianus Redwood Brighton Clearview Redwood Round Hill account에서 “Downtown”을 삭제한 후의 결과 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

B+ - 트리 삭제의 예 (계속) 삭제된 “Perryridge” 노드의 부모가 너무 작게 되지만, 그의 형제 노드에 하나의 포인터를 더 가질 공간이 없으므로 재분배가 수행된다. 그 결과 뿌리 노드의 검색 키 값이 변경됨을 주목하라. Perryridge Downtown Redwood Brighton Clearview Redwood Round Hill Mianus “Downtown” 대신 “Perryridge”의 삭제 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B+ - 트리 파일 구조 인덱스 파일 성능 저하 문제는 B+ - 트리 인덱스를 사용해 해결한다. 데이터 파일 성능 저하 문제를 B+ - 트리 파일 구조를 사용해 해결한다. B+ - 트리 파일 구조내의 잎 노드에는 포인터 대신 레코드를 저장한다. 레코드는 포인터보다 크기 때문에, 잎 노드에 저장될 수 있는 레코드의 최대 수는 잎이 아닌 노드내 포인터의 수보다 적다. 잎 노드에는 여전히 반 이상이 차야 한다. 삽입과 삭제는 B+ - 트리 인덱스 엔트리의 삽입 및 삭제와 같은 방법으로 처리된다. 레코드는 포인터보다 많은 공간을 사용하므로, 공간 활용도가 중요하다. 공간 활용도를 증가 시키려면, 분할 및 합병을 하는 동안 재분배에서 더 많은 형제 노드를 내포한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 B - 트리 인덱스 파일 B+ - 트리와 유사하지만, B - 트리는 검색 키 값이 단 한번만 나타나도록 하여 검색 키의 중복 저장을 제거한다. 잎이 아닌 노드내 검색 키는 B - 트리내 어디에도 나타나지 않는다 ; 잎이 아닌 노드내 각 검색 키에 대해 추가의 포인터가 내포되어야 한다. 일반적인 B - 트리 잎 노드의 구조 잎이 아닌 노드 - 포인터 B i는 버켓 또는 파일 레코드 포인터이다. P1 K1 P2 … P n-1 K n-1 P n P1 B1 K1 P2 B2 K2 … P m-1 B m-1 K m-1 P m Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

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

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

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

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 파일 구조의 예 Brighton A-217 750 Round Hill A-305 350 Redwood A-222 700 버켓 0 버켓 1 버켓 2 버켓 3 버켓 4 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Mianus A-215 700 Downtown A-102 400 Downtown A-110 6900 버켓 5 버켓 6 버켓 7 버켓 8 버켓 9 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 파일 구조의 예 (계속) 키로서 branch-name을 사용한 account 파일 의 해쉬 파일 구조(앞 장의 그림 참조). 10개의 버켓이 있다. i번째 문자의 이진 표현은 정수 i로 가정한다. 해쉬 함수는 문자들의 이진 표현의 합을 10으로 나누어 남는 값을 돌려준다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 버켓 오버플로의 처리 버켓 오버플로는 다음과 같은 이유로 발생할 수 있다. - 버켓이 불충분하다. - 레코드의 분산이 치우친다. 치우침은 다음과 같은 두 가지 이유 로 발생할 수 있다 : * 여러 레코드가 같은 검색 키 값을 갖는다. * 선택한 해쉬 함수가 키 값의 불균등 분포를 생성한다. 버켓 오버플로의 확률은 줄일 수는 있지만, 제거할 수는 없다 ; 이 때는 오버플로 버켓을 사용해 처리한다. 오버플로 체인 – 주어진 버켓의 오버플로 버켓들이 연결 리스트로 함께 연결된다. 위와 같은 기법을 폐쇄 해슁이라 한다. 개방 해슁이라는 대안이 있는데, 데이터베이스 어플리케이션에는 부적합하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 인덱스 해슁은 파일 구조에 뿐만 아니라, 인덱스 구조 생성에도 또한 사용될 수 있다. 해쉬 인덱스는 해쉬 파일 구조내에 관련 레코드 포인터와 함께 검색 키를 구성한다. 해쉬 인덱스는 항상 2차 인덱스이다 - 파일 자체가 해슁을 이용해 구성되면, 동일한 검색 키를 사용해 파일상의 별도의 주 해쉬 인덱스는 불필요하다. 그러나, 2차 인덱스 구조와 해쉬 구성 파일이라 하지 않고 해쉬 인덱스라는 용어를 사용한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 해쉬 인덱스의 예 버켓 0 버켓 1 버켓 2 버켓 3 버켓 4 버켓 5 버켓 6 A-215 A-305 A-101 A-110 A-217 A-102 A-218 A-222 A-201 Brighton A-217 750 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 Redwood A-222 700 Round Hill A-305 350 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

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

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 동적 해슁 크기가 늘어나고 줄어드는 데이터베이스에 좋다. 해쉬 함수가 동적으로 수정되도록 한다. 확장 해슁 – 동적 해슁의 한가지 유형 - 해쉬 함수는 큰 범위에 걸친 값들을 생성한다 – 일반적으로 b = 32인 b-비트의 정수 - 어떤 시점에서 버켓 주소의 테이블에 인덱스하기 위해 해쉬 함 수의 접두부만을 사용한다. 접두부의 길이를 0  i  32인 i 비트 라 하자 . - 처음에 i = 0 - 데이터베이스의 크기가 늘어나고 줄어듬에 따라 i의 값이 커지 고 작아진다. - 버켓의 실제 수는 2i보다 작으며, 이것은 또한 버켓이 합쳐지고 분할함에 따라 동적으로 변한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 일반적인 확장 해쉬 구조 이 구조에서 i1 = i - 1이고 i2 = i3 = i 해쉬 접두부 i i1 i2 i3 • • 00 • • 01 • • 10 • • 11 버켓 1 버켓 2 버켓 3 • 버켓 주소 테이블 • Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 확장 해쉬 구조의 이용 버켓 주소 테이블내 여러 엔트리들이 한 버켓을 가리킬 수 있다. 각 버켓 j는 값 i j를 저장한다 ; 동일한 버켓을 가리키는 모든 엔트리들은 처음 i j 비트상에 같은 값을 가진다. 검색 키 Kj를 내포한 버켓을 찾으려면 : 1. Compute h(K j) = X 2. X의 처음 상위 i 비트를 버켓 주소 테이블 내로의 변위로 사용해 포인터를 따라 적합한 버켓으로 간다. 검색 키 값 K j을 가진 레코드를 삽입하려면, j라는 버켓을 탐색하고 찾는 동일한 절차를 따른다. 버켓 j에 공간이 있으면, 그 버켓에 레코드를 삽입한다. 그렇지 않으면, 버켓을 분할하고 삽입을 재시도 해야 한다(다음 장을 참조하라). Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 확장 해쉬 구조에서의 갱신 검색 키 값 K l을 가진 레코드를 삽입할 때 버켓 j를 분할하려면 : i > i j 이면 (버켓 j로 둘 이상의 포인터가 있는 경우) - 새로운 버켓 z를 할당하고, i j와 i z를 이전의 i j + 1에 설정한다. - j를 가리키고 있는 버켓 주소 테이블 엔트리들의 다음 반이 z를 가리키도록 한다. - 버켓 j내의 각 레코드를 제거하고 재삽입 한다. - K l에 대한 새로운 버켓을 다시 계산하고, 버켓에 레코드를 삽입 한다(버켓이 여전히 차게 되면 분할이 더욱 요구된다). i = i j 이면 (버켓 j로 하나의 포인터만 있는 경우) - i를 증가 시키고 버켓 주소 테이블의 크기를 두 배로 한다. - 테이블내 각 엔트리를 같은 버켓을 가리키는 두 개의 엔트리로 대치한다. - K l에 대한 새로운 버켓 주소 테이블 엔트리를 다시 계산한다. 이 제 i > i j가 되어, 위의 첫번째 경우를 사용한다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 확장 해쉬 구조에서의 갱신 (계속) 값을 삽입할 때, 여러 번의 분할 후에도 버켓이 차면 (즉, i가 b에 어느정도 도달하면), 버켓 엔트리 테이블을 더욱 분할하는 대신 오버플로 버켓을 생성한다. 키 값을 삭제하려면 해당 버켓을 찾아 제거한다. 버켓이 비게 되면 버켓 자체가 제거될 수 있다 (버켓 주소 테이블에 적절한 갱신을 하고). 버켓의 합침과 버켓 주소 테이블 크기의 감소가 또한 가능하다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 확장 해쉬 구조의 사용 : 예제 branch-name h( branch-name) Brighton 0010 1101 1111 1011 0010 1100 0011 0000 Downtown 1010 0011 1010 0000 1100 0110 1001 1111 Mianus 1100 0111 1110 1101 1011 1111 0011 1010 Perryridge 1111 0001 0010 0100 1001 0011 0110 1101 Redwood 0011 0101 1010 0110 1100 1001 1110 1011 Round Hill 1101 1000 0011 1111 1001 1100 0000 0001 해쉬 접두부 버켓 1 버켓 주소 테이블 초기 해쉬 구조, 버켓 크기 = 2 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 예제 (계속) 해쉬 접두부 2 Brighton A-217 750 1 Downtown A-101 500 Downtown A-110 600 Mianus A-215 700 3 버켓 주소 테이블 4개 삽입후의 해쉬 구조 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 예제 (계속) 해쉬 접두부 Brighton A-217 750 Redwood A-222 700 1 Downtown A-101 500 Downtown A-110 600 2 Mianus A-215 700 Round Hill A-305 350 3 Perryridge A-102 400 Perryridge A-201 900 Perryridge A-218 700 버켓 주소 테이블 모든 삽입후의 해쉬 구조 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 순서 인덱싱과 해슁의 비교 고려할 사항 : 주기적인 재구성 비용 삽입과 삭제의 상대적인 빈도 최악의 경우의 액세스 시간의 비용으로 평균 액세스 시간을 최적화하는 것이 바람직한가? 예상되는 질의의 유형 - 특정한 키 값을 가진 레코드를 검색하는 데는 해슁이 일반적으로 더 낫다. - 범위 질의가 보통이면, 순서 인덱스를 사용하는 것이 더 낫다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

SQL에서의 인덱스 정의 인덱스의 생성 create index <인덱스명> on <릴레이션명> (<애트리뷰트–리스트>) 예 : 검색 키가 후보 키라는 조건을 간접적으로 명시하고 시행하려면 create unique index를 사용한다. 인덱스를 제거하려면 create index b-index on branch( branch-name) drop index <인덱스명> Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 다중 키 액세스 특정 유형의 질의에 여러 인덱스를 사용한다. 예제 : 단일 애트리뷰트상의 인덱스를 사용해 질의를 처리하는 가능한 전략 : 1. Perryridge 레코드를 찾기 위해 branch-name 상의 인덱스를 사용 하고, balance = 1000 인가를 테스트한다. 2. 1000불의 잔고를 가진 계좌를 찾기 위해 balance 상의 인덱스를 사용하고 branch-name = “Perryridge” 인가를 테스트한다. 3. Perryridge 지점에 속한 모든 레코드를 가리키는 포인터를 찾기 위해 branch-name 인덱스를 사용한다. 이와 유사하게 balance 인 덱스를 사용한다. 구한 양 포인터 집합의 공통 집합을 취한다. select account-number from account where branch-name = “Perryridge” and balance = 1000 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

다중 애트리뷰트상의 인덱스 다음과 같은 결합 검색 키상의 인덱스를 가지고 있다 하자. 다음과 같은 where 절을 가지면 각각의 인덱스를 사용하는 것이 비효율적이다 – 조건중의 하나만을 만족하는 많은 레코드(또는 포인터)를 가져올 수 있다. 또한 다음과 같은 경우 효율적으로 처리할 수 있다. 그러나 다음과 같은 경우 효율적으로 처리할 수 없다. 첫 번째는 만족하지만 두 번째는 만족하지 않는 많은 레코드를 가져 올 수 있다. where branch-name = “Perryridge”and balance = 1000 where branch-name = “Perryridge”and balance < 1000 where branch-name <“Perryridge” and balance = 1000 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 격자 파일 하나 이상의 비교 연산자를 내포한 일반적인 다중 검색 키 질의의 처리 속도를 높이는데 사용되는 구조 격자 파일은 하나의 격자 배열과 각 검색 키 애트리뷰트에 하나의 선형 축척을 가진다. 격자 배열은 검색 키 애트리뷰트 수와 같은 차원을 가진다. 격자 배열의 여러 셀이 동일 버켓을 가리킬 수 있다. 검색 키 값에 대한 버켓을 찾으려면, 선형 축척을 사용해 셀의 열과 행을 찾아 포인터를 따른다. 버켓이 가득차면, 두 개 이상의 셀이 가리키는 새로운 버켓이 생성될 수 있다. 하나의 셀만이 가리킨다면, 오버플로 버켓이 생성될 필요가 있다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 account에 대한 예제 격자 파일 4 3 2 1 0 1 2 3 4 5 6 Bi Bj Townsend Perryridge Mianus Central 4 3 2 1 branch-name에 대한 선형 축척 격자 배열 버켓들 1K 2K 5K 10K 50K 100K 1 2 3 4 5 6 balance에 대한 선형 축척 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 격자 파일 (계속) 두 개의 애트리뷰트 A와 B에 대한 격자 파일은 (a1  A  a2  b1  B  b2)와 (a1  A  a2), (b1  B  b2)형의 질의를 굉장히 효율적으로 처리할 수 있다. 예를 들어, (a1  A  a2  b1  B  b2)에 응답하려면, 후보 격자 배열 셀을 찾기 위해 선형 축척들을 사용하고 그들 셀에서 가리키는 모든 버켓을 탐색한다. 선형 축척은 레코드들을 셀에 균등하게 분포하도록 선택해야 한다. 그렇지 않으면, 너무 많은 오버플로 버켓이 생길 것이다. 주기적인 재구성이 도움을 주겠지만, 재구성은 매우 비용이 많이 들 수 있다. 격자 배열의 공간 비용이 클 수 있다. R - 트리(21장)가 대안이다. Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수

Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수 분할 해슁 해쉬 값들은 다음과 같은 검색 키의 각 애트리뷰트에 의존하는 세그먼트로 분할된다. n개의 애트리뷰트 검색 키에 대한 (A1, A2, …, An) 예 : customer에 대해, n = 2인 검색 키가 (customer-street, customer-city)인 경우 한 애트리뷰트의 동등 질의에 응답하려면, 여러 버켓을 탐색할 필요가 있다. 격자 파일의 효과와 유사하다. 검색 키 값 해쉬 값 (Main, Harrison) 101 111 (Main, Brooklyn) 101 001 (Park, Palo Alto) 010 010 (Spring, Brooklyn) 001 001 (Alma, Palo Alto) 110 010 Copyrightⓒ 1999 서울산업대학교 전자계산학과 석상기 교수