Chapter 10 데이터베이스 저장구조

데이터베이스의 성능

• 일반적으로 데이터베이스는 디스크에 저장됨
• 데이터베이스의 성능은 디스크 입출력(Disk Input/Output)의 효율성에 달려 있음
  • 디스크 접근 속도: 수십 miliseconds
  • 메인 메모리 접근 속도: 수십 nanoseconds
• 데이터베이스 성능 → 디스크 입출력 최소화

 

하드 디스크

임의 접근(Random Access) 가능

 

디스크의 구조

블록(Block, 디스크 IO의 단위)은 섹터들로 구성

강의 자료 참고

 

디스크 접근시간

• 디스크 접근 → 원하는 면, 원하는 트랙, 원하는 섹터
• 접근시간(Access Time)
  • 탐구 시간(Seek Time): 원하는  트랙까지 헤드를 움직이는 데 소요되는 시간
  • 회전 지연 시간(Rotational Delay): 원하는 섹터까지 회전되는 데 소요되는 시간
    • 디스크 회전 속도와 관계
  • 전송 시간(Tranfer Time): 섹터들을 읽고 메모리로 전송되는 데 소요되는 시간

 

DBMS에서 데이터가 접근되는 과정

강의 자료 참고

디스크 관리자의 페이지 버퍼(Page Buffer, 페이지 캐시)는 원하는 페이지가 캐싱되어 있으면 바로 반환한다.

 

입출력 관련 주요 모듈

• 디스크 관리자(Disk Manager)
  • 디스크는 페이지들의 집합
  • 페이지에 대해서는 Page ID를 부여
  • 페이지의 할당과 반환을 관리
    • 자유공간 페이지 세트(free space page set) 정보 관리
• 파일 관리자(File Manager)
  • 파일(SQL에서의 테이블)의 할당과 레코드 단위의 IO를 수행
  • 각각의 레코드에는 Record ID(RID)를 부여
    • Page ID + Slot #

 

데이터베이스 예시

강의 자료 참고

포인터를 이용한 파일 구분

디스크 디렉토리(페이지 0번)

페이지 내 레코드 배치 방법: 레코드 ID를 사용한 방법

 

파일 종류(파일 조직 방법)

강의 자료 참고

• 엔트리 순차 파일(Entry Sequence File, Pile): 입력된 순서대로 레코드 저장
• 키 순차 파일(Key Sequence File): 레코드의 키값 순서대로 정렬하려 저장
• 인덱스 파일(Index File): 인덱스 부분과 데이터 부분으로 구성
  • 인덱스 부분만 sorting하므로 키 순차 파일보다는 빠름
  • 검색할 때는 빠르지만 추가/삭제는 느림. 인덱스도 추가/삭제해야 하기 때문.
• 역 파일(Inverted File): 모든 데이터에 대해 인덱스를 달아줌.
  • DB에서 잘 사용하지 않음
  • Full-text 검색에 사용
• 다중리스트 파일(Multi-list File): 인덱스가 첫 번째 데이터의 포인터만 가짐

 

B-트리 인덱스 소개

• DBMS에서 가장 널리 사용되는 인덱스 구조
• 트리의 루트에서부터 단말까지의 모든 경로(높이)는 일정함(Balanced Tree)
  • 단말 노드(leaf node): 트리의 맨 아래 노드로서 자식이 없음
  • 내부 노드(internal node, non-leaf node): 단말이 아닌 노드로서 자식을 가진 노드
• 유사한 구조의 인덱스
  • B+트리 인덱스
  • B*트리 인덱스
• 3차 B-트리 예: 강의 자료 참고

B-트리 특징

• 차수가 m인 B-트리는
  • 최대 m개의 자식 노드를 가질 수 있다.
    • 최대 m개의 포인터를 가질 수 있다.
    • m-원 탐색 트리(m-way search tree)
  • 루트를 제외한 모든 노드는 최소 m/2개 이상의 자식 노드를 갖는다.
  • 루트는 자신이 단말 노드가 되는 경우를 제외하면 적어도 2개 이상의 자식 노드를 갖는다.
  • k개의 자식 노드를 갖는 내부노드는 k-1개의 키 값을 갖는다.

내부 노드 구조

강의 자료 참고

• 노드 내의 키 값들은 오름차순을 유지
• P(i)가 가리키는 노드 내의 키 값은 모두 K(i+1)보다 작다.
• P(i)가 가리키는 노드 내의 키 값을 모두 K(i)보다 크다.

단말 노드 구조

강의 자료 참고

 

B-트리 검색

• 특정 키 값에 대한 검색
• 키 값에 대한 순차 검색
  • 트리에 대한 중위 순회(inorder traversal)

삽입/삭제 예시

강의 자료 참고

 

B+-트리

• 내부 노드는 데이터레코드에 대한 포인터를 가지지 않음
  • 모든 검색은 단말 노드까지 탐색해야 가능
  • 내부 노드는 탐색 경로만을 알려주는 역할
  • 내부 노드에 키 값은 단말 노드에 다시 나타나거나 나타나지 않을 수도 있음
• 단말 노드들은 포인터로 연결됨
  • 단말 노드들을 스캔하면 키 순서 대로 검색 가능
• 인덱스 키를 이용한 직접 접근 및 키 순서 탐색에 모두 사용 가능
• 내부 노드 구조: 강의 자료 참고
• 단말 노드 구조: 강의 자료 참고
• 삽입/삭제 예시: 강의 자료 참고

 

해싱(Hashing)

• 해시키 값으로부터 데이터 레코드를 바로 검색
• 해싱 함수(Hashing Function)
  • (해시 키) → (데이터 레코드의 위치) 매핑
  • 해시 함수 값이 같은 레코드들은 물리적으로 동일한 위치(버킷)에 위치시킴
• 해시 키(Hash Key) 또는 해시 필드(Hash Field)
  • 해시 값을 계산하기 위한 테이블 컬럼
  • 하나의 컬럼만이 해시 필드가 될 수 있음
    • 하나의 테이블에 대해 여러 개의 해싱을 사용하지는 않음

버킷 해싱(Bucket Hashing)

해시 충돌(collision)로 인한 동거자(synonyms)

강의 자료 참고

 

확장성 해싱

• 레코드의 개수가 늘어나더라도 오버플로우 버킷을 사용하지 않으므로 성능의 감소가 크지 않음
  • 동거자의 증가 → 버킷 분할

강의 자료 참고

 

버킷 분할

지역 깊이 증가: 강의 자료 참고

전역 깊이 증가: 강의 자료 참고

정확하게 하나의 값을 찾을 때는 인덱스보다 유리함