데이터베이스

6. 물리적 데이터 구조

데이터베이스는 보통 저장장치에 저장된다.
여기선 하드디스크에 저장된다고 가정하겠다.

직접 저장장치

• 자기물질로 만들어진 여러개의 디스크 원반으로 이루어졌다.
• 각 면마다 헤드가 있다.
  • 이걸로 읽고 쓴다.
• 정보는 트랙에 저장된다.
• 디스크들끼리 같은 지름을 가지는 트랙을 실린더라고 한다.
• 한 트랙의 용량은 매우 커서 여러 섹터로 구분된다.
• 블록은 하나 이상의 섹터들로 이루어진다.

데이터가 어떻게 저장되느냐에 따라 db 성능에 큰 영향을 준다.

-> 자료 검색의 기본 원리를 아는 것이 중요하다.

탐구시간(seek time)

• 헤드가 원하는 트랙까지 이동하는데 걸리는 시간
• 제일 시간 소모가 크다.

회전 지연시간(rotational delay)

• 트랙에서 원하는 레코드가 헤드 밑에 회전하여 올 때까지 걸리는 시간

보통 탐구시간이 회전지연보다 길다.

데이터 접근시간(data access time)

• 탐구시간 + 회전지연시간 + 데이터전송시간

성능 개선을 위해서는 탐구시간을 줄여야한다.

어떻게??

• 헤더의 움직임을 최소화
  • 즉, 디스크 접근횟수의 최소화
    • 디스크 접근시간은 주기억장치보다 느리기 때문이다

=> 한 실린더에 저장을 하면 빠르다

플래시 메모리

HDD SSD 둘다 비휘발성 메모리다.

DBMS 저장장치는 하드디스크를 기반으로 발전했다.
HDD는 비휘발성(영구 저장) 데이터 장소로 기계적인 회전디스크를 통해 입출력이 수행, 순차적 탐색 뛰어남

하드디스크(HDD)

• Updatd in Place
• 기계적인 회전 디스크를 통해 입/출력 동작 수행
  • 순차적인 접근은 매우 뛰어남
  • 임의적인 접근(random access)에는 취약함
• 쓰기횟수에 대해 제한이 없는 반영구적 수명을 가진다.

-> 이러한 이유때문에 DBMS 물리적 구조는 순차적 탐색을 효율적으로 처리하는 방식으로 구현되어 왔다.

-> 그런데 전기적 신호를 사용해 임의 탐색이 뛰어난 플래시 메모리가 많이 사용되어서 순차탐색 위주의 설계방식에 새로운 변화가 일어났다.

플래시 메모리

• 전기적인 신호 사용
• 임의 접근이 뛰어남
• 성능이 HDD보다 훨씬 좋음
  • 근데 쓰기 연산은 매우 느림
• 소형 정보 기기들이 대중화됨에 플래시 메모리 기반의 SSD가 보편화 되었다.
  • DBMS 설계의 변화.. 순차적에서 변화가
• SSD는 HDD와 달리 덮어쓰기 연산을 할 수 없음
  • 사전에 블록단위로 지우고 쓰기를 해야한다.(UPdate out place)
    • 그래서 읽는건 HDD보다 sSD가 훨 빠른데 쓰기는 느리다.
• 쓰기횟수가 제한된다
  • 하나의 블록에 슈류류ㅠㄱ 쓴다면 그 불록 수명이 죽을수도

SSD를 효율적으로 사용하기 위해 새로운 DBMS 관리 기법 연구가 필요하다

운영체제의 역할

• DBMS는 운영체제에서 화일관리자와 디스크 관리자(입출력 서비스)를 이용한다.

페이지

• 입출력의 단위
  • 디스크와 주 기억장치 사이에 한번의 디스크 접근으로 데이터가 전송되는 양
  • 입출력은 시스템에서 속도가 가장 느린 작업
    • 입출력을 줄이는 것이 DBMS 성능을 향상시키는데 중요

가능하면 많은 블록들, 자주 참조되는 블록을 주기억장치에 유지하면 블록 전송 횟수를 줄일 수 있어 성능이 좋아진다.

파일 조직 방법

화일 조직(file organization)

• 데이타베이스의 물리적 저장 방법

화일 조직 방법

• 순차 방법
• 인덱스 방법
• 해싱 방법

순차(sequential) 방법

엔트리 순차(entry-sequence) 화일

• 레코드가 시스템에 삽입되는 순서로 만들어진다.
  • 입력 순서대로

키 순차(key-sequence)화일

• 레코드들의 키 값의 크기 순으로 만들어진다.
  • 레코드 중간에 값을 삽입하기 위해서 성능 저하가 일어난다. (소팅 다시)

일괄 처리(batch processing)에서 많이 사용된다.

인덱스(index) 방법

• 데이터를 신속하고 효율적으로 검색하기 위해 먼저 인덱스를 찾은 후, 원하는 레코드에 접근하는 방법
  • 인덱스를 구축, 유지하기 위해 비용이 필요하다.
    • 인덱스를 많이 만들면 오히려 성능이 떨어질 수도
      • 적절하게 만드는것이 중요
• 인덱스 화일(indexed file)과 데이타 화일(data file)로 구성
• 인덱스 화일은 키값과 주소 쌍으로 구성

인덱스 방법 종류

• 기본 인덱스
• 보조 인덱스
• 클러스터링 인덱스
• 비클러스터링 인덱스
• 다단계 인덱스

기본 인덱스(primary index)

기본 인덱스

• 기본키를 가지고 만드는 인덱스

  • DBMS에 의해 자동으로 만들어진다.
  • 인덱스된 순차 파일(indexed sequential file)이라고 한다.

• 순서로 된 인덱스파일을 가지고 직접 접근(direct access)

  • 키 값(primary key)에 따라 정렬된 순차 데이터파일에 순차적으로 접근(sequentail access)

direct access 후 sequential access

• 이를 위해 인덱스 파일과 순차 데이터 파일로 구성된다.

보조 인덱스(secondary index)

• 기본 인덱스 외의 인덱스를 보조 인덱스라 한다.
  • 기본키가 아닌 필드에 대해 인덱스를 생성하면 이를 보조 인덱스라 한다.
• 한 릴레이션에 여러개의 인덱스를 정의해야할 필요성이 있다.
  • 기본 키 말고 다른 속성을 이용해 접근해야할때
    • 보조 인덱스를 이용하면 헤더 움직임을 줄일 수 있어!

클러스터링 인덱스(clustering index)

• 탐색키 값에 따라 정렬된 데이터 화일을 가진다.
• 범위를 설정하는 질의에 유용하다.
  • 데이터파일과 인덱스가 증가하는 순서를 가진다면 원하는 값을 찾기 쉽다.
• 기본 인덱스는 클러스터링 인덱스의 한 종류다.

비클러스터링 인덱스(non-clustering index)

• 데이터 파일의 레코드들이 탐색키값과 무관하게 저장되어 있다.
• 레코드를 검색할 때마다 매번 다른 디스크 블록에 접근한다.
• 보조 인덱스는 비클러스터링 인덱스의 한 종류이다.

다단계 인덱스(multi-level index)

• 인덱스 자체가 큰 경우 인덱스 엔트리 탐색시간을 줄이기 위해 다시 인덱스를 정의
  • 원래의 인덱스는 1단계 인덱스라, 추가 인덱스를 2단계 인덱스라 한다.
  • 가장 상위 단계의 엔트리들이 한 블록에 들어갈때까지 반복..
    • 이렇게 하면 주 기억장치에 상위 단계 엔트리가 들어갈 수 있다.
    • 가장 상위단계 인덱스: 마스터인덱스
• B트리나 B+트리를 사용한다

B트리

인덱스를 구현하는데 가장 많이 사용되는 구조

차수가 M인 B트리의 특성

• 비어있거나 높이가 1이상인 M-way(자식노드가 최대 M인) 탐색트리
• 루트와 리프를 제외한 모든 노드는 최소 |m/2|, 최대 m개의 서브트리를 갖는다.
• 루트는 리프가 아닌 이상, 적어도 2개의 서브트리를 가진다.
• 모든 리프는 같은 레벨에 있어야한다
• 리프가 아닌 노드의 키 값 수는 그 노드의 서브트리 개수보다 하나 적다.
• 리프 노드에 있는 키 값 개수는 최소 |m/2|-1개 최대 m-1개를 가진다.
• 한 노드 안에 있는 키 값은 오름차순으로 정렬되어 있어야 한다.

B트리의 연산

검색

루트노드로부터 키 값을 비교하며 내려간다.

삽입

• 삽입은 항상 리프노드에서 수행
  • 빈 공간이 있을 시, 값을 삽입하면 된다.
    • 오름차순을 만족시키면서

리프 노드에 공간이 없으면??

• 일단 해당 리프노드의 키값들과 삽입할 값을 정렬한다.
  • 중간 값을 부모로 올리고 갈라지는 자식 노드를 만든다.
    • 이 때, 부모에서도 오름차순을 만족 시켜야한다.

삭제

• 리프노드에서 간단히 삭제할 수 있는 경우는 그냥 값을 지우면 된다.
• 하지만 리프가 아닌, 중간 노드일 시 복잡한 과정을 거친다.
  • 후행 키값(리프)와 삭제할 키 값을 바꾸고 삭제를 해야한다.
    • 하지만 삭제 후 남은 키값의 수가 [m/2]-1에 미달되면 복잡해진다.
      • 재분배 방법 or 합병 방법을 사용해 최소 키값 수를 유지해야한다.

재분배(redistribution)방법

• [m/2]개 이상의 키를 가지고 있는 형제 노드가 있을 시, 이 형제 노드의 키를 이동 시킨다.
  • 삭제하려는 값(언더플로우를 일으키는 노드) 자리에 원래 삭제하려는 노드의 부모 키 값을 넣고 이 노드 자리에는 형제 노드로부터 키값을 가져와 넣으면 된다.

합병(merge)방법

• 재분배 방법이 불가할 시, 형제 노드들의 키값, 부모노드의 키값, 언더플로우가 발생되는 노드의 키값을 모두 모아 합병한 후 합병 결과를 사용한다.

B+트리

• B트리 순차 접근의 취약점을 보완한 트리
• 실제 DBMS에서 가장 많이 사용된다.
• 인덱스 세트, 순차 세트로 구성된다.

인덱스 세트(index set)

• 리프노드에 있는 키들에게 접근할 수 있는 경로로 사용된다
• 직접 접근(direct access)을 지원한다.

순차세트(sequence set)

• 리프노드로 구성된다
• 인덱스 부분에 있는 키 값이 다시 표시된다.
• 링크드 리스트로 연결되어 있어, 순차 접근도 가능하다.

차수가 m인 B+트리의 특성

• 루트는 0 or 2~m개 사이의 서브트리를 가진다.
• 모든 리프 노드는 같은 레벨이다.
• 리프가 아닌 노드에 있는 키값 수는 그 노드의 서브트리 수보다 하나 적다.
• 한 노드에 있는 키값들은 오름차순이다.

노드의 구조는 서브트리에 대한 포인터 + 키값으로 구성된다.
포인터가 지시하는 왼쪽 서브트리에 있는 노드들의 모든 키값은 그 상위(부모) 키값보다 작거나 같다.
오른쪽 서브트리의 노드들의 키 값은 상위(부모) 키값보다 다 크다

리프 노드는 (키값,키값을 가진 레코드에 대한 주소)들과 마지막에 다음 리프노드에 대한 링크로 구성된다.

키값 개수 q는 [m/2]<=q이다.

B트리와의 차이점

• 인덱스 세트에 있는 키 값은 리프 노드에 있는 키 값을 찾아가는 경로로만 사용된다.
  • 그래서 인덱스 세트에 있는 모든 키값들은 순차 세트에 다시 나타난다.
  • 인덱스 세트와 리프노드의 구성은 서로 다르다.
    • 리프 노드는 키값과 키 값을 가진 레코드에 대한 주소가 있다.
    • 인덱스 세트 노드는 키 값만 저장되어 있다.
      • 노드에 저장할 수 있는 원소의 수도 다르다.
• 순차 세트의 모든 노드는 링크리스트로 되어 있어 순차 접근이 효율적이다.

B+ 트리의 연산

탐색

• B트리의 m-way 탐색 트리와 같다.
• 레코드는 리프에서 검색된다.

삽입

• 리프노드가 오버플로우 되면, 두개의 노드로 분할된다.
  • 분할된 리프노드도 링크드 리스트가 되어야한다.
  • 중간 키 값이 부모노드로 올라가 저장된다.
    • 분할된 리프노드에도 저장이 되어야 한다.

삭제

• 재분배, 합병이 필요 없는 경우에는 리프에서만 삭제하면 된다.
  • 인덱스 세트에 키 값이 남아있어도 괜찮다.
    • 실제 사용하는 값이 아닌, 분리자(seperator)로 사용되기 때문이다.

재분배

• B트리 처럼 형제노드에서 슉 빌려오면된다.
  • 인덱스 세트도 맞게 바꿔야한다.

합병

• 인덱스의 키 값도 삭제된다.
  • 필요없으면 버려~

해싱 방법

다른 레코드를 참조하지 않고 원하는 목표 레코드를 직접 접근하는 직접 화일 방법
단점: 충돌이 일어날 수도 있다.

해싱 함수(hashing function)

• 어떤 키 값이 주어졌을 때 그 키 값으로부터 그 키값을 가진 레코드가 저장되어 있는 주소를 계산해 낼 수 있는 기법

해시 키(hash key)

• 레코드 주소를 계산하기 위해 사용하는 레코드 키 값

해시 주소(hash address)

• 계산 결과로 나온 주소