[ch13] Data Storage Structures

File Organization

• db는 파일에 저장됨
• 파일은 레코드들로 구성됨
• 레코드는 여러 개의 field로 구성됨

 

• 구현하기 쉽게 가정해보자
  • 파일의 모든 레코드가 고정길이
  • 파일에 저장된 레코드 타입이 모두 동일
  • 각 테이블이 서로 다른 파일에 저장됨

 

Fixed-Length Records

• 레코드 i의 시작 위치: n*(i-1) byte
  • n: 각 레코드의 크기
• 한 block당 m개의 record가 들어감
• 레코드 삭제: 레코드 i가 삭제됨
  • opt1: 레코드 i 번째로 하나씩 옮김
  • opt2: 레코드 i를 가지고 있는 block에 마지막 레코드를 채워서 disk로 내보냄
    • 마지막 레코드를 가지고 있던 block은 마지막 레코드가 블록을 빠져나갔다고 버퍼에 업데이트 되었다가 disk에 쓰여져야 함
  • opt3: 삭제가 되는 빈 자리를 linked list로 유지

 

Variable-Length Records

• 다음과 같은 경우 가변길이 레코드 이용
  • 한 파일에 여러 타입의 레코드
  • 레코드의 field가 문자열인 경우
  • 반복되는 field를 허락하는 레코드 타입
    • 휴대전화, 직장전화, 자택전화 등 레코드마다 반복되는 field 수가 다를 수 있음
• field를 정해진 순서로 저장
• 가변길이 field는 고정된 포맷인 (offset, length)로 표현하고, 실제 데이터는 고정 길이 field 뒤에 저장
• Null value는 null-value bitmap으로 표현

 

Variable-Length Records: Slotted Page Structure

• Slotted page header
  • free space의 끝: 레코드의 시작점
    • free space: 새로운 레코드가 삽입되는 공간
  • slot: 각 레코드의 위치와 크기
  • #Entries: block 내의 slot 개수
    • 레코드 수와는 다름
    • 레코드가 삭제되었을 때 slot을 유지하기 때문
    • 놀고 있는 slot은 새 레코드 삽입 시 다시 활용 가능함
• 레코드들은 물리적으로 인접하게 붙어있고, 중간 레코드가 삭제되면 왼쪽의 레코드들이 움직여 빈공간을 메움. 그리고 헤더의 slot을 업데이트
• 위와 같이 레코드의 위치가 바뀔 수 있기 때문에 블록 외부의 포인터들은 헤더에 있는 slot을 통해 레코드에 접근해야함
• 설계를 어떻게 하냐에 따라서 헤더에 있는 항목이 바뀔 수 있음

 

Storing Large Objects

• 용량이 큰 objects들을 db에 어떻게 저장할까?
  • e.g. blob/clob types
    • blob: binary large object
    • clob: character large object
    • 이미지, 비디오, 오디오 등을 저장할 때 이용
• 레코드들을 page보다 작아야 함
• 방법
  • opt1: lob을 파일 시스템의 파일에 저장
    • lob의 attribute들은 파일에 대한 포인터와 경로명을 활용해 접근 가능하도록 함
  • opt2: lob를 db에 의해 관리받는 파일로 저장
    • db에 의해 관리가 되지 않으면, 검색을 할 때 데이터가 사라져 있는 문제가 발생할 수 있음. 파일 시스템에서 함부로 삭제할 수 없게 하는 제약 필요
  • opt3: lob를 여러 조각으로 나누고 각각을 tuple로 저장

---

Organization of Records in Files

• Heap: 순서 상관없이 레코드를 빈 공간에 저장
• Sequential: 레코드들에 순서 부여
  • 정렬의 기준이 각 레코드들의 탐색 키가 될 수 있음
• multi-table clustering file organization: 여러 테이블의 레코드들을 한 파일에 같이 저장
  • disk IO를 감소시켜 성능 향상에 도움이 됨
• B+ tree file organization: 제일 많이 쓰는 방법
• Hashing

 

Heap File Organization

• 순서 상관없이 빈 공간에 저장
• 레코드들은 한 번 할당되면 block 내에서 잘 움직이지 않음
• 빈 공간의 위치를 빠르게 찾는 것이 중요!
  •  Free-space map 이용
• Free-space map
  • block 당 빈 공간이 어느정도 있는지 나타내는 array
  • 한 block 당 array entry 하나를 차지
  • (array entry)/n 
    
    • e.g. n=3, array = [4,2,1,4,7,3,6,5,1,2,0,1,1,0,5,6]
      • n: block 당 3 bits
      • array[0] = 4/8 → 이 block에 최소한 4/8 만큼의 빈공간이 존재한다는 의미
  • secondary free-space map을 가질 수 있음
    • e.g. secondary_array = [4,7,2,6]
      • array의 entry를 4개씩 묶어서 최댓값 표현 

 

Sequential File Organization

• 레코드들 간 순서 존재
  • 순차적인 연산이 많이 발생하는 경우에 유리
• 삭제: pointer chain을 사용, linked list 삭제 방법과 유사
• 삽입
  • 레코드가 삽입될 위치 지정
  • 빈 공간이 충분하면, 삽입 후 링크 업데이트
  • 빈 공간이 부족하면, overflow block에 먼저 저장 후 링크 업데이트
• 주기적으로 파일구조를 순서에 맞게 재구성해줘야함

 

Multi-table Clustering File Organization

• 서로 다른 테이블을 동일한 파일에 저장
• 가변길이 레코드를 결과로 함
• join 연산을 수행한 결과를 저장하는 효과를 낼 수 있음
  • join 연산과 관련한 질의문이 많이 쓰일 때 유리 
• 아래의 예시
  • good: 교수 테이블과 학과 테이블에 대한 자연조인, 한 학과에 대한 교수를 찾는 질의
  • bad: 학과만을 다루는 질의
• 특정한 레코드에만 접근을 지원하기 위한 pointer chain을 더할 수 있음

---

Data Dictionary Storage

• Data Dictionary (or system catalog): metadata를 저장
  • 테이블 정보
    • 테이블 이름
    • field 이름, type, length
    • db의 가상테이블 이름, 정의
    • 무결성 제약조건
      • db의 정확성, 일관성을 보장하기 위해 저장, 삭제, 수정 등을 제약하기 위한 조건
  • 사용자 정보
  • 통계 데이터
    • 테이블 별 레코드 수
  • 물리적 파일 저장 구조
    • 테이블이 어느 파일 구조로 저장되어 있는지
      • sequential/heap/...
    • 테이블의 물리적 위치
  • 인덱스 정보

 

Relational Representation of System Metadata

• system metadata를 disk에 일반 테이블로 저장
• 레코드에 접근하기 전에 메타데이터에 먼저 접근함

---

Storage Access

• Block: 디스크와 버퍼 사이의 data 입출력 단위
• db 시스템은 block transfer의 횟수를 최소화하는 것을 추구
  • 버퍼 (in 메인메모리) 에 최대한 많은 block을 보유하고 있으면 됨
• buffer: disk block의 복사본이 저장되는 공간, 메인 메모리에 위치
• buffer manager: 버퍼 공간 관리

 

Buffer Manager

• 응용 프로그램이 disk로부터 한 block을 요청할 때,
• buffer manager는 버퍼에 해당 block이 있는지 check
  • cache hit: block address를 넘겨줘서 접근할 수 있도록 함
  • cache miss: 버퍼에 공간을 마련
    
    • victim 선택: 이미 있던 block 중 하나를 내보내야 함
    • victim이 수정된 값이라면 disk로 write 후 버림
• Buffer Replacement Strategy
  • LRU(least recently used): 마지막 접근이 제일 오래된 순으로 out, os에서 주로 사용
    • db에 적용할 때는 좋지 않을 수 있음
      • e.g. 중첩 루프: inner loop의 첫 부분들이 대체가 되어, outer loop가 바뀌면 다시 불러와야 함
  • Toss-immediate startegy
    • 이 block 처리하고 나면 한동안은 안보게찌..?
    • block의 마지막 레코드 접근이 끝나자마자 그 block이 차지하고 있는 buffer 공간을 비움
  • MRU(most recently used): 가장 최근에 접근한 친구 out
• Pinned block
  • Pin: 특정 페이지를 버퍼 내에서 고정시킴
    • 버퍼 매니저가 해당 페이지를 디스크로 out 시키거나, victim으로 선택하는 것을 막음
  • Unpin: read/write 작업 완료 후 pin 제거
• Shared and exclusive locks on buffer
  • 데이터의 concurrenency 유지를 위함
  • reader: shared lock을 얻음
  • write를 하려면 exclusive lock을 필요로 함
  • Locking rules
    • 한 번에 한 프로세스만 exclusive lock을 얻을 수 있음
    • shared lock은 exclusive lock과 동시에 걸릴 수 없음
    • shared lock은 여러 프로세스에게 동시에 부여될 수 있음