Data Storage Structures

상위 문서: 데이터베이스 시스템

개요

해당 문서에서는 기본 저장 장치인 하드 디스크나 SSD에 저장된 데이터의 구성 방식과, 데이터에 접근하는 방법에 초점을 맞춘다.

File Organization

데이터베이스는 OS에 의해 관리되는 디스크에 영구적으로 저장되는 여러 개의 파일에 매핑된다. 파일은 논리적으로(logically) 구성된 레코드들의 시퀸스로 구성되며, 이들 레코드들은 디스크 블록에 매핑된다. 각 파일은 논리적으로 블록(block)이라고 불리는 고정된 길이의 저장 단위로 구성된다. 이때 블록은 일반적으로 4~8 킬로바이트의 블록 크기를 사용하는 저장 공간 할당과 데이터 전송의 단위이다. 하나의 블록에는 여러 개의 레코드가 포함될 수 있으며, 어떤 레코드들이 블록에 포함되는지는 사용되는 물리적인(physical) 데이터의 조직(organization) 방식에 따라 결정된다. 이때 사용되는 기본적인 접근 방식은 다음과 같다:

• 레코드 크기가 고정되어 있다.
• 각 파일은 동일한 타입의 레코드만 가진다.
• 다른 릴레이션(relation)들은 서로 다른 파일에 저장된다.

Fixed-Length Records

예를 들어, 대학교 데이터베이스의 instructor 레코드들로 이루어지고, figure 1과 같이 레코드들을 저장한 파일을 고려하자. 이 파일의 각 레코드는 아래와 같이 정의된다.

파일:File containing instructor records.png

Figure 1. File containing instructor records

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바이트를 두 번째 레코드에 저장하는 것이다. 그러나 이 방식에는 두 가지 문제가 존재한다.

1. 블록 크기가 53의 배수가 아닐 경우, 일부 레코드가 블록 경계에 알맞게 정의되지 않는다. 즉, 레코드의 일부는 한 블록에, 나머지는 다른 블록에 저장된다.
   • 이 경우, 해당 레코드를 읽거나 쓰기 위해 두 번의 블록 접근이 필요하게 된다.
2. 레코드를 삭제하는 것이 어렵다.
   • 삭제된 레코드가 차지하던 공간은 파일의 다른 레코드로 채워야 하거나, 삭제된 레코드를 무시할 수 있도록 표시할 방법이 필요하다.

첫 번째 문제를 피하기 위해서, 사용되는 방식은 블록이 넘치지 않도록 레코드를 저장하는 것이다. 즉 블록의 크기를 레코드 크기로 나누고, 그 몫의 크기 만큼만 레코드를 계산한다. 각 블록에서 남는 바이트는 사용하지 않고 남겨둔다.

파일:File of Figure 1, with record 3 deleted and all records moved..png

Figure 2. File of Figure 1, with record 3 deleted and all records moved.

파일:File of Figure 1, with free list after deletion of records 1, 4, and 6.png

Figure 3. File of Figure 1, with free list after deletion of records 1, 4, and 6

또한 레코드를 삭제할 때 발생하는 문제를 해결하기 위해 생각할 수 있는 간단한 방식은 레코드가 삭제될 때, 삭제된 레코드 자리에 그 다음 레코드를 옮기고, 그 다음 레코드를 또 옮기고, 이런 식으로 모든 레코드를 앞으로 당기는 것이다. 이는 figure 2에 잘 나타나있다. 하지만 이런 접근은 매우 많은 레코드를 이동시켜야 하기 때문에 비효율적이다. 혹은 파일의 마지막 레코드를 삭제된 자리로 옮기는 것이 더 쉬울 수 있다. 그러나, 삭제된 레코드의 자리를 채우기 위해 레코드를 이동시키는 방식은 권장되지 않는다. 이는 이동 과정에서 추가적인 블록 접근이 필요하기 때문이다.
따라서, 파일에서 레코드를 삭제하고, 삭제된 자리를 표시하는 방식을 생각할 수 있다. 또한 일반적으로 삽입이 삭제보다 더 자주 발생하므로, 삭제된 레코드가 차지하던 공간은 비워 두었다가 이후 삽입 시 재사용하는 방식으로 활용하는 것을 가능케 한다는 점에서 좋아보인다. 하지만, 나중에 삽입 시 빈 레코드 공간을 찾는 것이 어렵기 때문에 역시 권장되지 않는다. 따라서 이 방식을 더 잘 활용하기 위해서, 추가적인 구조를 도입해야 한다.
이는 파일의 시작 부분에 일정 바이트를 파일 헤더로 할당하고, 삭제된 첫 번째 레코드의 주소 정보를 저장하는 것이다. 또한 첫 번째 삭제된 레코드 자리에는 두 번째 삭제된 레코드의 주소를 저장하고, 이런 식으로 연결된 구조를 형성한다. 이렇게 삭제된 레코드들은 연결 리스트(linked list)를 형성하며, 이를 보통 프리 리스트(free list)라고 한다. figure 3는 figure 1의 파일에서 레코드 1, 4, 6이 삭제된 후의 프리 리스트를 보여준다. 새로운 레코드를 삽입할 때는, 헤더가 가리키는 삭제된 레코드 위치를 사용한다. 그리고 헤터 포인터는 다음으로 사용가능한 레코드 자리를 가리키도록 변경된다. 만약 사용 가능한 공간이 없다면 새 레코드를 파일의 끝에 추가한다. 고정 길이(fixed-length) 레코드를 사용하는 파일에서는 삽입과 삭제가 단순하게 구현될 수 있다. 이는 삭제된 레코드가 차지하던 공간의 크기가 정확히 새로운 레코드가 필요한 공간의 크기와 일치하기 때문이다. 하지만 가변 길이(variable-length) 레코드를 사용하는 경우, 이러한 일치가 더 이상 성립하지 않는다.

Variable-Length Records

데이터베이스 시스템에서는 여러 이유로 인해 가변 길이 레코드(variable-length records)가 발생한다. 가장 일반적인 이유는 문자열과 같은 가변 길이 필드의 존재 때문이다. 그 밖의 이유로는 배열이나 다중 집합(multisets)과 같은 iterative 필드를 포함하는 레코드 타입이나, 하나의 파일 안에 여러 종류의 레코드 타입이 존재하는 경우가 있다.

가변 길이 레코드를 구현하기 위한 여러 기법이 존재하며, 이러한 기법은 아래의 두가지 문제를 해결해야 한다:

1. 개별 속성(attribute)이 가변 길이라 하더라도, 주어진 레코드 내에서 가변 길이 속성을 쉽게 추출할 수 있도록 표현해야 한다.
2. 블록 내에서 레코드를 쉽게 추출할 수 있도록 저장해야 한다.

이를 구현하기 위해서, 가변 길이 속성을 가진 레코드를 표현할 때는 일반적으로 두 부분으로 구성된다:

1. 고정된 길이를 가지는 초기 부분: 고정 길이 필드와, 가변 길이 필드에 대한 (offset, length)쌍들
2. 가변 길이를 가지는 속성들의 실제 값

예를 들어, 정수나 날짜, 고정 길이 문자열과 같은 고정 길이 속성은 해당 값을 저장하는 데 필요한 바이트 수 만큼을 할당한다. 반면, 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)가 있으며, 다음 정보를 담고 있다:

• 블록 내에 존재하는 레코드 항목 수
• 블록 내 남은 여유 공간의 끝을 가리키는 포인터
• 각 레코드의 위치와 크기 정보를 담은 배열

실제 레코드들은 블록의 끝 부분부터 연속적으로 할당되므로, 헤더 배열의 마지막 항목과 첫 번째 레코드 사이가 여유 공간 영역이다. 레코드를 삽입하면, 여유 공간 끝에서 공간을 할당하고, 헤더에 해당 레코드의 크기와 위치를 추가한다. 레코드를 삭제하면 해당 공간은 비워지고, 헤더에서 해당 항목은 삭제된 것으로 처리된다. 그리고 삭제된 레코드 앞의 레코드들을 앞으로 이동시켜 여유 공간이 한 곳에 연속적으로 유지되도록 한다. 그리고 이에 따라 헤더의 항목들과, 여유 공간을 가리키는 포인터를 갱신한다.

슬롯 페이지 구조에서는, 레코드를 가리키는 포인터가 직접 레코드를 가리키지 않고 헤더 배열의 항목(슬롯)을 가리킨다. 이런 간접화(indirection)를 통해, 블록 내에서 레코드를 이동시켜도 해당 포인터를 통해 접근이 가능하게 한다.