물리적 데이터베이스

1. 개요

- 다량의 데이터를 담고 있는 DB는 물론 주기억장치(메인 메모리)에만 저장돼있는 게 아니라 평소에는 보조기억장치(디스크 등)에 저장돼 있다가(물리적 데이터베이스) 필요할 때 DBMS에 의해 메모리로 불려져 사용되고 또 그 내용이 삽입/삭제/수정된다. 물론 보조기억장치에 데이터를 읽고 쓰는 시간은 주기억장치에 올라와 있는 데이터를 읽고 쓰는 데 비해 굉장한 시간이 소모되므로, 어떻게 하면 보다 효율적인 속도로 읽기와 쓰기를 수행할 것인지가 중요한 문제가 되며 DB의 설계 과정에 있어서도 이는 중요하게 고려할 요소가 된다.

- 보조기억장치와 주기억장치 사이 입출력 시간차를 해소하기 위한 OS의 수단으로서 버퍼가 있다. OS는 주기억장치 내 공간에 버퍼 공간을 할당하여, 보조기억장치로부터 데이터를 읽어올 때마다 버퍼 공간에 이를 저장해 두었다가 가까운 시간 내에 이를 다시 불러올 필요가 있을 때 보조기억장치까지 접근하지 않고 버퍼 공간으로부터 데이터를 불러와 신속하게 입/출력을 수행한다. 그러나 OS의 버퍼 공간에서 흔히 사용하는 LRU 같은 알고리즘은 일반적으로 DB의 입출력에는 우수한 성능을 보이지 않는 것으로 알려져 있다.

- 여러 OS에서는 파일과 디스크를 각각 ‘블록’과 ‘섹터’라는 균일한 크기의 최소단위로 분할하여 한 섹터에 한 블록을 담는 방식으로 데이터를 저장하며, DBMS가 관리하는 DB의 내용을 담은 파일 또한 대개 이처럼 블록 단위로 분할되어 디스크의 여러 섹터에 나뉘어 저장된다.

- 블록 하나에는 여러 릴레이션이 저장될 수도 있고, 한 릴레이션이 여러 블록에 나뉘어 저장될 수도 있다. 릴레이션을 구성하는 튜플 한 단위, 애트리뷰트 한 단위를 파일 시스템 관점에서 볼 때는 보통 레코드, 필드로 칭하며, 필드와 레코드가 저장장치 내에서 차지하는 물리적인 크기는 각각 동일할 수도 있고(고정길이) 가변적일 수도 있다(가변길이).

- 꼭 한 블록 안에 레코드가 가득 저장돼야 하는 것은 아니며, DBMS에서 채워지는 비율(fill factor)을 다르게 정할 수 있다. 레코드와 레코드 사이에 레코드를 추가하는 경우에 만약 기존 블록에 레코드가 가득 차 있다면 새로 레코드를 추가함으로써 새로운 블록을 추가하고 그곳으로 대량의 레코드를 이동시키는 등의 작업을 수행해야 하고 이로 인해 디스크 입출력에 상당한 시간이 소모될 수 있다. fill factor를 100%보다 적은 비율로 지정해 두면, 이후 레코드를 삽입하는 경우에 그러한 긴 입출력 시간을 쓰지 않고 빠른 시간 내에 삽입을 완료할 수 있다.

2. 파일 내 레코드의 저장 방식

• heap file: 새로 레코드가 삽입될 때마다 무조건 파일의 맨 끝에 추가하는 방식. 삽입은 굉장히 빠른 시간 내에 끝마칠 수 있지만, 레코드와 레코드 사이에 어떠한 논리적 연결구조가 전혀 없기 때문에 파일에서 특정 레코드를 찾아 이를 반환하거나 삭제하거나 수정할 땐 항상 순차탐색을 해야 한다. 삽입을 하는 경우 외에는 모두 비효율적이다. 항상 전체 레코드가 참조되는 특성을 지닌 릴레이션의 경우에는 이러한 단점이 크게 드러나지 않는다.

• sequential file: 릴레이션에서 하나 이상의 필드를 기준으로 그것이 정렬된 순서대로 레코드의 순서를 유지하는 방식. 이때 기준이 되는 필드를 탐색키(search key)라 한다. 이 방식은 새 레코드를 삽입/수정한 후에도 순서가 유지돼야 하기 때문에 이러한 처리에 상당한 시간이 소요될 수 있으나, 탐색키의 값을 기준으로 레코드의 정보를 찾는 속도는 매우 빠르다. 다만 탐색키가 아닌 필드를 기준으로 레코드를 찾을 때에는 heap file과 마찬가지 성능을 보인다.

3. 인덱스

1) 개요

- 릴레이션의 각 레코드의 디스크 내 위치 정보만 모아놓은 데이터셋을 특정 필드의 값을 기준으로 정렬해 두면 그 필드를 기준으로 레코드 정보를 가져오고자 할 때 매우 빠른 속도로 가져올 수 있다. 이처럼 레코드들의 디스크 내 위치 정보를 정렬해둔 것을 인덱스(index)라 하며, 인덱스를 구성하는 각각의 위치 정보를 엔트리(entry)라 한다.

• 인덱스는 전체 DB 정보를 담은 파일보다 크기가 훨씬 작으면서 DB에서 데이터를 탐색하는 성능을 매우 크게 개선한다. (특히 찾고자 하는 레코드의 수가 전체의 2-4% 정도로 적은 경우에 조건절을 적절히 사용하면 성능이 매우 크게 개선된다는 사실이 알려져 있다.)

  • 다만 릴레이션이 아주 크다면 인덱스의 크기도 그만큼 커질 수 있다. 또, 레코드의 삽입/수정/삭제 시 인덱스에도 관련 변경사항을 반영해야 하므로 이러한 연산으로 인한 속도 저하가 있을 수 있다.

• 한 릴레이션에 대해 서로 다른 필드를 기준으로 하는 인덱스를 여럿 두어서 각 필드를 기준으로 레코드를 찾는 성능을 크게 개선할 수 있다.

2) 여러 인덱스의 특성

• 클러스터 인덱스(clustered index)와 비클러스터 인덱스(non-clustered index): (릴레이션이 파일에 sequential file 방식으로 저장돼 있어) 레코드들이 인덱스가 가리키는 필드를 기준으로 정렬돼 있는 인덱스를 클러스터 인덱스, 반대로 레코드들의 정렬 순서와 관련 없는 필드에 관한 인덱스를 비클러스터 인덱스라 한다. 클러스터 인덱스는 그 탐색키의 범위를 기준으로 레코드를 가져오는 쿼리를 매우 효과적으로 수행할 수 있게 한다.

• 희소 인덱스(sparse index)와 밀집 인덱스(dense index): 엔트리 수가 레코드 수보다 훨씬 적은 인덱스를 희소 인덱스, 엔트리 수와 레코드 수가 일치하는 인덱스를 밀집 인덱스라 한다.

  • 릴레이션이 sequential file 방식으로 저장돼 있는 경우 그 탐색키에 관한 인덱스는 모든 레코드에 대한 주소값을 가질 필요가 없으므로 보통 희소 인덱스이다.

  • 희소 인덱스는 DB에서 데이터를 탐색하는 성능이 밀집 인덱스보다도 대부분 뛰어나지만, 예를 들어 필드의 값만을 기준으로 하는 연산처럼 굳이 디스크 내 각 레코드 위치까지 참조해야 할 필요가 없는 함수 등(COUNT 등)에 대해서는 밀집 인덱스가 더 나은 성능을 보인다.

• 기본 인덱스(primary index): 레코드가 sequential file 방식으로 저장돼 있을 때 탐색키가 그 릴레이션의 기본키인 인덱스로, 릴레이션마다 최대 하나씩 있다. 보통 DBMS가 릴레이션을 생성할 때는 그 릴레이션의 기본키를 탐색키로 하는 sequential file 방식으로 생성한다. 기본 인덱스는 보통 희소 인덱스다.

• 보조 인덱스(secondary index): 기본 인덱스가 있는 릴레이션에서 기본키가 아닌 필드에 대한 인덱스. 보조 인덱스는 모든 레코드에 대한 주소값을 가져야 하므로 밀집 인덱스여야 한다.

• 다단계 인덱스: 릴레이션의 크기가 어마어마한 경우에는 그에 대한 인덱스만 만들어도 인덱스 크기가 너무 커 전체 인덱스가 블록 하나에 담기지 않을 수도 있다. 이 경우 ‘인덱스에 대한 인덱스’를 만들면 적어도 그 인덱스는 블록 하나 안에 다 담을 수 있다. 이처럼 인덱스를 여러 단계로 만든 것을 다단계 인덱스라 하며, 가장 상위 단계 인덱스를 마스터 인덱스(master index)라 한다.

  • 다단계 인덱스의 각 단계는 희소 인덱스이며, 따라서 마스터 인덱스의 크기는 매우 작아 메인 메모리에 상주할 수도 있다.

  • 다단계 인덱스는 보통 B+ 트리 구조를 갖는다.

3) 인덱스에 관한 DDL

CREATE INDEX id1 ON table1(field1, field2)

- 표준 SQL에서는 특별히 인덱스에 관한 사항이 규정되지 않았지만 여러 DBMS에서 자체적으로 사용자가 임의로 인덱스를 생성할 수 있게 하는 쿼리를 지원한다. (표준 SQL 규정이 없으므로 각 DBMS마다 SQL 문법 규칙은 각자 다를 수 있다.)

4. 물리적 데이터베이스 설계와 인덱스

- 인덱스는 장단점이 있으므로 릴레이션의 모든 필드에 대해 인덱스를 만들 게 아니라 각 필드마다 장단점을 적절히 고려하여 인덱스를 만들지 말지를 결정해야 한다. 예를 들어 어떤 필드에 대해서는 어차피 매번 모든 레코드를 탐색해야 하는 쿼리가 들어온다면 그 필드를 기준으로 한 인덱스는 만들 필요가 없다.

- 인덱스는 클러스터/비클러스터 인덱스, 희소/밀집 인덱스, 기본/보조 인덱스, 단일 단계/다단계 인덱스 등 여러 종류가 있으므로, 각 필드에 관해 입력되는 쿼리의 특성을 고려해 인덱스를 생성할 필요가 있다.

- 구체적으로 주로 어떤 쿼리가 들어오는 DB인지, 각 쿼리의 우선순위와 빈도는 각각 어떠한지 등을 먼저 분석하고 그 다음 어떤 필드에 인덱스를 사용하는 것이 좋은지, 그 인덱스는 어떤 인덱스를 사용할지 순서대로 결정하는 것이 좋다.

• 외래키, 후보키, GROUP BY 또는 ORDER BY 연산을 자주 사용하는 필드는 인덱스를 생성하는 것이 좋을 수 있다.

• 갱신이 자주 일어나는 필드나 릴레이션은 인덱스를 생성하는 것을 피하는 게 좋다.

• 대량의 데이터 삽입/삭제가 일어날 때에는 매 레코드 삽입/삭제 때마다 인덱스 변경 연산이 일어나는 것보다 전체 삽입/삭제가 종료된 뒤에 다시 인덱스를 생성하는 게 더 빠를 수 있다.

- SQL 쿼리를 쓰는 방식에 따라 인덱스를 사용하지 않는 경우가 있으므로(예를 들면 조건절에서 필드에 관한 산술연산 등을 하는 경우 등), 인덱스 생성 여부를 결정할 때 또는 인덱스를 활용하여 쿼리의 성능을 개선하고자 할 때 이 점을 고려해야 한다.

* 해시

- 릴레이션의 특정 속성에 관해 인덱스를 사용하는 경우 그 속성값에 해당하는 레코드의 디스크 내 주소를 찾으려면 인덱스 트리라 하더라도 3-4회 이상 인덱스 트리를 탐색해야 찾을 수 있다. 만약 해시를 이용해, 각 속성값에 대응되는 레코드의 디스크 내 주소를 얻을 수 있는 해시 함수를 찾을 수 있다면 단 한 번의 탐색으로 특정 속성값에 해당하는 레코드의 디스크 내 주소를 찾을 수 있다.

- 다만 해시의 경우 속성값의 범위를 기준으로 여러 레코드를 가져오는 작업에 있어서는 인덱스 트리보다 더 효율적이라 할 수 없으므로 실제 용도는 다소 제한적이다.

- 확장성 해싱(extendible hashing): 일단 원래의 키값(pseudo key)에서 일부 정보만 추출하여 이를 키값으로 해, 그 키값에 대응되는 버킷 개수를 제한적으로 할당한 후, 버킷이 가득 찰 때마다 (1)pseudo key에서 추출해오는 정보의 양을 늘리고 이와 함께 (2)버킷을 추가해 (3)각 추출해온 키값에 대응되는 버킷의 주소를 각각 달리하여 버킷에 저장하는 식으로 버킷의 오버플로우 문제를 해소하는 해시 방식. 해시 테이블의 크기를 매우 효율적으로 활용한다는 이점이 있으나, 버킷이 가득 찰 때마다 이를 나누는 오버헤드가 발생한다는 단점이 있다.