[데이터베이스] 데이터베이스 저장 및 인덱스

데이터베이스의 저장 장치

• 일반적으로 하드디스크(HDD, mechanic device), SSD(electronic device)에 저장함.

디스크 성능 결정의 주요 요소

• 디스크 I/O
  • 디스크 접근 횟수를 줄이기
  • disk access time 줄이기
• 디스크에 데이터를 배치하는 방식 ⇒ 파일 조직 방법

Disk Access Time

• disk access time = seek time + rotational delay + transfer time
  • seek time = 데이터가 있는 트랙을 찾아가는 시간
  • rotational delay = 데이터가 있는 섹터를 찾아가는 시간
  • transfer time = 디스크 헤드가 데이터를 읽어들이는 시간
• 하드 디스크는 mechanical device이므로, 트랙을 찾는 시간(seek time)이 가장 오래 걸림.
• 같은 플랫터 내에 있는 데이터는 동시에 읽을 수 없음
• 같은 실린더 내에 있는 데이터는 동시에 읽을 수 있음
  • DB 설계 예시) 두 개의 파일을 디스크에 기록하는 경우
    → 따로 write하면 서로 다른 실린더에 기록할 수 있음.
    → 동시에 write하면 fragmentation이 발생할 수 있음.
• 결론 : seek time이 가장 오래 걸리므로 seek time을 줄이는 방향으로 데이터를 배치해야 함.
  1. 같은 트랙 내에 데이터가 있도록 배치
  2. 같은 실린더에 데이터가 있도록 배치 → seek time이 0
     예시) ‘학생’ 테이블을 같은 실린더에 배치

파일 조직

1. 순차 방법 (heap file)

• 레코드들이 삽입된 순서대로 파일에 저장됨

삽입 : 새로운 레코드는 파일의 가장 끝에 삽입됨

• 중간에 삭제된 위치가 있다면 비어있는 위치에 삽입

삭제 : 삭제를 위해서는 검색이 선행됨

검색 : 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근

 

2. 인덱스 방법 (index file)

• 데이터 파일과 인덱스 파일로 구성
  • 데이터 파일 : 실제 레코드들을 저장하고 있는 heap file
  • 인덱스 파일 : 레코드들에 대한 포인터를 가지고 있는 파일
• B-트리 : 인덱스 파일을 구성하는 트리
  • B-트리에서의 삽입 시, 빈자리가 없을 경우 추가적으로 루트로 돌아가는 과정 (log n) 소요
  • 검색 후 루트로 돌아가는 worst case : 2(log n)
  • 중위순회를 하기 때문에 순차 탐색에 불리하다.
• B+트리 : B-트리 순차 탐색을 개선한 트리
  • 첫 리프노드부터 링크 타고 가면 순차탐색을 할 수 있음
  • 인덱스 세트와 순차 세트로 구성
  • 인덱스 세트 : 내부 노드, 리프의 키들에 대한 경로 제공 - 직접 탐색 지원
  • 순차 세트 : 리프 토드, 모든 키 값들을 포함 - 순차 탐색 지원
• B-트리와 B+트리의 차이점
  • B+ 트리의 인덱스 세트 키 값은 대부분 순차 세트에 다시 나타남
  • 노드에 저장할 수 있는 원소의 수가 서로 다름.
    • B-트리 : 최대 m/2개
    • B+트리 : 인덱스 - 1개, 리프 - m/2

3. 해싱 방법 (hash file)

• 확장성 해싱을 사용해서 충돌(collision) 문제 해결
  • collision은 버킷이 만원일 때 발생
  • 버킷을 분할하여 해결함
• 확장성 해싱
  • 모조키의 처음 d bit를 인덱스로 사용 → d는 global depth
  • 디렉토리(인덱스 헤더와 포인터들) : 디스크에 저장됨