[DataBase System] ch10 - 데이터베이스 저장과 접근

[DataBase System] ch10 - 데이터베이스 저장과 접근

 

책정보, 데이터베이스 시스템 : 네이버 책 (naver.com)

데이타베이스 시스템 : 네이버 도서

 

문제 풀이

 

1 ) 디스크에 저장되어 있는 데이터를 접근할 때 접근 시간은 어떤 요소로 구성되는지 설명하라

 

• 접근 시간 = 탐구 시간 +  회전 지연 시간 + 실제 데이터 전송 시간

 

• 탐구시간
  • 헤드가 판독이나 기록할 데이터가 있는 트랙(실린더)까지 이동하는 데 걸리는 시간
• 회전 지연 시간
  • 트랙에서 원하는 레코드가 회전하여 헤드 밑에 까지 올 때의 대기 시간
• 실제 데이터 전송 시간

---

2 ) 저장 데이터베이스의 일반적인 접근 과정을 단계별로 설명하라

 

1. 사용자가 요구하는 레코드가 어떤 저장 레코드인지 결정해서 파일관리자에게 해당 레코드의 검색을 요청한다
2. 파일관리자는 DBMS가 원하는 저장 레코드가 어떤 Page에 저장되어 있는가를 결정해서 디스크 관리자에게 해당 페이지를 요청
   1. 디스크와 메인 메모리 사이에 한 번의 디스크 접근으로 데이터가 전송되는 양을 말함
3. 디스크 관리자는 화일 관리자가 원하는 페이지의 물리적 위치를 알아내서 그 페이지 전송에 필요한 디스크 입출력 명령을 내림
   1. 경우에 따라서 이 페이지가 다른 목적으로 먼저 수행된 명령에 의해 이미 메모리의 버퍼에 거주하고 있을 수도 있는데 이때는 다시 전송할 필요 없음

 

---

3 ) 디스크 관리자의 기능과 화일 관리자의 기능을 설명하고, 이들 간의 관계를 설명하라

 

• 디스크 관리자 - disk manager
  • 운영체제의 한 구성요소
  • 모든 물리적 입출력 연산에 대한 책임을 지고 있다
  • 물리적 디스크 주소에 대해 알고 있어야 한다.
• 파일 관리자 - file manager
  • 디스크 관리자를 이용해서 DBMS가 디스크에 저장된 저장 데이터베이스를 저장 파일들의 집합으로 취급할 수 있도록 지원
  • 하나의 저장화일은 한 레코드 타이비의 저장레코드 어커런스들의 집합을 의미
• 관계
  • 파일 관리자가 페이지를 요구하면 디스크 관리자는 해당 페이지가 어디에 존재하는지 알아야 함
  • 다만 이때 파일 관리자는 명령을 하는 존재기에 해당 파일의 물리적 위치가 어디인지는 몰라도 된다.
  • 파일 관리자는 디스크를 단순히 일정한 크기의 페이지로 구성된 페이지 세트들의 논리적 집합으로 취급

---

4 ) 데이터 밀집이 데이터 접근에 어떻게 영향을 주는 지를 설명하라

 

•  서로 관련이 된 데이터는 동시에 함께 사용되기에 보통 물리적으로도 디스크 상에 가까이 저장시키는 것을 의미
• 연속해서 읽을 두 레코드가 같은 페이지에 존재 시 첫 번째 레코드에 접근할 때 두 번째 레코드도 주기억장치의 버퍼로 올라가 있음
• 연속해서 읽을 두 레코드가 물리적으로 가까운 두 페이지에 있다면 두 번째 레코드를 접근하기 위해 별도의 물리적 입입출력이 필요하지만 이에 수반되는 탐구 시간은 아주 작을 것

---

5 ) 레코드 ID는 무엇이며 효율적 구현 방법을 설명하고 그 이점을 설명해 보라

 

• 파일 관리자가 다루는 저장 레코드들을 내부적으로 식별하는 식별자 역할
• 레코드 ID는 페이지 번호와 그 페이지 내의 유일한 값인 오프셋, 슬롯 번호로 구성되어 있음

---

6 ) 디스크 디렉터리를 설명하고 어떻게 활용되는가를 설명하라

• 디스크에 있는 모든 페이지 세트 리스트와 페이지 세트의 첫 페이지에 대한 포인터가 저장되어 있는 시스템 파일
• 보통 지정된 페이지(실린더 0, 트랙 0)에 위치

---

7 ) 디스크를 페이지 단위로 나누어 레코드를 저장할 때 페이지 구조, 페이지 관리 방식과 레코드 검색에 대해 설명하라

 

페이지 : 디스크와 메인 메모리 사이에 데이터를 전송하는 단위

• 페이지 구조 
  • 헤더와 바디로 나눠짐
    • 헤더 
      • 페이지 번호, 페이지 크기, 레코드 수 등의 정보 저장
    • 바디
      • 실제 레코드들이 저장
      • 레코드는 고정 길이 또는 가변 길이일 수 있으며 페이지 내에 연속 배치
• 페이지 관리 기법
  • 연속 할당
    • 파일의 모든 페이지를 디스크의 연속적인 공간에 할당
    • 디스크 접근 시간을 줄일 수 있지만 외부 단편화 문제 발생 가능
  • 연결 할당
    • 파일의 각 페이지에 다음 페이지의 주소를 저장하여 링크드 리스트 형태로 연결
    • 외부 단편화 문제를 해결하지만 임의 접근이 어렵고 오버헤드 발생할 수 있음
  • 색인 할당
    • 파일의 각 페이지의 주소를 별도의 색인 블록에 저장하여 관리하는 방식
    • 임의 접근 용이
    • 외부 단편화 문제 해결
    • 색인 블록 유지를 위한 추가적인 공간과 시간 필요
• 레코드의 검색
  • 디스크에서 원하는 레코드를 찾아내는 과정
  • 해당 레코드가 속한 파일을 식별하고, 그 파일의 페이지들을 디스크에서 메인 메모리로 전송, 그중에서 원하는 레코드를 선택하는 방식
  • 해당 과정에서 파일 시스템이나 DBMS가 제공하는 인덱스나 해시 테이블과 같은 보조 자료구조를 활용하여 효율적 레코드 검색 가능

---

8 ) 키 순차 파일과 파일의 차이점을 설명하라

• 키 순차 화일
  • 래코드들의 키 값의 크기 순으로 만들어짐
• 파일
  • 레코드들이 시스템에 삽입되는 순서대로 만들어짐

---

9 ) B - 트리의 특성을 설명하고 레코드의 삽입과 삭제에 대해 그 과정을 설명하라

• 이진트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조
• 모든 리프 노드가 같은 높이에 존재
• 노드의 자식 수와 키 수가 일정한 범위 내에 존재
• 정렬된 데이터를 유지하고 검색, 순차 접근, 삽입, 삭제를 log(n)에 수행
• 디스크와 같은 보조 저장 장치에서 효율적 입출력을 위해 고안

 

• 삽입
  • 루트 노드에서 시작하여 탐색하여 삽입을 할 위치 찾기
  • 해당 위치는 리프노드이며, 삽입할 키 값은 오름차순
  • 삽입할 위치의 노드가 키 값이 가득 차 있다면, 즉 최대 키 값의 개수인 U-1개를 가지고 있다면, 해당 노드를 분할
    • U-1개의 키값을 오름차순으로 정렬, 중간 위치의 키 값을 부모 노드로 올림
    • 중간 위치보다 작은 키 값들은 오른쪽 자식 노드로 분배
    • 삽입하려는 키 값은 분배된 자식 노드 중 알맞은 위치에 삽입
    • 부모 노드로 올라간 키 값은 부모 노드의 기존 키 값들과 오름차순으로 정렬
    • 부모 노드도 가득 차 있으면 부모 노드도 분할
    • 만약 루트 노드가 분할 시, 새로운 루트 노드 생성
• 삭제
  • 루트 노드에서 시작하여 탐색을 하면서 삭제 위치 찾기
  • 삭제할 위치는 리프 노드이며, 삭제 후에도 최소 키값의 개수인 L-1개 유지
  • 만약 삭제 후에도 최소 키 값의 개수를 유지한다면 삭제 과정 종료
  • 최소 키 값의 개수보다 작아지면 노드를 재구성
    • 형제 노드 중에서 최소 키 값의 개수보다 많은 키 값을 가지고 있는 경우가 있다면, 부모 노드에서 하나의 키 값을 내려받고, 형제 노드에서 하나의 키 값을 올려줌
      • 부모와 형제 사이에 있는 자식 포인터도 함께 조정
    • 형제 노드 중에서 모두 최소 키 값의 개수만큼 가지고 있는 경우가 있다면, 부모 노드에서 하나의 키 값을 내려받고, 형제노드와 합치기
      • 부모와 형제 사이에 있는 자식 포인터도 함께 합침
    • 부모 노드로부터 내려받은 키 값이 최소 키 값의 개수보다 작아지면 부모 노드도 재구성
    • 부모 노드가 없어지면, 즉 합친 자식 노드가 유일한 자식이 되면 그 자식 노드가 새로운 루트가 됨

 

---

10 ) B+ - 트리의 특성을 설명하고 B-트리와이 차이점을 설명하라

• 루트는 0이거나 2에서 m개의 서브트리를 가짐
• 루트와 리프를 제외한 모든 내부 노드는 최소 [m/2] 개, 최대 m개의 서브트리를 갖는다
• 리프가 아닌 노드에 있는 키 값의 수는 그 노드의 서브트리 수보다 하나 적다
• 모든 리프 노드는 같은 레벨에 존재
• 한 노드 안에 있는 키 값들은 오름차순으로 저장

B+ 트리는 B-트리의 변형이다. 

• B+트리는 데이터와 키를 리프 노드에만 저장하고 내부 노드에는 키만 저장
• B+트리는 리프노드를 링크드 리스트로 연결하여 순차 접근을 용이하게 함
• B+트리는 디스크와 같은 보조 저장 장치에서 데이터베이스나 파일 시스템의 인덱스를 관리하는데 용이하다.

---

11 )  버킷 해싱을 설명하고 오버플로 처리 방법을 설명하라

• 해싱 함수가 레코드의 키 값으로부터 그 레코드가 저장되어 있는 버킷주소로 해싱하는 것을 의미
• 버킷은 M/B개의 슬롯으로 구성되며, 해시 함수는 각 레코드를 버킷의 첫 번째 슬롯에 할당
• 버킷 
  • 하나의 주소를 가지고 있으면서 하나 이상의 레코드를 저장 가능한 파일의 한 구역
  • 충돌
    • 해시 키와 버킷 주소 간의 사상은 보통 다대일의 관계가 되기에 서로 다른 레코드들이 같은 주소로 사상되는 경우 존재
    • 해싱 함수에 의해 같은 주소로 변환된 모든 레코드들을 동거자라고 함
• 해당 버킷이 다 차는 경우 오버플로가 생김, 즉 빈 공간이 존재하지 않기에 생기는 문제
  • 선형 탐사
    • 해시 함수가 계산한 슬롯부터 시작하여 순차적으로 빈 슬롯 찾기
  • 제곱 탐사
    • 해시함수가 계산한 슬롯에서 제곱함수 적용으로 빈 슬롯 찾기
  • 랜덤 탐사
    • 해시함수가 계산한 슬롯에서 랜덤 수를 +-하여 빈 슬롯 찾기
  • 체이닝
    • 각 슬롯의 연결리스트나 배열과 같은 자료구조를 사용하여 여러 레코드 저장

---

12 ) 확장성 해싱 기법을 설명하고, 충돌을 해결하는 방법에는 어떤 것이 있는지 설명하라

• 디텍 터리와 버킷 집합을 사용
• 해시 테이블의 크기를 동적으로 조절
• 접근 구조와 파일을 분리하여 저장
  • 접근 구조
    • 디렉터리와 버킷으로 구성
• 해시 함수의 일부 비트를 사용하여 레코드를 버킷에 할당하며, 버킷이 가득 차면 디렉터리와 버킷 확장
• 버킷 해싱과 마찬가지로 충돌 존재
  • 개방 주소법
    • 충돌이 발생하면 다른 슬롯을 탐색하여 빈슬롯 찾기
  • 분리 연결법
    • 각 슬롯에 연결 리스트나 배열과 같은 자료구조를 사용하여 여러 레코드 저장