Data Storage Structures
상위 문서: 데이터베이스 시스템
개요
해당 문서에서는 기본 저장 장치인 하드 디스크나 SSD에 저장된 데이터의 구성 방식과, 데이터에 접근하는 방법에 초점을 맞춘다.
File Organization
데이터베이스는 OS에 의해 관리되는 디스크에 영구적으로 저장되는 여러 개의 파일에 매핑된다. 파일은 논리적으로(logically) 구성된 레코드들의 시퀸스로 구성되며, 이들 레코드들은 디스크 블록에 매핑된다. 각 파일은 논리적으로 블록(block)이라고 불리는 고정된 길이의 저장 단위로 구성된다. 이때 블록은 일반적으로 4~8 킬로바이트의 블록 크기를 사용하는 저장 공간 할당과 데이터 전송의 단위이다. 하나의 블록에는 여러 개의 레코드가 포함될 수 있으며, 어떤 레코드들이 블록에 포함되는지는 사용되는 물리적인(physical) 데이터의 조직(organization) 방식에 따라 결정된다.[1] 이때 사용되는 기본적인 접근 방식은 다음과 같다:
- 레코드 크기가 고정되어 있다.
- 각 파일은 동일한 타입의 레코드만 가진다.
- 다른 릴레이션(relation)들은 서로 다른 파일에 저장된다.
Fixed-Length Records
예를 들어, 대학교 데이터베이스의 instructor 레코드들로 이루어지고, figure 1과 같이 레코드들을 저장한 파일을 고려하자. 이 파일의 각 레코드는 아래와 같이 정의된다.
type instructor = record
ID varchar(5);
name varchar(20);
dept_name varchar(20);
salary numeric(8,2);
end
각 문자가 1바이트를 차지하고, numeric(8, 2) 타입이 8바이트를 차지한다고 가정하자. 또한 속성인 ID, name, dept_name에 대해 가변적인 크기의 바이트를 할당하는 대신, 각 속성이 가질 수 있는 최대 바이트 수를 고정적으로 할당한다고 가정하자. 그러면 instructor 레코드는 총 53바이트의 크기를 가지게 된다. 이때 instructor 레코드를 파일에 저장하는 가장 간단한 방식은 파일의 첫 53바이트를 첫 레코트에, 그 다음 53바이트를 두 번째 레코드에 저장하는 것이다. 그러나 이 방식에는 두 가지 문제가 존재한다.
- 블록 크기가 53의 배수가 아닐 경우, 일부 레코드가 블록 경계에 알맞게 정의되지 않는다. 즉, 레코드의 일부는 한 블록에, 나머지는 다른 블록에 저장된다.
- 이 경우, 해당 레코드를 읽거나 쓰기 위해 두 번의 블록 접근이 필요하게 된다.
- 레코드를 삭제하는 것이 어렵다.
- 삭제된 레코드가 차지하던 공간은 파일의 다른 레코드로 채워야 하거나, 삭제된 레코드를 무시할 수 있도록 표시할 방법이 필요하다.
첫 번째 문제를 피하기 위해서, 사용되는 방식은 블록이 넘치지 않도록 레코드를 저장하는 것이다. 즉 블록의 크기를 레코드 크기로 나누고, 그 몫의 크기 만큼만 레코드를 계산한다. 각 블록에서 남는 바이트는 사용하지 않고 남겨둔다.
또한 레코드를 삭제할 때 발생하는 문제를 해결하기 위해 생각할 수 있는 간단한 방식은 레코드가 삭제될 때, 삭제된 레코드 자리에 그 다음 레코드를 옮기고, 그 다음 레코드를 또 옮기고, 이런 식으로 모든 레코드를 앞으로 당기는 것이다. 이는 figure 2에 잘 나타나있다. 하지만 이런 접근은 매우 많은 레코드를 이동시켜야 하기 때문에 비효율적이다. 혹은 파일의 마지막 레코드를 삭제된 자리로 옮기는 것이 더 쉬울 수 있다. 그러나, 삭제된 레코드의 자리를 채우기 위해 레코드를 이동시키는 방식은 권장되지 않는다. 이는 이동 과정에서 추가적인 블록 접근이 필요하기 때문이다.
따라서, 파일에서 레코드를 삭제하고, 삭제된 자리를 표시하는 방식을 생각할 수 있다. 또한 일반적으로 삽입이 삭제보다 더 자주 발생하므로, 삭제된 레코드가 차지하던 공간은 비워 두었다가 이후 삽입 시 재사용하는 방식으로 활용하는 것을 가능케 한다는 점에서 좋아보인다. 하지만, 나중에 삽입 시 빈 레코드 공간을 찾는 것이 어렵기 때문에 역시 권장되지 않는다. 따라서 이 방식을 더 잘 활용하기 위해서, 추가적인 구조를 도입해야 한다.
이는 파일의 시작 부분에 일정 바이트를 파일 헤더로 할당하고, 삭제된 첫 번째 레코드의 주소 정보를 저장하는 것이다.[2] 또한 첫 번째 삭제된 레코드 자리에는 두 번째 삭제된 레코드의 주소를 저장하고, 이런 식으로 연결된 구조를 형성한다. 이렇게 삭제된 레코드들은 연결 리스트(linked list)를 형성하며, 이를 보통 프리 리스트(free list)라고 한다. figure 3는 figure 1의 파일에서 레코드 1, 4, 6이 삭제된 후의 프리 리스트를 보여준다. 새로운 레코드를 삽입할 때는, 헤더가 가리키는 삭제된 레코드 위치를 사용한다. 그리고 헤터 포인터는 다음으로 사용가능한 레코드 자리를 가리키도록 변경된다. 만약 사용 가능한 공간이 없다면 새 레코드를 파일의 끝에 추가한다. 고정 길이(fixed-length) 레코드를 사용하는 파일에서는 삽입과 삭제가 단순하게 구현될 수 있다. 이는 삭제된 레코드가 차지하던 공간의 크기가 정확히 새로운 레코드가 필요한 공간의 크기와 일치하기 때문이다. 하지만 가변 길이(variable-length) 레코드를 사용하는 경우, 이러한 일치가 더 이상 성립하지 않는다.
Variable-Length Records
데이터베이스 시스템에서는 여러 이유로 인해 가변 길이 레코드(variable-length records)가 발생한다. 가장 일반적인 이유는 문자열과 같은 가변 길이 필드의 존재 때문이다. 그 밖의 이유로는 배열이나 다중 집합(multisets)과 같은 iterative 필드를 포함하는 레코드 타입이나, 하나의 파일 안에 여러 종류의 레코드 타입이 존재하는 경우가 있다.
가변 길이 레코드를 구현하기 위한 여러 기법이 존재하며, 이러한 기법은 아래의 두가지 문제를 해결해야 한다:
- 개별 속성(attribute)이 가변 길이라 하더라도, 주어진 레코드 내에서 가변 길이 속성을 쉽게 추출할 수 있도록 표현해야 한다.
- 블록 내에서 레코드를 쉽게 추출할 수 있도록 저장해야 한다.
이를 구현하기 위해서, 가변 길이 속성을 가진 레코드를 표현할 때는 일반적으로 두 부분으로 구성된다:
- 고정된 길이를 가지는 초기 부분: 고정 길이 필드와, 가변 길이 필드에 대한 (offset, length)쌍들
- 가변 길이를 가지는 속성들의 실제 값
예를 들어, 정수나 날짜, 고정 길이 문자열과 같은 고정 길이 속성은 해당 값을 저장하는 데 필요한 바이트 수 만큼을 할당한다. 반면, varchar 타입과 같은 가변 길이 속성은 (offset, length) 쌍으로 표현된다. 이때 offset은 해당 속성의 실제 값이 레코드 내에서 어디서 시작되는지를 나타내고, length는 그 속성의 바이트 수를 의미한다. 이렇게 초기 부분이 고정된 길이로 작성된 채로, 가변 길이 속성들의 실제 값은 레코드의 초기 고정 부분 다음에 연속적으로 저장된다. Figure 4는 이러한 표현 방식의 예시를 보여준다. 해당 그림은 instructor 레코드를 보여주며, 이 레코드는 처음 세 개의 속성 ID, name, dept_name이 가변 길이 문자열이고, 네 번째 속성 salary는 고정 크기의 숫자이다. 이때 offset과 length는 각각 2바이트로 저장된다고 가정하면, 각 가변 길이 속성 당 4바이트가 필요하다. 또한 salary는 8바이트로 저장되며, 문자열은 각 문자의 개수만큼 바이트를 사용한다고 가정한다. 이 경우, 레코드의 초기 부분은 20바이트의 고정된 길이로 저장된다. 해당 figure는 또한 null bitmap의 사용도 보여준다. 이 비트맵은 레코드의 어떤 속성이 null 값인지를 나타낸다. 예를 들어, salary 속성이 null이라면, null 비트맵의 네 번째 비트가 1로 설정되고, 12~19 바이트에 저장된 salary 값은 무시된다. 이 레코드는 4개의 속성을 가지므로, null 비트맵은 1바이트면 충분하다.
다음으로, 가변 길이 레코드를 블록 내에 저장하는 방식은 슬롯 페이지 구조(slossted-page structure)이며, 이는 figure 5에 잘 나타나 있다. 각 블록의 시작 부분에는 헤더(header)가 있으며, 다음 정보를 담고 있다:
- 블록 내에 존재하는 레코드 항목 수
- 블록 내 남은 여유 공간의 끝을 가리키는 포인터
- 각 레코드의 위치와 크기 정보를 담은 배열
실제 레코드들은 블록의 끝 부분부터 연속적으로 할당되므로, 헤더 배열의 마지막 항목과 첫 번째 레코드 사이가 여유 공간 영역이다. 레코드를 삽입하면, 여유 공간 끝에서 공간을 할당하고, 헤더에 해당 레코드의 크기와 위치를 추가한다. 레코드를 삭제하면 해당 공간은 비워지고, 헤더에서 해당 항목은 삭제된 것으로 처리된다.[3] 그리고 삭제된 레코드 앞의 레코드들을 앞으로 이동시켜 여유 공간이 한 곳에 연속적으로 유지되도록 한다. 그리고 이에 따라 헤더의 항목들과, 여유 공간을 가리키는 포인터를 갱신한다.
슬롯 페이지 구조에서는, 레코드를 가리키는 포인터가 직접 레코드를 가리키지 않고 헤더 배열의 항목(슬롯)을 가리킨다. 이런 간접화(indirection)를 통해, 블록 내에서 레코드를 이동시켜도 해당 포인터를 통해 접근이 가능하게 한다.
Storing Large Objects
데이터베이스는 종종 디스크 블록보다 훨씬 더 큰 데이터를 저장해야 할 수 있다. 예를 들어 이미지나 오비오, 비디오 객체들이 이에 해당한다. SQL은 이와 같은 대형 데이터를 위해 blob (binary large object), clob (character large object)와 같은 대형 객체 타입을 지원한다. 많은 데이터베이스는 내부적으로 하나의 레코드 크기가 블록 크기를 초과하지 않도록 제한한다. 이러한 시스템에서는, 레코드가 논리적으로 대형 객체를 포함할 수는 있지만 대형 객체의 실제 값은 별도로 저장되고, 레코드 안에는 해당 객체를 가리키는 포인터만 저장된다. 이때 대형 객체는 다음 방식 중 하나로 저장될 수 있다:
- 데이터베이스에 의해 관리되는 외부의 파일 시스템 영역에 저장
- 데이터베이스 내부에서 파일처럼 관리하도록 저장
- 데이터를 여러 조각으로 나눠서 별도의 릴레이션에 분산 저장(PostgreSQL TOAST)
Organization of Records in Files
하나의 릴레이션(relation)은 레코드들의 집합이며, 레코드 집합이 주어졌을 때 해결해야 할 문제 중 하나는 이 레코드들을 파일 내에서 어떻게 조직할 것인가이다. 이때 파일 내에서 레코드를 조직할 수 있는 여러 방식들이 아래와 같이 존재한다.
- Heap file organization: 어떤 레코드든, 공간만 있다면 파일 내 어디에나 저장될 수 있으며, 레코드를 정렬하는 순서가 존재하지 않는다.
- Sequential file organization: 레코드는 각 레코드의 “검색 키(search key)” 값에 따라 순차적인 순서로 저장된다.
- Multitable clustering file organization: 서로 다른 여러 릴레이션의 레코드를 하나의 파일 혹은 파일 내의 동일한 블록 내에 저장하여 어떤 조인 연산의 비용을 줄인다.[4]
- B+-tree file organization: B+-트리 인덱스 구조를 통해서 삽입, 삭제, 갱신 작업이 많더라도 레코드에 대한 효율적인 정렬 접근을 제공한다.
- Hashing file organization: 각 레코드의 어떤 속성에 대해 해시 함수를 계산하고, 이를 통해 해당 레코드를 파일의 어떤 블록에 저장할 것인지를 지정한다.
Heap File Organization
힙 파일 조직에서는, 하나의 레코드가 해당 릴레이션에 해당하는 파일 내 아무 위치에나 저장될 수 있으며, 레코드가 일단 특정 위치에 저장되면, 그 레코드는 보통 이동되지 않는다. 파일에 레코드를 삽입할 때, 한 가지 방법은 항상 파일 끝에 추가하는 것이다. 그리고 레코드가 삭제되면, 해당 공간을 새 레코드 저장에 재사용하는 것이 합리적이다. 하지만 이를 위해서는 데이터베이스 시스템은 파일의 모든 블록을 순차적으로 탐색하지 않고도, 여유 공간이 있는 블록을 효율적으로 찾을 수 있어야 한다.
대부분의 데이터베이스는 free-space map이라는 공간 효율적인 자료 구조를 사용하여 어떤 블록에 레코드를 저장할 수 있는 여유 공간이 있는지 추적한다. 이 free-space map은 보통 각 블록마다 하나의 항목(entry)을 갖는 배열로 표현된다. 배열의 항목은 해당 블록의 공간 중 적어도 f 비율이 비어 있다는 것을 나타낸다.[5] 레코드가 삽입, 삭제되거나 크기가 변경될 때, 해당 블록의 점유율(fraction)이 변화하여 저장된 값에 영향을 줄 정도라면, 그 항목은 free-space map에서 업데이트된다. Figure 6는 16개의 블록을 가진 파일에 대한 free-space map이다:
위에서 점유율을 표현하기 위해서 3비트를 사용한다고 가정한다면, 각 항목에 저장된 값을 8로 나누어서 각 블록에 해당하는 여유 공간의 비율을 구할 수 있다. 예를 들어, 값이 7이라면, 해당 블록 공간의 최소 7/8이 비어 있음을 의미한다. 주어진 크기의 새로운 레코드를 저장할 블록을 찾기 위해, 데이터베이스는 free-space map을 스캔하여 충분한 공간을 가진 블록을 찾을 수 있다. 만약 그런 블록이 없다면, 새로운 블록이 릴레이션에 할당된다.
이러한 스캔은 실제로 블록을 직접 읽는 것보다는 훨씬 빠르지만, 파일이 매우 큰 경우에도 여전히 느릴 수 있다. 이 문제를 해결하기 위해, 2단계 free-space map을 도입할 수 있다. 예를 들어, 주 free-space map의 100개 항목마다 하나의 항목을 가지는 2단계 free-space map을 생성할 수 있다. 이 항목은 해당하는 100개 항목 중 최댓값을 저장한다. 아래에 제시된 free-space map은 앞서 예시로 든 주 map에 대해 4개 항목마다 하나씩 대응되는 2단계 free-space map이다:
100개마다 하나의 항목을 가진 2단계 맵이 있다면 2단계 맵을 스캔하는 시간은 1/100로 줄어든다. 이때 충분한 여유 공간이 있는 항목을 찾으면 그에 대응되는 free-space map의 100개 항목을 스캔하여 실제로 충분한 공간을 가진 블록을 찾을 수 있다. 하지만 free-space map의 항목이 갱신될 때마다 디스크에 즉시 기록하는 것은 매우 비용이 크므로 free-space map은 주기적으로 디스크에 기록된다. 따라서 디스크에 있는 free-space map은 최신 상태가 아닐 수 있으며, 데이터베이스가 시작될 때, 오래된 여유 공간 정보를 얻을 수 있다. 그 결과, free-space map이 실제로는 공간이 없는 블록을 공간이 있다고 잘못 표시할 수 있다. 이런 오류는 해당 블록을 실제로 읽어들이면 발견되며 다시 map을 검색하여 다른 블록을 찾는 방식으로 처리된다. 반면에, map이 실제로는 공간이 있는 블록을 공간이 없다고 잘못 판단할 수도 있다. 이 경우는 단지 공간이 사용되지 않은 채 남겨지는 문제일 뿐이다.
Sequential File Organization
Sequential file은 어떤 검색 키(search key)를 기준으로 정렬된 순서를 통해서 레코드를 효율적으로 처리할 수 있도록 설계된다. 어떤 릴레이션의 어떤 속성이나 여러 속성들의 집합은 모두 검색 키가 될 수 있으며, 반드시 기본키(primary key)이거나 슈퍼키(superkey)일 필요는 없다. 이때 검색 키 순서대로 레코드를 빠르게 검색할 수 있도록, 레코드들을 포인터로 연결(chain)하고, 각 레코드에 있는 포인터는 검색 키 순서상 다음 레코드를 가리키도록 한다. 또한 sequential file 처리에서 블록에 대한 접근 횟수를 최소화하기 위해, 레코드들을 물리적으로(physically) 검색 키 순서에 가깝게 또는 가능한 한 그 순서대로 저장한다. Figure 8은 instructor 레코드들의 sequential file을 보여주며, ID를 검색 키로 사용하여 검색 키 순서로 레코드를 저장하고 있다. sequential file 조직은 레코드를 정렬된 순서대로 읽을 수 있게 해주며, 이는 출력(display)이나, 특정 질의 처리 알고리즘들에 대해서 유용하다.
하지만, 레코드가 삽입되거나 삭제될 때, 물리적 정렬 순서를 유지하는 것은 어렵다. 이는 삽입이나 삭제 하나 때문에 여러 레코드를 이동해야 하는 높은 비용이 들기 때문이다. 먼저 삭제는 이전 절에서 본 것처럼 포인터 체인을 이용해 처리할 수 있다. 그리고 삽입 작업을 위해서는 다음 두 가지 규칙을 따른다.
- 검색 키 순서상 삽입될 레코드 앞에 오는 레코드를 파일 내에서 찾는다.
- 이 레코드와 같은 블록 안에 삭제된 레코드로 인해 남은 여유 공간이 있다면, 새 레코드를 그곳에 삽입한다. 그렇지 않다면, 오버플로우 블록(overflow block)에 새 레코드를 삽입한다. 어느 경우든, 포인터를 조정하여 검색 키 순서대로 레코드들을 연결한다.
Figure 9은 (32222, Verdi, Music, 48000) 레코드를 figure 8의 파일에 삽입한 후의 구조를 보여준다. 이 구조는 새 레코드를 빠르게 삽입할 수 있게 하지만, 레코드들의 물리적 순서와 일치하지 않는 순서로 sequential file 응용 프로그램이 레코드를 처리하게 만든다. 오버플로우 블록에 저장되어야 하는 레코드 수가 적을 경우, 이 방식은 잘 작동한다. 그러나 시간이 지남에 따라 검색 키 순서와 물리적 순서 간의 대응 관계가 완전히 깨질 수도 있으며, 이 경우 seqential file의 효율성이 크게 저하된다. 이 시점에서 파일을 다시 정렬된 순서대로 물리적으로 재구성(reorganize) 해야 하는데, 이는 비용이 크므로 시스템 부하가 적은 시간에 수행해야 한다.
