[DataBase] Data Storage Structures

https://www.db-book.com/

Database System Concepts - 7th edition

< 인터넷에 제공되어있는 Avi Silberschatz 외 2인, Database System Concepts - 7th edition, McGraw-Hill, 2019 에 관한 자료를 참조 >

 

 

 

Goal

 데이터가 어떻게 저장되고 접근가능한지 그 구조를 살펴볼 것이다.

 

 

Index

• File Organization
• Organization of Records in Files
• Data-Dictionary Storage
• Database Buffer
• Column-Oriented Storage

 

 

File Organization

 데이터베이스는 파일들의 집합으로 구성되어있다.

Database <- File <- Record <- Field

• 각 파일은 일련의 레코드로 구성되어있다.
  • 레코드는 일련의 필드로 구성되어있다.
• 각 파일은 fixed-length storage units, 고정길이 저장단위를 가지고 있다. 이는 Block이라 한다.
  • block은 여러 레코드를 포함할 수 있다.

 

레코드의 저장방식

• 레코드의 크기는 고정되어있다고 가정하자.
• 각 파일은 하나의 특정한 타입만 저장가능하다.
• 각 파일은 각기 다른 릴레이션으로 저장된다.
• 레코드는 디스크 블록보다 클 수 없다.

 

 

Fixed Length Record

• 각 레코드의 사이즈가 n이라 할 때, i번째 레코드는 byte n*(i-1)에서 시작하는 범위에 저장된다.
• 레코드 접근은 쉬우나, 레코드가 블록의 크기를 넘어설 때 여러 블록에 걸쳐서 저장될 위험이 있다.
  • 이는 블록 경계를 넘어서 저장하지 않도록 제약을 걸어놓아서 해결할 수 있다.
• 레코드 i 의 삭제
  • i-th record를 삭제한 후, i+1, ..., n 번째 레코드를 i, ... , n-1번째 위치로 옮긴다.
  • 혹은 n번째 record를 i번째 위치로 옮긴다.
  • 삭제후 레코드의 움직임 없이 free list에 빈 공간을 link한다.
    • free list는 각 파일에서 빈 레코드들을 묶어놓은 리스트이다. 헤더는 파일의 맨 위에 위치.

 

 

Variable-Length Records

 가변 길이 레코드 방식

• 고정길이 레코드는 하나의 레코드 타입만 저장하는데, 가변길이 레코드는 다양한 타입에 관한 저장이 가능하다.
• varchar같은 type을 사용하여 가변길이 레코드를 다룬다.
• 이러한 레코드는 반복적인 필드도 허용한다.

 

가변 길이 레코드 방식의 스키마

 

• 맨 앞에 이후 나올 가변길이 레코드들의 위치와 크기가 저장된 (offset, length)이 존재한다.
• 이후에 고정길이 타입의 속성들이 존재한다.
• 이후 null bitmap이,
  • null bitmap의 구조는 다음과 같다.
    • 첫 번째와 세 번째 가변길이 레코드가 null이면 0101을 저장
    • 첫 번째가 null 이면 0001을 저장, 이런 방식이다.
• 이후 가변길이 레코드 들이 존재한다.

 

 

 

 

Slotted Page Structure

 여기서 Page는 블록과 같은 의미로 사용된다.

• Block Header
  • 레코드 개체의 수
  • 블록 속 빈공간의 마지막 주소를 가리키는 포인터
  • 각 레코드의 위치와 크기 정보를 가지고있다.

 

 

 

Organization of Records in Files

 File에 record를 구성하는 방법이다.

 

• Heap
  • 힙 구조를 이용한다. 레코드에 순서가 없고 각 릴레이션은 하나의 파일과 파일 집합으로 이루어져 있다.
• Sequential
  • 연속적인 순서로 자료를 저장한다. 각 레코드의 Search key 값에 기반해있다.
• Multi-table clustering file organization
  • 여러 다른 릴레이션의 레코드들이 한 파일이 같이 저장되어있다.
  • I/O 연산을 최소화 하기 위하여 같은 블록에 연관된 레코드들을 저장한다.
• B+ tree file organization
  • CH14에서 추가로 배운다
• Hashing
  • search key에서 계산된 해시함수를 이용. 해시 자료구조의 저장방법을 이용.

 

 

 

 

Sequential File Organization

• 파일의 순차적 처리에 유리하다.
• 파일 속 레코드는 search-key, 즉 탐색 키에 의해 정렬되어있다.

 

• 삭제
  • pointer chain을 이용한다.
• 삽입
  • 삽입할 position에 위치하 뒤 레코드를 삽입한다.
  • 이 position에 빈공 간이 없을 때 overflow block(확장된 블록)에 record를 삽입한다.
  • 두 개의 경우 모두 pointer chain이 업데이트되어야 한다.
• pointer chian은 각레코드들이 다음 레코드와 연결짓는 부분을 의미한다.

 

 

Multitable Clustering File Organization

• 해당 파일구조에 담긴 관련 릴레이션들의 조인연산에 효율적이다.
• 단일 릴레이션만 사용한 연산에서는 비효율적이다.

 

 

 

Data-Dictionary Storage

 System catalog, 시스템 카탈로그라고도 불린다. 이는 데이터를 설명하는 데이터, metadata(;메타데이터)이다.

 

• 릴레이션들의 이름
• 각 릴레이션의 속성들의 이름, 자료형, 길이
• 뷰의 정의와 이름
• 무결성 제약
• 통계적 데이터
• 물리적 구조 정보
• 인덱스에 대한 정보

등을 담고 있다.

 

 

 

Database Buffer

 데이터베이스는 디스크와 메모리 간 블록 전송 횟수를 최소화 해야한다. 그래야 효율이 좋다.

많은 블록을 메인 메모리에 위치시킴으로서 디스크에 접근하는 횟수를 줄일 수 있다.

이때 메인 메모리에 어떤 블록이 얼마나 있어야 하는지를 Database Buffer manager가 관리를 하고,

메인 메모리에서 disk block을 위해 사용하는 부분을 Buffer라고 한다.

 

 

Buffer-Replacement Policies

 버퍼에 빈 공간이 없을 때 버퍼 교체전략을 설명하고 있다.

 

• LRU strategy - least recently used
  • 대부분의 운영체제가 LRU  최근에 가장 적게 참여한 블록을 교체하는 방식으로 사용한다.
• Toss - immediate strategy
  • 한 블록의 마지막 튜플이 처리가 완료되자마자 해당 블록을 버퍼에서 내보낸다.
• MRU strategy - Most recently used
  • 최근에 가장 많이 사용된 블록을 버퍼에서 내보낸다. pinned 처리하면 안내보낼 수 있다.

 

Column-Oriented Storage

 열 지향 저장공간이다. 같은 속성의 데이터들을 빠르게 처리할 수 있다는 장점이 있어 빅 데이터 처리에 유리하다.

 

기존에 튜플 당, 레코드 당 처리하는 방식이 row-oriented, 행 기준이었다면 이는 열 기준으로 바뀐 것이다.

속성별로 저장을 하기에,

• 동일한 속성들에 대한 접근 I/O 시간을 줄여준다.
• CPU cache 성능을 향상시켜준다.
• 압축성능을 향상시켜준다.
• 최근 CPU architecture에 Vector processing, 벡터 처리가 가능하다.
  • 병렬 처리가 가능하다는 의미이며, 따라서 빅 데이터 처리에 유용하다.

그러나 이에 상응하는 Drawback도 존재하는데,

• 기존 튜플 관련 구조에서 열 지향 구조로 재구성하는데 드는 비용 
• 튜플 삭제와 업데이트 비용
• 압축 해제 비용

이다.