데이터베이스(8) : 데이터 저장소의 구조(Data Storage Structure)

데이터 파일의 구조

스토리지의 구조를 알려면 우선 파일에 대해서 알아야한다. 데이터베이스가 사실 파일의 집합체이기 때문이다.

파일은 페이지의 집합체이고, 페이지는 레코드의 집합체이고, 레코드는 필드의 집합체이다.

여기서 레코드와 필드는 우리가 여태 배운 객체(row, object)와 attribute라고 생각하면 된다.

즉, DB > File > Page > Records > Fields 순으로 큰 단위가 되는 것이다.

 

파일의 구조는 레코드의 사이즈가 고정형이냐 가변형이냐에 따라 구분할 수 있다.

가장 쉬운 방법은 레코드의 사이즈가 고정되었다고 가정하고, 파일이 하나의 레코드 타입만 가진다고 가정하는 것.

즉 각 파일에 서로 다른 relation(테이블)이 저장되어있는 것이다. 이렇다고 가정하고 밑의 내용을 보도록하자.

Fixed-Length Records

가장 간단한 데이터 저장 접근법으로, 각 레코드의 사이즈를 n 이라고 가정하면, i 개의 레코드가 있을 시

파일의 크기는 n * i 가 된다. 가장 쉬운 방법이지만 지정해둔 바운더리를 넘어가는 overhead 발생 가능성이 있다.

이런 상태인 파일이 있다고 해보자.

여기서 레코드 하나를 삭제하는 방법에는 크게 세 가지가 있다.

 

1. i번째 레코드를 삭제하고, i+1...n번째 레코드를 i...n-1번째로 이동시키는 방법

2. 가장 마지막 레코드를 i번째 위치에 이동시키는 방법

3. 레코드의 이동 없이, 연결리스트를 사용해 free space를 관리하는 방법 

 

1번의 예시부터 보면, 가장 프로그래밍하면서 자주 보게 되는 재정렬 방식이다. 3번 레코드를 지웠다고 가정하면,

위의 사진처럼 빈 자리를 뒤에서 한 칸씩 앞으로 땡기면서 채워주는 느낌이다.

그럼 자연스레 다음에 들어올 정보는 가장 마지막 칸에 저장될 것이다.

 

2번의 예시도 매우 간단하다. 그냥 맨 마지막에 있던 레코드를 빈 자리로 가져오면 된다.

 

마지막 3번의 경우는, 연결 리스트를 통해 새로운 데이터가 들어갈 수 있는 free space를 구성하는 것이다.

위의 사진처럼, 삭제된 자리를 다시 채우는 것이 아니라, 그냥 그대로 두고 연결 리스트로 구조를 유지해준다.

이후 새로운 데이터가 들어오면, free space의 위치를 연결 리스트를 통해 접근해 데이터를 삽입한다.

레코드의 길이를 고정형으로 가정하면 이렇게 매우 간단하게 파일을 구성할 수 있다.

그렇다면 가변형일 경우에는 어떨까?

Variable-Length Records

레코드의 길이를 가변형으로 할 경우, 고정형에 비해 다양한 타입의 레코드를 저장할 수 있고,

레코드들의 attribute(field)를 길이 제한 없이 설정해 사용할 수 있다는 장점이 있다.

그러나 고정형보다는 방법이 약간 복잡하다. 밑의 구조를 보면서 살펴보자.

 

기본적으로, attribute들은 순차적으로 저장되어 있다. 이때, 사진의 0000 위치를 기준으로 좌우가 정보가 나뉘게 된다.

실제 정보는 우측에 있는 것들이고, 좌측에 있는건 해당 우측 정보를 찾아가게끔 해주는 힌트라고 생각하면 된다.

즉, 데이터에 관한 정보이므로 메타데이터 격이라고 생각하면 좋을 것 같다.

이런 구조를 slotted page라고 부르며, 좌측은 block header, 우측은 records 라고 한다.

 

Block header(그림의 좌측 블록들)의 내부에 들어가는 정보는 크게 세 가지가 있다.

 

1. 객체의 수

2. free space의 끝부분의 위치

3. 각 레코드의 위치와 사이즈

 

그 중 3번에 대해서 조금 더 이야기하자면, 사진의 (21, 5)라고 적힌 블록을 보자. 해당 블록이 의미하는 바는

21byte부터 5byte만큼 정보가 저장되어 있다는 뜻이다. 사진을 보면 21~26 블록에 '10101'이 저장되있음을 알 수 있다.

이런 식으로 앞의 헤더를 고정형 길이로 유지해 정보를 저장해줌으로써, 우측의 실제 레코드는 가변형으로 저장할 수 있다.

이런 구조를 잘 사용한다면, 파일의 공간 낭비가 없이 가변형 레코드로 파일을 채워 효율적으로 사용할 수 있다.

물론 그때그때 헤더를 잘 업데이트해줘야 하기 때문에 귀찮은 작업이긴 하다.

그 외의 파일 구조들

이외에도 여러 파일 구조들이 존재한다.

• Heap(힙 구조)
  
  • 구조화 하기 매우 간단하고 기본적인 방법이다.
  • 레코드를 파일의 끝에 저장하고, 굳이 추가로 삽입 시에 정렬이나 순서를 맞춰줄 필요가 없다.
  • 즉, 파일의 빈 공간이 있다면 어디든 새로운 데이터가 삽입될 수 있다.
• Sequential(순차 구조)
  • 뒤에 알아볼 구조중 하나로, 연결 리스트같은 방식을 이용해 순차적으로 데이터를 저장한다.
• Multitable clustering file organization
  • 서로 다른 타입의 relation을 하나의 파일에 저장하기 위해 사용되는 구조이다.
  • 주로 겹치는 attribute가 존재하고, 하나로 묶을 수 있을 때 사용하는 방법이다.
• B+ 트리
  
  • Balanced binary search tree를 활용한 구조로, 대부분의 DBMS가 채용하는 방식이다.
• Hashing
  • 해시함수를 계산해 나온 값에 위치한 블록에 데이터를 놓는 방식이다.

이런 파일 구조들이 존재하는데, 이 중 몇 가지만 알아보도록 하자.

Sequential File Organization

전체 파일의 입력을 순차적으로 처리하는 프로그램에 적합한 방식중 하나이다.

간단한 방법이지만, 접근 비용이 매우 거대해진다는 단점이 존재한다.

각 레코드들은 탐색 키에 의해 순서를 가지고 정렬된다(연결 리스트와 비슷함)

새로운 데이터의 삽입과 삭제도 연결 리스트의 방식과 매우 유사하다.

우선 삭제의 경우, 간단하게 연결 리스트의 포인터만 바꿔주면 된다. 중간의 33456 행을 삭제한다고 하면,

33456이 가리키는 다음 객체에 대한 포인터를, 32343이 가리키게끔 하면 자연스레 리스트에서 사라진다.

 

삽입의 경우는 free space의 존재 여부에 따라 방식이 달라지는데,

만약 free space가 있다면 그냥 그 위치에 데이터를 삽입하고 마지막 객체의 포인터를 연결해주면 된다.

없는 경우에는 overflow block에 데이터를 삽입한다. 두 경우 모두 포인터를 잘 연결해주어야 한다!

더불어 연결 리스트 방식이기 때문에, 이 순서를 잘 유지하기 위해 주기적으로 포인터 업데이트를 잘 해야한다.

Multitable Clustering File Organization

위에 적었듯이 여러 개의 relation을 하나의 파일에 저장하기 위해 고안된 방법이다.

다음과 같이 두 개의 테이블이 있다고 했을 때, dept_name을 이용해서 클러스터링을 진행해주면 다음과 같다.

사실 이렇게 보면 굉장히 난해한 정리 방법이다. 실제로도 자주 사용되지는 않는 방법이다.

왜냐면 해당 파일 구조는 join 쿼리에만 효율적이기 때문이다.

두 테이블을 하나로 합쳐버렸으니 당연히 join에는 좋은 효율을 보일 것이지만, 그외의 쿼리에는 그다지 좋지 못하다.

더불어 쿼리의 결과 또한 레코드의 사이즈가 고정되어있지 않을 수 있기 때문에, 여러 장단점이 존재한다.

B+ Tree

균형 이진탐색 트리라고도 부르는 이 구조는, 현재 대부분의 DBMS에서 채용하는 구조로 알려져있다.

특히 인덱스에 해당 트리구조를 사용하는데, 설명을 보면 이해가 될 것이다.

기본적으로 모든 데이터, 레코드는 트리의 리프노드(맨 끝 노드)에 위치해 있다.

 

위와 같은 트리 모양을 생각해보자. 우리가 55라는 값을 찾고 싶다고 한다면,

55를 포함할 만한 intermediary node에 접근해야 한다. 이때 intermediary node는 그림 상 실제 값 사이에 있는 부분이다.

55를 찾으려면 50과 75 사이에 있는 노드에 접근하면 될 것이라고 쉽게 유추해볼 수 있다.

 

즉, intermediary node에는 양쪽 값 사이에 존재하는 값들로 연결해주는 포인터가 존재한다고 생각하면 된다.

이후 노드를 통해서 진입하면, 순차탐색을 통해 원하는 데이터가 있는지 찾아내어 반환하면 끝이다.

데이터베이스 포스트기 때문에 매우 간단하게 설명했는데, 자세한 설명은 다른 자료구조 포스트를 찾아보길 바란다!

저장소 접근(Storage Access)

스토리지에 저장한 데이터를 가져오려면 직접 접근해 해당 부분의 정보를 메모리로 가져오는 과정이 필요하다.

이때 스토리지로부터 메모리로 데이터를 옮길 때도 블록에 데이터를 할당하고 반환하는 작업이 수행되는데,

최적화를 위해서 이러한 전송 작업을 할 때 최대한 덜 블록을 사용해야 한다.

즉, 메모리가 클수록 유리하며 한 번 가져올 때 최대한 많은 양의 블록을 메모리에 저장해야 최적화가 이루어진다.

Buffer(버퍼)

이때 사용하는 것이 버퍼(buffer)다. 버퍼는 메모리의 일부를 스토리지 블록들의 복사본을 저장하기 위해 빼둔 공간이다.

즉, 매번 스토리지에서 데이터를 블록을 통해 가져올 필요 없이 미리 버퍼에 복사해두고 그걸 쓰겠다는 이야기다.

 

버퍼는 버퍼 매니저에 의해 관리되는데, 이제부터 그 과정을 알아보겠다.

우선 버퍼 매니저(buffer manager)는 메인 메모리에 버퍼 공간을 할당해주는 서브시스템을 이야기한다.

 

1. 프로그램이 버퍼 매니저에게 특정 데이터를 요청한다.

2. 해당 데이터가 이미 버퍼에 있다면 버퍼에서 해당 데이터가 있는 블록의 주소를 바로 반환해준다.

3. 데이터가 없는 경우는 두 가지로 나뉜다.

1. 버퍼에 공간이 있는 경우
   • 버퍼 매니저가 버퍼에 블록을 복사해둘 공간을 할당한다.
2. 버퍼에 공간이 없는 경우
   • 버퍼에 있는 다른 블록들을 우선순위에 따라 재배치(Replacing, throwing out)해 공간을 만들어 할당한다.
   • 이때 재배치되는 블록은, 가장 오랫동안 사용하지 않은 블록이 재배치된다.

4. 이후 공간을 할당해 블록을 복사해왔으면, 해당 블록의 주소를 반환해준다.

 

이런 과정을 통해 버퍼가 작동해 스토리지에 효율적으로 접근해 데이터를 사용할 수 있게 해준다.

Buffer replacement strategy

아무래도 한정된 크기의 버퍼에서 이보다 큰 양의 데이터를 읽고 쓰고 해야하기 때문에, 교체에도 몇 가지 전략이있다.

몇 가지 개념들이 추가되는데 이를 알아보자.

• Pinned block :
  • 이는, 내용을 변경할 수 없는 메모리 블록을 이야기한다. 주로 현재 사용중인 블록이 고정되는 경우가 많다.
• Shared and Exclusive locks :
  • 데이터베이스에 혼자 접근하는 것이 아니므로, 동시다발적인 연산이 요청될 때가 있다. 읽기, 쓰기 다양하지만
    읽기는 여러 명이 동시에 해도 문제가 안된다. 그러나 쓰기, 수정은 동시에 진행되면 문제가 생긴다.
    
    
  • 그래서 Reader들은 shared lock(공유락)을 받고, update를 하려면 exclusive lock(배타락)이 필요하다.
    이때 몇 가지 규칙이 생긴다.
  • exclusive lock(배타락)은 블록에 대해 오직 한 프로세스만 사용할 수 있고, 공유락과 동시에 사용되지 않는다.
    즉, 배타락을 걸고 데이터를 수정하는 순간, 해당 프로세스를 제외한 누구도 읽을 수 없고 접근할 수 없다.
  • shared lock(공유락)은 한 블록에 대해 여러 명이 동시에 접근해도 문제가 없다.

이런 개념과 추가로, 버퍼가 꽉 차있을 때 어떤 블록을 버리는지에 대해 알아보자.

거의 대다수의 운영체제는 LRU strategy(Least Recently Used) 방식을 사용한다.

즉, 가장 오랫동안 사용되지 않은 블록을 제거한다. 오래 사용하지 않았으니, 앞으로도 안쓸거라 판단해 버리게 된다.

가장 최근에 사용된 블록이 뒤, 덜 사용된게 앞에 놓인다. 이후 맨 앞의 블록을 제거하며, 맨 뒤에 블록을 추가한다.

버퍼 매니저가 이런 개념과 방식을 통해 버퍼가 꽉 차더라도 새 데이터를 저장할 수 있게끔 관리해주는 역할이다.

이번 포스트에서 가장 중요한 부분이기도 하니, 잘 알아두자.

Column-Oriented Storage

마지막으로 기존에 알던 행 단위의 저장방식과 다른 열 지향적인 저장소를 소개하고 마무리하겠다.

말 그대로 객체의 각 attribute를 분리해서 저장하는 방식이다. 상상만해도 불편하지만 놀랍게도 존재는 한다고 한다.

본인같으면 매우 불편해서 안쓰겠지만.. 나름 장점은 있다.

• 장점
  • 만약 특정 열에만 접근해야 하는 데이터베이스의 경우는 I/O 횟수가 줄어든다.
• 단점
  • 열 기준의 데이터로 다시 각 레코드를 재구성하는데 매우 많은 시간과 비용이 소모된다.
  • 레코드를 삭제하고 수정하는데 매우 많은 시간과 비용이 소모된다.

더불어 트랜잭션 처리나, 기존의 DB들은 모두 row-oriented 를 사용하기 때문에, 호환성때문에라도 열은 잘 안쓴다.

 

 

이상으로 이번 포스트까지해서, 데이터베이스의 스토리지 그 자체에 대해서 알아보았다.

다음장부터는 다시 트랜잭션, 정규화 등 데이터베이스 안 쪽의 내용으로 돌아갈 것 같다.

데이터베이스 포스트도 어느덧 끝을 향해 가고있는데, 끝까지 잘 봐주시길 바라겠다.