[ADV_db]Chap 2. 데이터 저장 장치 구조-2

---

# 레코드 저장 방법

---

Heap File Organization

• 빈 공간에 어디든 저장하는 방식
• 한번 할당받아서 저장된 레코드들은 움직이지 않는다. 
• 중요한 문제는 Free Space를 효과적으로 찾는 방법
  • Free-Space Map
    • 파일의 블록 중에 빈곳을 표시해주는 데이터 구조
    • 만약 하나의 블록이 3bit로 이루어져 있다고 한다면, 각 블록을 8로 나누면 비어있는 곳이 얼마나 있는지 알 수 있다. 
     

• Second-Level Free Space Map
  • 각 엔트리가 First-level Space Map의 4개씩을 나타낸다면 그 중 최대값만을 이용하여 빈곳을 탐색하는 시간을 더욱 줄일 수 있다.
   

Sequential File Organization

• Search-Key를 기반으로 정렬하여 파일에 레코드를 저장한다.
• Insertion
  • 비어있는 곳이 있다면 그곳에 넣으면 되지만, 비어있는 곳이 없다면 다른 공간(Overflow Block)에 만들고 순서에 맞게 포인터로 연결한다.
  • 주기적으로 재구성을 해줘야 한다.
• Deletion
  • 삭제 시 포인터를 이용하여 순서를 조정한다.
   

Multitable Clustering File Organization

• 자주 같이 쓰이는 릴레이션은 하나의 파일로 구성하여 두는 방식
• 디스크 접근을 최소화하기위해 서로 관련된 레코드를 같이 두는 방식
• 두 릴레이션에 대한 쿼리가 들어올 때는 빠르지만, 그렇지 않은 경우에는 더 느리게 할 수 있다.
• 포인터 체인을 통해 구현할 수 있다.

 

• Table Partitioning
  • GiantTable을 여러개의 작은 테이블로 나누어 여러 저장장치에 나누어 저장할 수 있도록 하거나, 공간 관리에 더 용이하도록 만든다.
  • 예를 들어, 한양대학교 모든 학생들을 저장하기보다는 연도로 나누어 저장하는게 더 효율적이다.
• Data Dictionary Storage
  • Meta Data 를 저장하고 있는 데이터 사전 

---

# Buffer Manager

---

• Block이라는 거는 저장장치에 저장과 데이터 전송의 단위다.
• 따라서 시스템에서는 디스크와 메모리 사이의 블록 움직임을 최소화하려고 노력한다.
  • 메인 메모리에 많은 블록을 두면 디스크에 접근하는 일을 줄일 수 있다.

 

프로그램이 필요한 블록을 요청했을 때 이미 버퍼에 있다면 버퍼 매니저를 통해 버퍼에서 바로 꺼내 줄 수 있다. 그러나 없다면, 버퍼 매니저가 디스크에서 해당 블록을 가져와 버퍼에 옮긴 후에 주소를 되돌려준다. 만약 버퍼가 가득 찼는데 없는 블록을 요청한다면, 버퍼 매니저는 버퍼 중 삭제할 데이터를 결정한 후 삭제하고 새로운 데이터를 가져와 프로그램에게 주소를 알려준다.

하지만, 만약 프로그램에서 사용중인 데이터 블록을 삭제할 수도 있기 때문에 사용중인 데이터 블록에는 Pin을 해두어 삭제되지 않도록 하고 사용한 후에는 Unpin해야 한다. 이러한 Pin은 여러 프로세스에서 할 수 있기 때문에 Pin count를 통해 0이 되어야지만 삭제될 수 있도록 관리한다. 이 때, 삭제할 블록은 Least Recently Used(LRU)전략을 통해 삭제가 이루어진다. 하지만 특정 쿼리들에서는 이게 좋지 않을 수 있다. 이런 경우에는 Toss-immediate(마지막 반복이 끝나고 삭제하는 방식)이나 Most-Recently used방식을 사용할 수 있다.

 

그리고 동시에 해당 블록을 수정하면 겹칠 수 있기에 Shared Lock과 Exclusive Lock을 이용하여 여러 프로세스가 접근한 데이터에 대해 겹치지 않도록 한다. 

• Update에 필요한 Exclusive Lock의 경우 동시에 하나의 프로세스에만 주어진다.
• Read에 필요한 Shared Lock의 경우 여러 프로세스에게 동시에 주어진다.
• 하지만 Exclusive Lock이 되어 있는 경우 Shared Lock은 부여되지 않는다.