[DB] 인덱싱

데이터베이스 시스템 7판을 읽으며 간략하게나마 정리하는 글입니다.

 

예를 들어 학생 번호가 "22201"에 해당하는 tuple을 찾기 위해 전체 student 릴레이션을 조사하는 것은 비효율적이다.

이상적인 방법은 시스템이 직접 이 레코드를 찾는 것이다. 이런 형태의 접근을 제공하기 위해 파일과 관련된 부가적인 구조를 설계한다.

 

1. 기본 개념

데이터베이스 시스템의 인덱스는 도서관에서 사용되는 책의 인덱스와 똑같은 역할을 한다.

예를 들어 주어진 ID를 가진 student 레코드를 검색하기 위해 데이터베이스 시스템은 Index를 이용해 대응되는 레코드가 어느 디스크 블록에 있는지 찾은 후에, student 레코드를 얻기 위해 해당 block을 가져온다.

 

학생 ID를 정렬된 순서로 유지하여 student 릴레이션에 대한 인덱스를 구축하는 방식은 매우 큰 데이터베이스에서 적합하지 않다.

1) 인덱스 자체가 매우 커져버리고

2) 정렬된 순서로 인덱스를 유지하면 검색 시간을 줄일 수 있지만, 학생을 찾는 데 여전히 많은 시간이 걸리며

3) 학생이 데이터베이스에서 추출되거나 제거될 때, 정렬된 목록을 갱신하는 비용이 많이 발생하기 때문이다.

 

따라서 좀더 복잡한 인덱스 기술이 필요하며, 이에 대하여 학습해보자.

 

우선 인덱스는 기본적으로 2가지 종류가 있다.

→ 순서 인덱스(Ordered index): 값에 대해 정렬된 순서로 되어있다.

→ 해시 인덱스(Hash index): 버켓의 범위 안에서 값이 일정하게 분배로 되어 있다. 값이 할당되는 버켓은 해시 함수에 의해 결정된다.

 

각 인덱스들은 다음 요소들에 기초하여 평가된다.

 

1. 접근 유형(Access Type)

효율적으로 지원되는 접근 유형, 접근 유형은 특정한 속성의 값을 가진 레코드나, 특정한 범위에 들어가는 속성의 값을 가지는 레코드를 찾는 것을 포함한다.

 

2. 접근 시간(Access Time)

특정한 데이터 항목이나 항목의 집합을 찾는 데 걸리는 시간

 

3. 삽입 시간(Insertion Time)

새로운 데이터 항목을 삽입하는데 걸리는 시간.

이 시간은 새로운 값을 삽입하기 위한 위치를 찾는 시간과, 인덱스 구조를 갱신 하는 데 걸리는 시간을 포함한다.

 

4. 삭제 시간(Deletion Time)

데이터 항목을 삭제하는데 걸리는 시간.

이 시간은 값을 삭제하기 위해 위치를 찾는 시간과, 인덱스 구조를 갱신 하는 데 걸리는 시간을 포함한다.

 

5. 공간 부담(Space overhead)

인덱스 구조가 사용하는 부가적인 공간.

부가적인 공간이 넉넉하다면, 성능 향상을 위해 인덱스가 차지하는 공간을 늘리는 것은 일반적으로 합리적이다.

 

한 파일에서 레코드를 찾는데 사용되는 속성이나, 속성들의 집합을 검색 키(search key)라 한다.

여기서 키에 대한 정의는 primary key, candidate key, super key와 다르다.

 

또한 하나의 파일에 한 개 이상의 인덱스가 필요할 수 있으며, 이런 경우 검색 키 또한 여러 개일 수 있다.

 

2. 순서 인덱스

파일 안에 있는 레코드에 대한 임의 접근(random access)를 빨리 하기 위해서 인덱스 구조를 이용할 수 있다.

각 인덱스 구조는 특정한 검색 키와 관련이 있다.

 

책이나 도서관 목록 같은 인덱스처럼 순서 인덱스(ordered index)는 검색키의 값을 정렬된 순서로 저장하고, 검색 키와 검색 키를 포함하는 레코드를 연계시킨다.

 

인덱스 파일의 레코드도 특정 속성에 의해 정렬된 순서로 저장될 수 있다. 파일은 서로 다른 검색 키에 따라 몇몇 인덱스를 갖고 있다.

레코드를 포함하는 파일이 연속적인 순서로 저장되어야 하는 클러스터링 인덱스(clustering index)는 그 파일을 연속적인 순서로 정의한 속성을 검색키로 사용하는 인덱스다.

clustering index

 

클러스터링 인덱스는 또한 기본 인덱스(primary index)라고도 불린다.

클러스터링 인덱스의 검색 키는 보통 primary key인 경우가 많지만, 반드시 그런 것은 아닙니다!

 

파일의 연속적인 순서와 다른 순서로 구성되는 검색 키의 인덱스를 비클러스터링 인덱스(non-clustering index) 또는 보조 인덱스(secondary index)라고 부른다.

non-clustering index

 

다음은 검색 키에 대한 기본 인덱스(클러스터링 인덱스)를 가지는 인덱스 순차 파일(index-sequential file)입니다.

검색 키로 사용된 교수 ID에 대하여 순서대로 저장되어 있다.

이러한 구조는 DBMS에서 사용된 가장 오래된 인덱스 구조 중 하나라고 한다!

 

2 - 1) 밀집과 희소 인덱스

인덱스 레코드(index record) or 인덱스 엔트리(index entry)는 검색 키 값과 포인터로 구성되어 있는데, 이때 포인터는 이것을 검색 키값으로 가지는 한 개 이상의 레코드에 대한 포인터이다.

index record

레코드에 대한 포인터는 [디스크 블록의 식별자, 디스크 블록 안에서의 offset]으로 구성되어 있다.

 

일반적으로 사용하는 순서 인덱스는 2가지 유형이 있다.

 

2 - 1 - 1) 밀집 인덱스 (Dense index)

밀집 인덱스에서 인덱스 엔트리는 파일에 있는 모든 값은 모든 검색 키 값에 대해 나타난다.

 

밀집 클러스터링 인덱스에서 인덱스 레코드는 검색 키 값과, 그 검색 키 값의 첫 번째 데이터 레코드에 대한 포인터를 포함한다.

똑같은 검색 키 값을 가진 나머지 레코드는 첫번째 레코드 이후부터 연속적으로 저장되는데 이는 인덱스가 클러스터링 인덱스여서 이런 레코드는 동일한 검색 키로 정렬되면 순서대로 연속적으로 있기 때문이다.

 

(다음 그림에서 왼쪽이 인덱스 엔트리, 오른쪽이 순차 파일이다)

dense index

예를 들어 "22222"인 instructor 레코드를 찾는다고 해보자.

인덱스 엔트리에서 "22222"를 찾아 포인터를 통해 접근한다. ID가 primary key이기 때문에 희망하는 레코드는 반드시 존재한다.

 

밀집 비 클러스터링 인덱스에서 인덱스는 똑같은 검색 키를 가진 모든 레코드에 대한 포인터 목록을 저장해야 한다.

비클러스터링이라 순서대로 저장된것이 아니기 때문이다.

 

2 - 1 - 2) 희소 인덱스(Sparse index)

희소 인덱스에서 인덱스 엔트리는 검색 키 값에 대한 단지 몇 개만 나타낸다.

희소 인덱스는 오직 릴레이션이 검색 키로 정렬되어 저장될 때, 즉 클러스터링 인덱스인 경우에만 사용할 수 있다.

 

밀집 인덱스처럼 각 인덱스 엔트리는 [검색 키값, 검색 키값의 첫 번째 데이터 레코드에 대한 포인터]로 되어있다.

 

레코드를 찾기 위해서 찾고자 하는 검색 키 값보다 작거나 같은 것 중 가장 큰 검색키 값을 가지는 인덱스 엔트리를 찾아야 한다.

그리고 그 검색키 엔트리의 포인터 가리키는 레코드를 시작으로 원하는 레코드를 찾을 때까지 탐색한다.

sparse index

만약 15151을 키로 하는 레코드를 찾는다면, 우선 15151보다 작거나 같은 10101 키값을 인덱스 엔트리에서 찾은 후 해당 레코드로 이동한다.

이후 레코드 끝에 있는 포인터를 이용하여 다음 레코드를 확인하면 15151이 나올 때까지 반복한다.

---

다음은 검색 키가 dept_name인 밀집 클러스터링 인덱스이다.

ID 대신 dept_name으로 정렬되어 있다.

History학과 레코드를 찾는다고 하자. 위 그림의 인덱스를 사용하면, 첫 History 학과 레코드에 대한 포인터를 따라간다.

해당 레코드를 처리하고 나서 검색 키 순서로 다음 레코드에 있는 레코드의 포인터를 따라간다.

다른 학부의 레코드를 만나기 전까지 계속해서 레코드를 처리한다.

 

시스템 설계자는 접근 시간과 공간 부담 사이의 상반 관계를 고려해야 한다.

일반적으로 좋은 절충안은 블록당 하나의 인덱스 엔트리를 가지는 희소 인덱스를 가지는 방식이다.

왜냐하면 DB의 요구를 처리하는 비용 중 가장 큰 부분이 디스크에서 메인 메모리로 블록을 가져오는 데 걸리는 시간이다.

일단 블록을 가져왔다면, 전체 블록을 살피는 데 걸리는 시간은 대수롭지 않다.

 

희소 인덱스를 사용하면 찾고자 하는 레코드를 포함하는 블록을 가져올 수 있다.

 

2 - 2) 다계층 인덱스

1,000,000개의 튜플을 가진 릴레이션에 밀집 인덱스를 구축한다고 하자.

인덱스 엔트리가 데이터 레코드보다 더 작은 크기를 가지게 되므로 4KB 블록에 맞는 100개의 인덱스 엔트리를 가정하자.

따라서 해당 인덱스 하나당 10,000개의 블록을 할당한다.

 

인덱스가 메인 메모리에 유지될 만큼 충분히 작다면, 엔트리를 찾는 데 걸리는 검색 시간은 짧다.

하지만 전체 인덱스를 메모리에서 계속 유지할 수 없다면, 필요할 때마다 인덱스 블록을 디스크로부터 가져와야 한다.

그다음에 인덱스에서 엔트리를 찾기 위해 여러 개의 디스크 블록을 읽어야 한다.

 

이진 탐색은 인덱스 파일 내 엔트리의 위치를 찾기 위해 사용되지만, 여전히 비용이 많이 든다.

인덱스가 b개의 블록을 차지한다면, 이진 탐색은 log(b)만큼이나 많은 블록을 읽어야 한다.

만약 읽어야 할 블록이 인접 하게 있지 않다면, 각 블록을 읽어오는 I/O 연산이 필요하다.

 

위에서 말한 10,000개의 블록으로 구성된 인덱스의 경우, 이진 탐색은 14번의 블록 읽기가 필요하다.

한 블록당 10밀리초로 걸리는 디스크 시스템에서 검색하는데 140밀리 초가 걸린다.

이 시간은 크지 않아 보이지만, 1초에 오직 7개의 인덱스만 탐색할 수 있다.

크기가 큰 인덱스에 대한 검색은 비용이 많이 발생한다.

 

이러한 문제를 해결하기 위해, 인덱스를 다른 순차 파일처럼 취급해서 내부 인덱스라 불리는 원래의 기본 인덱스에 대한 희소 외부 인덱스를 구성한다. 다음 그림을 보자.

레코드의 위치를 찾기 위해 먼저 outer index에서 이진 탐색을 통해 원하는 레코드보다 작거나 같은 값 중 가장 큰 값을 갖는 레코드를 찾는다. 이때 포인터는 내부 인덱스 블록을 가리킨다.

이 포인터가 가리키는 블록을 스캔하여 원하는 레코드보다 작거나 같은 검색 키 값 중에서 가장 큰 값을 가지는 레코드를 찾을 수 있다.

이 레코드에는 찾고자 하는 레코드가 있는 파일의 블록을 가리키는 레코드가 있다.

 

이처럼 2개 이상의 단계를 가지는 인덱스를 다계층 인덱스(multilevel index)라 부른다.

 

2 - 3) 인덱스 갱신

모든 인덱스는 어떤 레코드가 파일에 삽입되거나, 삭제될 때마다 갱신되어야 한다.

더욱이, 파일 안에 레코드가 갱신된 경우에는 갱신에 영향을 받는 검색 키를 소유한 어떤 인덱스도 갱신되어야 한다.

(생략...)

 

2 - 4) 보조 인덱스

보조 인덱스는 무조건 밀집 인덱스이며, 모든 검색 키 값과 모든 레코드에 대한 포인터를 가지는 인덱스 엔트리이다.

 

클러스터링 인덱스는 연속적으로 접근하기 때문에 일부의 검색키만 저장하는 희소 인덱스가 가능하다.

연속적인 접근으로 파일의 일부분에서 키값을 가지는 레코드를 찾는 것이 항상 가능하기 때문이다.

 

하지만 보조 인덱스는 순차적으로 저장하지 않기 때문에 일부의 키만 저장해버리면, 해당 값을 찾기 위해 전체 파일을 탐색해야만 한다.

 

후보 키를 사용하는 보조 인덱스는 연속적인 값에 의해 가리켜지는 레코드가 연속적으로 저장되어 있지 않다는 것을 제외하고는 밀집 클러스터링 인덱스와 같다.

 

그러나 보조 인덱스는 클러스터링 인덱스와는 다른 구조를 가집니다.

 

클러스터링 인덱스의 검색 키가 후보 키가 아닌 경우, 그 인덱스가 검색 키에 있는 값을 가지는 첫 번째 레코드를 가리킨다면 충분합니다!

왜냐하면 다른 레코드는 파일의 순차 스캔을 통해 가져올 수 있기 때문입니다.

 

반대로 보조 인덱스의 검색 키가 후보키가 아닌 경우, 검색 키 값을 가지는 첫 번째 레코드를 가리키는 포인터로는 충분하지 않습니다.

똑같은 검색 키 값을 가지는 레코드가 파일의 여러 곳에 흩어져 있을 수 있기 때문이죠!

왜냐하면, 레코드는 보조 인덱스의 검색 키가 아닌 클러스터링 인덱스의 검색 키로 정렬되기 때문입니다.

따라서 보조 인덱스는 모든 레코드에 대한 포인터를 포함해야 한다.

 

릴레이션에서 동일한 검색 키 값을 가지는 레코드가 2개 이상 있다면, 이러한 검색 키 를 비고유 검색 키(nonunique search key)라고 한다.

 

비고유 검색키에 대한 보조 인덱스를 구현하는 방법은 다음과 같다.

기본 인덱스와는 다르게 보조 인덱스의 포인터는 레코드를 직접 가리켜서는 안 된다.

대신 인덱스에 있는 각각의 포인터는 우리가 찾고자 하는 파일의 포인터가 담겨있는 버켓을 가리켜야 한다. 다음 그림을 보자!

하지만 이 방식에는 몇 가지 단점이 있다.

 

1) 임의 I/O 작업이 필요한 간접 참조로 인해 인덱스 접근 시간이 더 오래 걸린다.

2) 키에 중복이 거의 없거나, 전혀 없는 경우, 전체 블록이 해당 버켓에 할당되어 많은 공간이 낭비될 수 있다.

 

클러스터링 인덱스에서 순차 탐색은 효율적이다. 파일에 있는 레코드가 물리적으로도 순서대로 저장되어 있기 때문이다.

하지만 클러스터링 인덱스의 검색 키 와 보조 인덱스 검색 키 둘다를 고려하여 순서대로 정렬할 수는 없다.

 

보조 인덱스는 기본 인덱스의 검색 키가 아닌 다른 키를 사용하면 쿼리 문의 성능이 향상된다.

하지만 이것은 데이터베이스 변경에 상당한 부담이 된다. DB 설계자는 검색만을 위한 질의와 데이터 변경의 상대적인 빈도에 대한 평가에 기초하여 바람직한 보조 인덱스를 결정해야 한다.

 

3. B+ - Tree 인덱스 파일

인덱스 순차 파일의 단점은, 파일이 커질수록 인덱스를 찾아서 그 데이터를 연속으로 스캔하는 성능이 감소하는 것이다.

 

B+ - Tree 인덱스 구조는 데이터의 삽입과 삭제에도 불구하고 성능을 유지하는 몇몇 인덱스 구조 중 가장 널리 사용된다.

B+ - Tree 인덱스 트리의 Root에서 단말 노드까지 모든 경로의 길이가 같은 균형 트리(balanced tree)형태 이다.

 

B+ - Tree 구조는 삽입과 삭제 시 성능 부담과 공간 부담을 준다는 것을 알게 될 것이다.

이 성능 부담은 파일의 변경이 많은 경우에 파일 재구성 비용을 피할 수 있으므로 나름 합리적이다.

게다가 노드가 반 정도 비어있으므로, 약간 낭비되는 공간이 있게 되는데 이런 공간 부담 역시 B+ - Tree 구조의 성능 이익을 고려하면 받아들일 수 있다.

 

3 - 1) B+ - Tree의 구조

우선 중복 검색 키값이 없다고 가정하자. 즉 우리는 각각의 검색 키는 고유하다 가정하고, 비고유 검색키는 나중에 다룬다.

 

다음 그림은 B+ - Tree의 대표적인 노드를 보여준다.

이는 n-1개의 검색 키 값 K1, K2,... , Kn-1과 n개의 포인터 P1, P2,... , Pn을 포함한다.

노드 안의 검색 키 값은 정렬된 순서로 유지된다. 그래서 i < j 이면 Ki < Kj이다.

 

먼저 단말 노드(leaf node)의 구조를 생각해보자. i = 1, 2,... , n-1일 때 포인터 Pi는 검색 키 값 Ki를 가지는 파일 레코드를 가리킨다.

다음 그림을 살펴보자. 검색키는 name이다.

B+ - Tree 인덱스의 단말 노드(n = 4)

 

이번에는 특정한 노드에 검색 키 값을 할당하는 방법에 대하여 생각해보자.

각 단말 노드는 n-1개 까지의 값을 가질 수 있는데, 단말 노드는 적어도 (N-1)/2 개의 값을 포함해야 한다.

위 그림에서 n=4 이기 때문에 각 단말 노드는 적어도 두 개, 많아도 세 개의 값을 가진다.

 

Li와 Lj가 단말 노드이고, i < j 이면(즉 트리에서 Li는 Lj의 왼쪽에 있음), Li에 있는 모든 검색 키값은 Lj에 있는 모든 검색 키 값보다 작다.

만약 B+ - Tree 인덱스가 밀집 인덱스로 사용된다면, 단말 노드에 모든 검색 키값이 나타나야 한다.

 

포인터 Pn에 대하여 알아보자.

각 단말 노드는 검색 키 값을 기초로 선형 순서로 되어 있다. 그래서 단말 노드를 검색 키 순서로 연결하기 위해서 Pn을 사용한다.

이는 파일의 연속 처리를 효율적으로 해준다.

 

B+ - Tree 비 말단 노드, 내부 노드(nonleaf node, internal node)는 단말 노드상에서 다계층 (희소) 인덱스를 형성한다.

비 단말 노드의 구조는 모든 포인터가 트리의 노드를 가리키고 있다는 것을 제외하면, 단말 노드의 구조와 동일하다.

비단말 노드는 n개까지의 포인터를 가질 수 있고, 적어도 n/2 개의 포인터를 갖고 있어야 한다.

한 노드의 포인터 수를 그 노드의 팬아웃(fanout)이라 부른다.

 

m개의 포인터를 가지고 있는 노드를 생각해보자. i = 2, 3,..., m-1 일 때 포인터 Pi는 Ki 보다는 작고 Ki-1 보다는 크거나 같은 검색 키 값을 포함하는 서브 트리를 가리킨다.

 

Root 노드는 다른 내부 노드와는 달리 n/2개보다 더 적은 포인터를 가질 수 있다.

그러나 하나의 노드로 구성된 트리가 아닌 경우 루트 노드는 적어도 2개의 포인터를 가지고 있어야만 한다.

 

다음 그림은 n=4인 B+ - Tree 구조의 instructor 파일을 보여준다.

 

다음 그림은 n=6인 B+ - Tree이다. n=4인 경우보다 트리의 높이가 작은 것을 알 수 있다.

B+ - Tree는 모두 균형 트리이다. 즉 루트에서 단말 노드까지의 모든 경로의 길이가 동일하다.

이러한 속성은 B+ - Tree가 되기 위한 요구 사항이다. 실제로 B+ - Tree에서 "B"는 "balanced"를 나타낸다.

이러한 균형적인 속성은 검색, 삽입, 삭제의 성능을 좋게 한다.

 

대부분의 데이터베이스 구현에서 검색키는 다음과 같이 고유하게 만든다.

릴레이션 r의 검색 키 속성 ai가 고유하지 않다고 가정하자. 또한 Ap가 릴레이션 r의 주 키라고 가정하자.

그러면 인덱스 구출 시 ai 대신 고유한 복합 검색 키 (ai, Ap)가 사용된다.

 

예를 들어 instructor 릴레이션에서 속성 name에 대하여 인덱스를 생성하고자 한다면, ID가 교수의 주 키에 해당하므로 복합 검색 키 (name, ID)에 대하여 인덱스를 생성한다. 

name에 대한 인덱스 조회는 이 인덱스를 사용하여 효율족으로 처리할 수 있다.

 

3 - 2) B+ - Tree에서 Query

질의를 처리하는 방법에 대하여 생각해보자.

 

검색 키값 v를 가지는 모든 레코드를 찾기를 원한다고 해보자. 다음 코드는 이러한 작업을 수행하는 find(v) 함수의 의사 코드이다.

직관적으로 이 함수는 Tree의 Root에서부터 시작해서 트리 안에 존재하는 특정 값을 포함하는 단말 노드에 도착할 때까지 아래 방향으로 탐색한다.

 

특히 Root 노드를 현재 노드로 시작하게 되면 함수는 단말 노드에 도달할 때까지 다음과 같은 단계를 반복한다.

 

1) 현재 노드를 조사하여 v값보다 큰 검색 키 Ki를 만족하는 가장 작은 i값을 찾는다

2) i가 발견되었다면

    2 - 1) Ki와 v가 같다면, Pi+1이 현재 노드를 가리킨다.

    2 - 2) Ki > v 이면, Pi가 현재 노드를 가리킨다.

3) 만약 i를 발견하지 못한 경우

    3 - 1) 명백하게 v > Km-i이며 이때 Pm은 노드에서 Null이 아닌 마지막 포인터가 된다. 이 경우 Pm이 현재 노드를 가리킨다.

 

검색 키 값이 Ki = v인 단말 노드의 경우 포인터 Pi가 검색 키 값이 Ki에 해당하는 레코드를 직접 가리키고 있다.

 

B+ - Tree는 또한 특정 범위의 검색 키값을 가지는 모든 레코드를 찾기 위해서 사용될 수 있다. 이를 range query라고 부른다.

이러한 질의를 처리하기 위해 프로시저 findRange(lb, ub)를 생성할 수 있다.

 

▶ B+ - Tree 인덱스에 대한 질의 비용

질의를 처리할 때 Root에서 일부 단말 노드까지 트리의 경로를 탐색해야 한다.

파일에 레코드 N개가 있다면 그 경로는 다음보다 더 길지 않다.

보통 디스크 블록의 크기는 4KB이다. 검색 키의 크기가 12바이트이고 디스크 포인터의 크기가 8바이트 라면 n은 약 200이 된다.

검색 키의 크기를 32바이트로 하면 n은 약 100이 된다.

n이 100이고, 파일에 백만 개의 검색 키 값이 있다면 검색하는 데 단지 log 50 (1,000,000) = 4 개의 노드가 접근된다.

그래서 검색하기 위해 기껏해야 4개의 블록만 디스크로부터 읽어 오면 된다.

 

트리의 Root노드는 보통 많이 접근되기 때문에 버퍼에 있을 확률이 매우 높다.

이 말은 즉, 실제로는 3개 or 더 적은 블록이 디스크로부터 읽힌다.

 

일반 이진트리와 B+ -Tree 구조의 가장 큰 차이점은 노드의 크기로부터 인한 트리의 높이다.

이진트리는 기껏해야 노드당 2개의 포인터를 갖지만, B+ - Tree는 각 노드가 크고, 많은 수의 포인터를 가질 수 있기 때문이다.

 

이렇게 단말 노드로 이동한 후, 고유한 검색 키의 단일 값에 대한 일치하는 레코드를 가져오기 위해 한번 이상의 I/O가 필요하다.

 

이번에는 비고유 키의 경우에 대하여 생각해보자.

앞에서 설명했듯, 후보 키가 아니어서 중복이 발생할 수 있는 속성에 인덱스를 생성하는 경우, 중복이 없는 복합 키를 만들어 인덱스를 생성하게 된다.

복합 키는 고유성을 보장하기 위해 주키와 같은 추가 속성을 ai에 추가하여 생성한다. ai에 인덱스를 생성하는 대신 복합키 (ai, Ap)에 인덱스를 생성했다고 가정하자.

 

중요한 질문은 위 인덱스를 사용하여 ai에 대해 주어진 값 v를 갖는 모든 튜플을 어떻게 검색하는지 이다.

이 질문에 대한 대답은 findRange(lb, ub)를 사용하는 것이다. 여기서 lb = (v, -∞), ub = (v, ∞)이다.

 

3 - 3) B+ - Tree 갱신

레코드가 릴레이션에 삽입되거나 삭제될 때 릴레이션에 대한 인덱스 역시 갱신되어야 한다.

레코드에 대한 갱신은 이전 레코드의 삭제에 뒤이어 새로운 레코드의 삽입으로 모델링 된다. 따라서 오직 삽입과 삭제만 고려된다.

 

삽입, 삭제는 검색보다 훨씬 복잡하다.

왜냐하면 삽입 결과로 노드가 너무 크게 되어서 노드를 분할(split) 해야 하거나, 너무 작아서 노드를 유착(coalesce) 해야 할지도 모르기 때문이다.

또한 하나의 노드가 분할되거나, 한쌍으로 결합되었을 때 균형이 보존되어야 한다.

 

▶ 삽입

find()의 검색 때와 똑같은 기술로 검색 키 값이 어느 단말 노드에 있는지를 찾는다.

그 이후에 단말 노드에 엔트리를 삽입하면서 검색 키가 여전히 순서를 유지하도록 조정한다.

 

▶ 삭제

검색 때와 똑같이 삭제될 레코드를 검색 키로 조사하고, 삭제될 엔트리를 포함하는 단말 노드를 찾는다.

만약 같은 검색 키 값을 가지는 다중 엔트리가 존재한다면, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 같은 검색 키 값을 가지는 모든 엔트리를 검색한다. 그리고 제거한다.

 

자세한 삽입, 삭제 과정은 너무 복잡해져서 생략하도록 하겠습니다... 이거 까지 정리하다간 머리 터진다구요!!! 아으!!!

 

3 - 4) B+ - Tree 갱신의 복잡도

B+ - Tree 상에서 삽입과 삭제 연산이 복잡할지라도 상대적으로 적은 디스크 I/O 연산을 요구합니다.

이는 I/O 연산이 매우 비용이 높으니, 상당한 이득입니다.

 

삽입에서 일어날 수 있는 최악의 경우에 필요한 I/O 연산의 수는 log n/2 (N)에 비례합니다. 이때 n은 한 노드 안에 있는 포인터의 최대 개수이고, N은 인덱스 된 파일에 있는 레코드의 개수입니다.

 

삭제 또한 최악의 경우 검색 키에 대해 중복 값이 없다면, 마찬가지로 log n/2 (N)에 비례합니다.

즉, I/O 연산의 관점에서 삽입과 삭제 연산의 비용은 B+ - Tree의 높이에 비례하므로 작습니다.

실제로 B+ - Tree에서 연산의 최악의 경우보다 작은 I/O 연산을 일으킵니다.

 

비록 B+ - Tree가 적어도 반 정도 노드가 채워지는 것을 보장할지라도 엔트리가 무작위 순서로 삽입된다면 노드는 평균적으로 2/3 이상 채워질 수 있다. 한편 엔트리가 정렬 순서로 삽입된다면, 노드는 정확하게 반만 채워진다.

 

4. 다중 키 접근

지금 까지는 릴레이션의 쿼리를 처리하기 위해 단지 하나의 인덱스만 사용해왔습니다!

하지만 몇몇 쿼리에서는 다중 인덱스 or 다중 속성 검색 키에 대한 인덱스를 사용하는 것이 더 편리합니다.

 

4 - 1) 다중 단일 키 인덱스 사용

instructor 파일은 각각 dept_name, salary에 대해 2개의 인덱스를 갖고 있다고 해보자.

다음 쿼리를 생각해보자. "재무학과에서 급여(salary)가 $80,000인 모든 교수를 찾아라." 다음과 같이 작성하자!

이를 처리하는 3가지 방법이 있다.

 

1) Finance 학과에 속하는 모든 레코드를 찾기 위해 dept_name 인덱스를 이용한다. 이때 인덱스로 찾은 레코드의 salary가 80000인지 조사한다.

 

2) 급여가 80000인 교수에 속하는 모든 레코드를 찾기 위해 salary 인덱스를 이용한다. 이때 인덱스로 찾은 레코드의 dept_namedl "Finance"인지 조사한다.

 

3) Finance 학과에 속하는 모든 레코드에 대한 포인터를 찾기 위해 dept_name 인덱스를 사용한다.

또 급여가 80,000인 교수에 속하는 모든 레코드에 대한 포인터를 찾기 위해 salary 인덱스를 사용한다.

이 두 포인터 집합의 교집합을 취한다. 교집합에 속하는 포인터는 재무학과에서 급여(salary)가 $80,000인 모든 교수에 속하는 레코드를 가리킨다.

 

3번째 방식은 유일하게 다중 인덱스를 사용하는 방식이다. 하지만 3번을 사용할 가능성은 희박하다.

3번은 Finance 학과에 속하는 레코드가 많거나, 급여가 80000인 교수가 많거나, 둘다에 속하는 교수가 많지 않다면 사용하기에 적합하지 않다.

 

즉, 적은 결과를 찾기 위해 너무 많은 수의 포인터를 탐색해야 하는 점이 부담이다.

 

4 - 2) 다중 키 인덱스

이런 경우 복합 검색 키 (dept_name, salary)를 검색 키로 사용하여 인덱스를 생성한다.

 

이런 경우 다음 쿼리를 효율적으로 처리하기 위해 B+ - Tree 인덱스를 사용하게 된다.

 

다음과 같이 검색 키의 첫 번째 속성(dept_name)에 대한 동등 조건과 두 번째 속성(salary)에 대한 범위 지정으로 이루어진 질의 역시 범위 검색에 대응 대기 때문에 효율적으로 처리된다.

 

검색 키(dept_name, salary)에 대한 순서 인덱스를 사용하면 한 가지 속성에 대한 동등 조건만 있는 쿼리도 효율적으로 처리된다.

 

하지만 복합 검색 키에 대한 순서 인덱스 구조를 사용하면 약간의 단점이 있다.

다음 질의를 살펴보자.

위 쿼리는 검색키(dept_name, salary)를 가지는 순서 인덱스를 사용해서 대답할 수 있다.

즉, 알파벳순으로 "Finance"보다 작은 dept_name의 각 값에 대해 시스템은 salary 값이 80,000인 레코드를 위치시킨다.

그러나 각 레코드는 다른 디스크 블록에 있을 수도 있고, 파일에 있는 레코드 순서 때문에 I/O 연산을 많이 할 수도 있다.

 

바로 직전의 쿼리와 가장 큰 차이점은 dept_name에 대한 조건이 동등 조건이 아니라, 비교 조건이라는 점이다.

이러한 조건은 검색 키에 대한 범위 질의에 대응되지 않는다.

 

4 - 3) 커버링 인덱스

커버링 인덱스(covering index)는 레코드에 대한 포인터와 함께 일부 속성의 값이 저장된 인덱스이다.

별도의 속성 값을 보조 인덱스에 포함하 면 어떤 질의에 대해서는 실제 레코드를 살펴보지도 않고 인덱스만을 통해 값을 얻을 수 있다.

 

예를 들어 instructor 릴레이션의 ID 속성에 대해 non-clustering 인덱스가 구축되어 있다고 하자.

만약 레코드 포인터와 함께 salary 속성의 값이 저장되어 있다면, instructor 레코드에 접근하지 않고도 급여만 필요한 질의에 대해 응답할 수 있다.

 

이러한 커버링 인덱스는 검색 키의 크기를 줄여 주어 내부 노드의 팬아웃을 크게 해 주고, 잠재적으로 높이를 줄여준다.