물리적 설계

논리적 스키마를 이용하여 효율적인 물리적 데이터베이스를 구성한다.



물리적 데이터베이스는:

저장 레코드의 형식, 저장 순서, 접근 경로, 물리적 저장 장치 할당 등에 대한 내역



파일 구성



데이터베이스는 여러 개의 파일로 저장되고, 파일은 여러개의 레코드를 저장, 레코드는 여러개의 필드로 구성된다.

DB-파일-레코드-필드



레코드 표현 방법

1. 고정 길이 레코드

모든 레코드의 길이를 동일하게 한다. 구현이 용이하다.

이 때, i번째 레코드가 삭제되는 경우

- 아래 레코드를 한칸씩 위로 이동

- 마지막 레코드를 i번째로 이동

- Free list로 연결(파일 헤더에 첫번째 삭제 레코드 주소를 저장하고, 삭제된 레코드들을 연결 리스트로..)

등 방법으로 구현할 수 있다.



2. 가변 길이 레코드

한 파일에 다양한 타입의 레코드를 저장하거나 레코드가 varchar타입 필드를 가지는 경우, 레코드에 배열 타입 필드가 있는 경우 가변 길이 레코드 표현이 필요하다.



가변 길이 레코드를 표현하는 하나의 방법을 소개하자면...

필드의 순서는 고정,

가변 필드 위치에 (offset, length) 정보만 저장하고, 실제 데이터는 offset 위치에 저장한다.

-> 이 방법은 속성 수가 고정됨





파일에서 레코드 저장 방법

1. 순차 파일 구성

:레코드를 키 순서대로 정렬(연결리스트)



2. 다중-테이블 클러스터링 파일 구성

: 여러개의 릴레이션을 한 파일에 같이 저장

조인 성능 효과적이지만 가변 길이 레코드 처리가 복잡함



접근 방법 설계



접근 방법: 저장 장치에 자료를 저장하거나 검색하는 방법.

저장 구조와 검색 기법으로 구성



인덱스

주로 B+트리로 구현되고, 자주 검색되는 필드에 인덱스를 생성하면 검색이 빨라짐. 특정 키 범위 검색 가능

유일인덱스와 보조인덱스가 있음(키 값 중복 허용 여부)



해싱은 구간검색 불가능



클러스터링

연관된 레코드를 물리적으로 인접한 공간에 저장함.



Clustered Index

데이터 레코드의 저장 순서와 인덱스 내의 순서가 동일한 경우

하나의 테이블에는 하나의 clustered index만 존재함.



(index 구조)

B트리



사실상 업계 표준임.

각 노드는 최대 m개의 자식을 가질 수 있고, 루트와 리프를 제외한 모든 노드는 m/2개의 자식이 있어야함.

리프가 아닌 루트는 적어도 2개의 자식이 있어야 한다.

모든 리프 노드들은 동일한 level

리프가 아닌 노드가 k개의 자식을 가질 경우, 그 노드는 k-1개의 key를 가져야 함

각 노드에서 key들은 순서대로 정렬되어야 함





B*트리

한쪽 자매가 full이 될 때 까지 재분배

루트를 제외한 모든 노드들은 2m-1/3개의 자식이 있어야함. 





B+트리

index set: 리프 노드가 아닌 노드들은 데이터를 가지고 있지 않으며 리프노드까지의 경로만 제공

순차 set: 리프노드. 데이터 주소를 포함하고 있으며 인접한 리프 노드간 연결 리스트로 구성되어 순차검색 용이



각 노드는 최대 m개의 자식,

루트와 리프를 제외한 모든 노드는 적어도 m/2개의 자식 필요

리프가 아닌 루트는 적어도 2개의 자식

모든 리프는 동일한 레벨





해시와 B트리 비교

equals는 해싱이 빠르고 구간검색은 B+트리가 빠름



보조 인덱스

키의 중복이 가능



중복 키의 저장 방법-

1. 역 인덱스

: 보조 인덱스를 array구조로 구현. 

새로운 record 첨가 시 array에 포함시킴

가변길이 레코드



2. 다중 리스트

: 보조 키에 대한 다중 리스트 인덱스 파일 + 데이터 파일

링크드 리스트

논리적 스키마와 물리적 데이터베이스 구성

논리적 스키마는 데이터베이스의 구조를 정의합니다. 이는 데이터와 관계, 제약 조건을 포함하지만, 이 데이터가 어떻게 저장되는지에 대해서는 묵시적입니다. 반면에, 물리적 데이터베이스 구성은 이러한 논리적 스키마에 기반하여 실제 데이터의 저장 방식을 정의합니다. 여기에는 레코드의 형식, 저장 순서, 접근 경로, 물리적 저장 장치의 할당 등이 포함됩니다.

파일 구성 및 데이터 저장

데이터베이스는 여러 파일로 구성되며, 각 파일은 다수의 레코드를 저장합니다. 레코드는 다시 여러 필드로 구성됩니다. 이 구조는 DB-파일-레코드-필드로 나타낼 수 있습니다.

레코드 표현 방법

1. 고정 길이 레코드: 모든 레코드가 동일한 길이를 가집니다. 이는 구현이 쉽지만, 공간 효율성이 낮을 수 있습니다. 삭제된 레코드는 여러 방법으로 관리할 수 있습니다.
   • 아래 레코드를 한 칸씩 위로 이동
   • 마지막 레코드를 삭제된 위치로 이동
   • 삭제된 레코드를 Free list로 관리
2. 가변 길이 레코드: 다양한 타입의 레코드를 저장하거나, VARCHAR 타입의 필드를 포함할 경우 사용됩니다. 가변 필드의 위치는 (offset, length) 정보로 저장되며, 실제 데이터는 offset 위치에 저장됩니다.

파일에서 레코드 저장 방법

1. 순차 파일 구성: 레코드를 키 순서대로 정렬하여 저장합니다. 보통 연결 리스트 형태를 띱니다.
2. 다중-테이블 클러스터링 파일 구성: 여러 릴레이션(테이블)을 한 파일에 저장합니다. 이 방식은 조인 연산의 성능을 향상시킬 수 있지만, 가변 길이 레코드 처리가 복잡해질 수 있습니다.

접근 방법 설계

접근 방법은 데이터 저장 및 검색 방식을 정의합니다. 이는 저장 구조와 검색 기법으로 구분됩니다.

인덱스

• B+트리: 주로 B+트리로 구현되며, 자주 검색되는 필드에 적용됩니다. 특정 키 범위 검색이 가능합니다.
• 유일 인덱스와 보조 인덱스: 키 값의 중복 여부에 따라 구분됩니다.

해싱과 B트리의 비교

• 해싱: 'equals' 검색에 유리하지만, 구간 검색은 불가능합니다.
• B+트리: 구간 검색에 유리합니다.

클러스터링

• Clustered Index: 데이터 레코드의 저장 순서가 인덱스 내 순서와 일치합니다. 하나의 테이블에는 하나의 클러스터드 인덱스만 존재할 수 있습니다.

보조 인덱

스

• 중복 키 허용, 다양한 구현 방식(역 인덱스, 다중 리스트)이 존재합니다.

B트리와 B+트리

• B트리: 각 노드는 최대 m개의 자식을 가지며, 리프 노드들은 동일한 레벨에 있어야 합니다.
• B+트리: 리프 노드가 아닌 노드는 데이터를 가지지 않고, 리프 노드까지의 경로만 제공합니다. 순차 검색에 유리합니다.