Chapter 16 데이터베이스 파일 인덱싱 기법, B-트리 및 B+-트리 2018-12-07 Chapter 16 데이터베이스 파일 인덱싱 기법, B-트리 및 B+-트리 Copyright © 2004 Ramez Elmasri and Shamkant Navathe

Chapter Outline 단일-단계 순서 인덱스들의 유형 기본 인덱스 클러스터링 인덱스 보조 인덱스 다단계 인덱스 B-트리와 B+-트리를 이용한 동적 다단계 인덱스 다중키 인덱스

그림 15.7 NAME 필드를 순서키로 갖는 EMPLOYEE 레코드들로 구성된 순서 화일의 일부 목록

인덱스 - 접근 경로 단일 단계 인덱스는 데이터 화일내의 레코드를 효과적으로 찾도록 도와주는 보조 화일임 인덱스는 보통 화일내의 한 필드에 대해 정의된다 (여러 필드에 대해 정의될 수도 있음 인덱스는 <필드값, 레코드에 대한 주소>로 구성된 엔트리들을 저장한 화일이다. 인덱스는 화일에 대한 접근 경로(access path) 라고 불린다

인덱스 - 접근 경로 (계속) 인덱스 엔트리는 실제 레코드 크기보다 훨씬 작기 때문에, 인덱스 화일은 데이터 화일보다 훨씬 적은 디스크 블록을 차지한다. 인덱스에 대한 이진 탐색으로 데이터 화일의 해당 레코드에 대한 주소를 얻을 수 있다. 인덱스는 밀집 또는 희소 인덱스가 될 수 있다. 밀집 인덱스는 데이터 화일내의 모든 탐색 키 값 (즉, 모든 레코드)에 대한 인덱스 엔트리를 갖는다. 희소 (또는 비밀집) 인덱스는 탐색 값의 일부에 대해서만 인덱스 엔트리를 갖는다.

인덱스 - 접근 경로 (계속) 예: 주어진 데이터 화일: EMPLOYEE(NAME, SSN, ADDRESS, JOB, SAL, ... ) 데이터 화일에 대한 가정: 레코드 크기 R=150 바이트 블록 크기 B=512 바이트 레코드 개수 r=30000 레코드 얻을 수 있는 값: 블럭킹 인수 Bfr= B div R= 512 div 150= 3 레코드/블럭 화일의 블록 수 b= (r/Bfr)= (30000/3)= 10000 블럭 SSN 필드에 대한 인덱스에서, 필드 크기 VSSN=9 바이트 라고 가정하고, 레코드 포인터 크기 PR=7 바이트 라고 가정한다. 그러면: 인덱스 엔트리 크기 RI=(VSSN+ PR)=(9+7)=16 바이트 인덱스 블럭킹 인수 BfrI= B div RI= 512 div 16= 32 엔트리/블럭 인덱스 블록 수 b= (r/ BfrI)= (30000/32)= 938 블럭 이진 탐색시 접근할 블록 수 log2bI= log2938= 10 블록 이 비용은 다음의 평균 선형 탐색 비용보다 훨씬 적은 비용임: (b/2)= 30000/2= 15000 블록 접근 만약 화일의 레코드들이 정렬되어 있으면, 이에 대한 이진 탐색 비용은 다음과 같다: log2b= log230000= 15 블록 접근

단일 단계 인덱스의 유형 기본 인덱스 순서화일에 대해 정의할 수 있는 인덱스이다. 이 데이터 화일은 키 필드 순으로 정렬돼 있어야 한다. 데이터 화일의 각 블록에 대해 하나의 엔트리를 가지며, 블록 앵커라 불리는 각 블록의 첫 번째 레코드에 대한 키 필드 값을 엔트리로 갖는다. 각 블록의 마지막 레코드를 블록 앵커로 사용하는 방식을 이용할 수도 있다. 전체 탐색 값이 아니라 데이터 화일의 각 블록에 대해 하나의 엔트리 (즉, 블록의 앵커 레코드에 대한 키 값)을 가지므로, 기본 인덱스는 비밀집(희소) 인덱스이다.

그림 16.1 그림 15.7에 있는 화일의 순서키 필드에 대한 기본 인덱스

단일 단계 인덱스의 유형(계속) 클러스터링 인덱스 순서 화일에 대해 정의할 수 있다. 데이터 화일은 각 레코드에 대해 구별된 값을 갖지 않는 필드(즉, 키가 아닌 필드)에 따라 정렬된다. 해당 필드에 올 수 있는 각 값의 종류별(each distint value)로 하나의 인덱스 엔트리를 포함하며, 이 엔트리에는 그 필드 값을 가진 레코드들이 저장된 첫번째 블록에 대한 주소를 포함한다. 클러스터링 인덱스는 삽입과 삭제가 상대적으로 간단한 비밀집 인덱스의 한 예이다.

클러스터링 인덱스는 밀집 또는 비밀집 인덱스 교재 영어 원서 (p.615, ) 클러스터링 인덱스는 밀집 또는 비밀집 인덱스 교재 영어 원서 (p.615, ) A dense index has an index entry for every search key value (and hence every record) in the data file. A sparse (or nondense) index has index entries for only some of the search values. A sparse index has fewer entries than the number of recods in the file. Thus, a clustering index is another example of a nondense index because it has an entry for every distinct value of the indexing field, which is a nonkey.

위키피디아 A dense index in databases is a file with pairs of keys and pointers for every record in the data file. Every key in this file is associated with a particular pointer to a record in the sorted data file. In clustered indices with duplicate keys, the dense index points to the first record with that key.[3] A sparse index in databases is a file with pairs of keys and pointers for every block in the data file. Every key in this file is associated with a particular pointer to the block in the sorted data file. In clustered indices with duplicate keys, the sparse index points to the lowest search key in each block.

그림 16.2 EMPLOYEE 화일의 키가 아닌 필드 DEPTNUMBER에 대한 클러스터링 인덱스

그림 16.3 같은 클러스터링 필드값을 갖는 레코드들의 각 그룹을 위해 별도의 블록 클러스터를 가지는 클러스터링 인덱스

단일 단계 인덱스의 유형(계속) 보조 인덱스 보조 인덱스는 기본 접근 방법이 이미 존재하는 화일을 접근하는 보조 수단을 제공한다. 보조 인덱스는 후보 키나 모든 레코드에 대해 유일한 값을 갖는 필드 또는 중복된 값을 갖는 키가 아닌 필드에 대해 만들 수 있다. 보조 인덱스는 두 개의 필드로 구성된 순서 화일이다. 첫 번째 필드는 인덱스 필드인 데이터 화일의 비순서 필드와 같은 데이터 타입이다. 두 번째 필드는 블록 포인터이거나 레코드 포인터이다. 같은 화일에 여러 개의 보조 인덱스가 존재할 수 있다. 엔트리에는 레코드에 대한 보조키 값과 레코드가 저장되어 있는 블록 또는 레코드 자체에 대한 포인터가 있으므로, 키 필드에 대한 보조 인덱스는 밀집 인덱스이다.

그림 16.4 화일의 비순서 키 필드에 대한 밀집 보조 인덱스(블록 포인터를 갖는 경우)

그림 16.5 인덱스 엔트리들이 고정 길이이고 유일한 필드값들을 갖도록 하나의 간접 단계를 이용하여 구현된, 키가 아닌 필드에 대한 보조 인덱스(레코드 포인터를 갖는 경우)

표 16.2 인덱스 유형의 특징

다단계 인덱스 단일 단계 인덱스가 순서 화일이므로, 이 인덱스 자체에 대한 기본 인덱스를 만들 수 있다; 이 경우, 원래 인덱스 화일은 첫번째 단계 인덱스라 부르고 그 인덱스에 대한 인덱스는 두번째 단계 인덱스라 부른다. 위와 같은 과정을 반복하면 모든 엔트리를 한 블록에 저장할 수 있는 단계가 생기고, 이 단계의 블록을 최상위 단계라고 한다. 다단계 인덱스는 첫번째 단계 인덱스가 어떤 인덱스 유형(기본 인덱스, 클러스터링 인덱스, 보조 인덱스)이든지 사용할 수 있다.

그림 16.6 ISAM (Indexed Sequential Access Method) 조직과 유사한 2-단계 기본 인덱스

다단계 인덱스 이러한 다단계 인덱스는 탐색 트리 형태를 갖는다. 그러나 인덱스의 모든 단계가 순서 화일이므로, 새로운 인덱스 엔트리에 대한 삽입과 삭제가 매우 복잡하다는 문제점이 있다.

그림 16.8 서브트리에 대한 포인터를 갖는 탐색 트리의 한 노드

그림 16.9 차수가 p = 3인 탐색 트리

B-트리와 B+-트리를 사용한 동적 다단계 인덱스 이들 자료 구조들은 새로운 탐색 키의 삽입과 삭제를 효율적으로 처리할 수 있는 탐색 트리의 변형이다. B-트리와 B+-트리 자료 구조에서 각 노드는 하나의 디스크 블록을 할당하여 저장한다. 각 노드가 최소한 절반 이상 차 있도록 보장하여 저장 효율을 높일 수 있는 방식이다.

B-트리와 B+-트리를 사용한 동적 다단계 인덱스(계속) 완전히 차 있지 않는 노드에 삽입하는 것은 간단히 처리될 수 있다; 만약 노드가 차 있으면 삽입을 위해 두 노드로 분할한다. 노드 분할은 트리의 다른 단계로 파급될 수 있다. 삭제시 절반이상 차 있게 되는 노드에 대한 삭제는 간단히 처리될 수 있다. 삭제시 노드가 절반이하로 차게되면 이 노드를 이웃 노드들과 합병해야 한다.

B-트리와 B+-트리의 차이점 B-트리에서는 모든 단계의 노드들이 데이터 레코드들에 대한 포인터들을 갖는다.

그림 16.10 B-트리 구조 (a) q – 1개의 탐색값을 갖는 B-트리의 한 노드 (b) 차수 p = 3인 B-트리(삽입 순서는 8, 5, 1, 7, 3, 12, 9, 6이다.)

그림 16.11 B+-트리의 노드 (a) q – 1개의 탐색값을 갖는 내부 노드 (b) q – 1의 탑색값과 q – 1의 데이터 포인터를 가지는 B+-트리의 리프 노드

그림 16.12 p = 3이고 pleaf = 2인 B+-트리에 대한 삽입의 예

그림 16.13 B+-트리에서 삭제하는 예

다중키 인덱스 애트리뷰트들의 어떤 조합이 자주 사용되면 이런 애트리뷰트들의 조합에 의한 키 값을 이용하여 효율적인 접근을 제공할 수 있는 접근 구조를 구축하는 생성하는 것이 유용하다. 다중 속성에 대한 순서화된 인덱스 인덱스가 < A1, A2, …, An>의 애트리뷰트에서 생성되었다면 탐색키 값은 n개의 키값을 갖는 튜플(< V1, V2, ……, An>)이 된다. 튜플을 구성하는 각 키 값은 사전적(lexicographic) 순서를 갖는다. 분할 해싱 정적 외부 해싱의 확장된 형태이며, 동등 비교에만 적합하다. n개의 요소로 이루어진 키에 대해 해시 함수는 n개의 별도의 해시 주소를 갖는 결과를 생성한다. 버켓주소는 이런 주소들의 결합이다. 주소의 일부와 부합되는 적절한 버켓을 탐색하여 원하는 복합 탐색키를 찾을 수 있다. 애트리뷰트의 수를 쉽게 확장할 수 있다는 점과 각 애트리뷰트를 위한 어떤 별도의 접근 구조를 유지할 필요가 없다는 장점이 있다. 어떠한 구성 애트리뷰트에 대해서도 범위 질의를 할 수 없다는 단점이 있다.

다중키 인덱스(계속) 그리드 화일 EMPLOYEE 화일을 격자 화일로 구성 이 방법은 선형 눈금을 따라 여러 값의 그룹에 대응되는 셀들의 집합으로 사상되는 범위 질의에 특히 유용하다. 그리드 화일은 다중키 접근에 걸리는 시간을 줄일 수 있는 효율적인 방법이다. 그리드 화일은 그리드 배열 구조를 위해 많은 공간을 필요로 한다. 더욱이 동적 화일에서는 화일을 자주 재조직해야 하므로 유지보수 비용이 많이 증가한다.

다른 인덱스 유형 해시 인덱스 해싱을 기반으로 인덱스와 유사한 접근 구조를 만듬 인덱스 엔트리는 (키값, 레코드 포인터)로 구성됨 인덱스 엔트리에 대한 탐색은 해시 탐색 알고리즘 사용함

다른 인덱스 유형 (계속) 비트맵 인덱스 다중키에 대한 질의에 널리 사용함 많은 개수의 행을 가진 릴레이션을 위해 사용됨 보통 적은 수의 유일한 값들을 갖는 열들에 대해 만들어짐 한 열의 특정 값을 갖는 레코드들을 비트맵으로 표현함

다른 인덱스 유형 (계속) 함수 기반 인덱싱 어떤 필드 또는 필드 모임에 함수를 적용한 결과 값들이 인덱스의 키가 되는 인덱스

인덱스에 관한 일반적인 몇가지 이슈들 논리적 인덱스와 물리적 인덱스 물리적 인덱스 : 인덱스 엔트리들이 물리적 레코드 주소를 나타내는 물리적 포인터를 가짐. 엔트리 = <K, Pr> 논리적 인덱스 : 인덱스 엔트리들이 레코드 주소대신에 대응하는 레코드의 기본 파일 조직에 사용하는 필드의 값을 가짐. 엔트리 = <K, Kp>, Kp는 또 다른 레코드에 대한 키 값.