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) 레코드를 사용하는 경우, 이러한 일치가 더 이상 성립하지 않는다.
