[데이터베이스 개론] 7. 인덱스 구조(Index Structures)

SELECT * FROM R이라는 쿼리를 실행 하기 위해서 어떻게 해야할까? 저장소의 모든 블럭을 검사해야한다면, 너무 비효율적이다. 일부 블록과 실린더를 따로 R을 위해 예약할 수도 있지만, 여전히 비효율적이다.

인덱스는 하나 이상의 필드 값을 받아서, 그 값을 가진 레코드를 빠르게 찾을 수 있게 해주는 자료구조다. 인덱스를 사용하면 전체 레코드 중 일부만 보고, 원하는 레코드를 모두 찾을 수 있다. 인덱스가 기반하는 필드를 검색 키(search key)라고 한다.

이 챕터에는 가장 흔한 형태의 인덱스를 다룬다. B-tree 이다. 또 다른 중요한 인덱스 구조인 2차 저장소의 해시 테이블도 다룬다. 마지막으로, 다차원의 데이터를 다루기 위해 디자인 된 인덱스 구조도 다룬다. 이 이덱스 구조들은 여러 값이나 범위의 속성들을 한 번에 다룬다.

14.1 Index-Structure Basics

앞으로 다룰 몇가지 개념을 소개한다. 저장소는 파일(file)로 구성된다. 운영체제의 파일과 비슷하다. 데이터 파일(data file)은 릴레이션을 저장하기 위해 사용된다. 데이터 파일은 하나 이상의 인덱스 파일(index files)을 가질 수 있다. 인덱스 파일은 검색 키의 값과 해당 값을 가진 데이터 파일의 레코드를 가리키는 포인터를 포함한다.

데이터 파일의 모든 레코드가 인덱스 파일에 항목이 존재하면 밀집하다(dense), 몇몇의 레코드만 항목으로 존재하면 희소하다(sparse)고 표현한다.

인덱스는 주/보조로도 나눈다. 주 인덱스는 레코드의 위치를 결정하지만, 보조는 그렇지 않다. 예를 들어, 1차 인덱스는 릴레이션의 주요 키(primary key)와 나머지 속성으로 2차 인덱스를 구성하는 것이 흔하다.

마지막으로, 우리는 역-인덱스(Inverted index)에 대해 소개한다. 역-인덱스는 문서속에서 특정 키워드가 있는지 검색을 도와준다. 웹에서 검색어에 응답하는 등의 사례에 필수적인 기능이다.

• 순차 파일(Sequential file): 릴레이션을 주요 키로 소팅하여 만든 파일. 튜플들은 블럭들안에 정렬되어 자리잡는다.
• 밀집 인덱스(Dense Index): 레코드의 키와 해당하는 레코드의 포인터를 담은 블럭들의 묶음이다. 보통 레코드를 저장하는 것보다, 키와 포인터가 훨씬 적은 저장공간을 차지하기 때문에, 데이터 파일보다 훨씬 적은 수의 블럭이면 충분하다. 그래서, 데이터 파일과 달리 메인 메모리에 올릴 수 있어서, 비싼 디스크 I/O 횟수를 줄일 수 있다. 키가 정렬되어 있다면, 이진 탐색(binary search)를 통해 탐색 시간도 줄일 수 있다.

밀집인덱스

• 희소 인덱스(Sparse Index): 보통 하나의 블럭당 하나의 키와 포인터 쌍만 갖는다. 밀집 인덱스보다 공간을 덜차지하지만, 더 많은 레코드 탐색 시간을 요구한다. 그리고 모든 레코드에 해당하는 인덱스가 있는 밀집 인덱스와 달리, 일부 레코드만 인덱스에 의해 참조되므로, 키로 sorting되는 것이 반드시 필요하다.

희소인덱스

• 멀티 레벨 인덱스(Multiple level index): 인덱스 위에 또 다른 인덱스를 두어 이진탐색 이상으로 두 빠른 탐색 속도를 만들 수도 있다. 그러나, 일반적으로 너무 많은 레벨의 인덱스를 두는 것보다는 B-tree 자료구조를 이용하는 것이 더 빠르다.

멀티 레벨 인덱스

• 보조 인덱스(Secondary Index): 주 인덱스(Primary Index)와의 차이는 데이터 파일 내에 레코드의 위치를 결정하지 않는다는 것. 멀티 레벨로 구현될수 있지만, 첫번째 레벨 인덱스는 반드시 밀집 인덱스여야함.

보조 인덱스

보조 인덱스는 언제 필요할까? Movie와 Studio가 다대일 관계라고 하자. Movie의 정보를 Movie들끼리 저장할수도 있지만, Movie가 제작된 Studio 정보와 연속되게 배치하면 더 효율적이다. 이렇게 배치된게 클러스터드 파일이다. 하지만 Studio 정보가 아닌, 다른 Movie 필드의 조건으로 검색하려고 하면 비효율적이다. 그래서 해당 속성에 대한 보조 인덱스가 필요하다.

같은 키값을 갖는 인덱스들이 여러번 저장되는 보조 인덱스는 공간 비효율적이다. 이것을 해결하는 버킷(bucket)이 있다. 버킷은 같은 인덱스 키값을 갖는 데이터 파일을 별도의 버킷 파일에 모아둔다. 인덱스는 이제 (키, 버킷위치) 만을 저장한다.

버킷은 문서 속 키워드를 검색하는데에도 사용된다. 아래 버킷파일에는 cat을 포함하는 문서들과 dog를 포함하는 문서들이 함께 모여있다.

버킷 파일 스스로가 레코드의 역할도 할 수 있다. 아래의 그림은 버킷 파일이 cat과 dog라는 키워드의 포함여부 뿐만 아니라 위치와 타입까지 저장하고 있다.

14.2 B-Trees

앞서 언급했듯이, 3개 이상의 너무 많은 멀티 레벨 인덱스보다는 B-Tree 자료 구조가 효율적이다. 그 중에서도 B+ Tree가 가장 보편적이다. B+ Tree는 인덱스되는 파일 크기에 맞게 인덱스 레벨을 조절하고, 사용되는 블럭들이 최소 절반이상 채워지도록 조절한다. 앞으로 얘기하는 B-Tree는 모두 B+ Tree에 관한 내용이다.

B-Tree는 3개의 계층(루트, 중간, 리프)로 구성되며, 모든 리프와 루트의 거리가 같은 균형잡힌 트리이다. 중간계층은 수에는 제한이 없다. 각 트리 인덱스는 n개의 검색 키와 n+1개의 포인터 저장공간으로 구성된다. 블럭의 크기에 따라 n을 최대한 크게 결정하는 것이 좋다.

리프노드의 포인터는 레코드를 가리킨다. 최소 (n+1)/2개(버림)의 포인터가 있어야 하며, 마지막 포인터는 예외적으로 다음 리프 노드를 기리킨다.

중간노드와 루트노드는 아래 계층의 블럭을 가리킨다. 중간 노드는 최소 (n+1)/2개(올림)의 포인터가 있어야 하지만, 루트 노드는 2개만 있어도 된다. 또, 중간노드와 루트노드는 갖고 있는 검색 키를 기준으로 크기를 비교하여 참조할 블럭을 정한다. 예를 들어, 23, 31, 43을 키로 갖는 중간 노드의 4개의 포인터는 각각 23미만, 23이상 31미만, 31이상 43미만, 43이상의 레코드가 있는 부분을 가리킨다.

B-tree는 다양하게 응용할 수 있다. B-tree 키를 레코드의 주요키로 쓸지말지/리프를 희소로할지 말집으로 할지/B-tree 키의 중복을 허용할지(이러면 null도 허용되어야 함) 등에 따라 데이터 파일의 정렬 여부도 다르다.