태양 만세!

1. 인덱싱과 해싱 I

   9.1 인덱싱

• 인덱싱이란?
  • 인덱싱은 데이터 검색에서 발생하는 비효율적인 문제를 해결하기 위한 기법
    • 인덱스: DBMS에서 요청된 레코드에 빠르게 접근할 수 있도록 하는 데이터와 관련된 부가적인 구조
    • 인덱싱: 인덱스를 디자인하고 생성하는 작업
  • DMBS는 인덱스를 통하여 레코드가 디스크 저장장치 또는 메모리의 어느 블록에 저장되어 있는지 파악하고, 해당 블록을 읽어 들임
    • 검색키: 파일에서 레코드를 찾는데 사용되는 컬럼이나 컬럼의 집합

         

• 인덱스의 종류
  • 순서 인덱스: 특정 값에 대해 정렬된 순서 구조
  • 해시 인덱스: 버킷의 범위 안에서 값의 균일한 분포에 기초한 구조로 해시 함수가 어떤 값이 어떤 버킷에 해당되는지 결정

       

• 인덱스의 평가기준
  • 접근시간: 데이터를 찾는 데 걸리는 시간
  • 유지비용: 새로운 데이터 삽입 및 기존 데이터 삭제연산으로 인한 인덱스 구조 갱신 비용
  • 공간비용: 인덱스 구조에 의해 사용되는 부가적인 공간비용

       

9.2 순서 인덱스

• 순서 인덱스
  • 검색키로 정렬된 순차파일에 대하여 레코드에 대한 빠른 접근이 가능하도록 순서 인덱스를 사용
    • 검색키를 정렬하여 해당 검색키와 관련된 레코드와의 연계를 통하여 인덱스 생성
• 인덱스 엔트리의 구조

포인터: 검색키에 대응되는 한 개 이상의 레코드에 대한 포인터로, 레코드가 저장되어 있는 디스크블록의 식별자와

블록 안에서 레코드를 인식하기 위한 오프셋으로 구성

• 순서 인덱스의 분류
  • 밀집(dense) 인덱스
  • 희소(sparse) 인덱스
• 밀집 인덱스
  • 모든 레코드에 대해 [ 검색키 값 | 포인터 쌍 ] 을 유지

    

  • 인덱스의 엔트리가 소수의 검색키 값만을 유지

    

• 다단계 인덱스
  • 4KB 크기의 한 블록에 100개의 엔트리가 들어간면, 100,000,000 개의 레코드의 인덱스를 유지
    • 100,000,000ro의 블록 = 4GB의 공간
    • 인덱스의 용량이 작아 전체가 메모리에 적재되면 탐색시간이 축소
    • 인덱스가 메모리보다 크다면 저장된 블록을 디스크로부터 읽어야하기 때문에 I/O 비용이 증가하여 탐색시간 증가

      => 다단계 인덱스를 구성하여 해결

  • 내부 인덱스와 외부 인덱스로 구성
    • 외부 인덱스를 내부 인덱스보다 희소한 인덱스로 구성하여 엔트리의 포인터가 내부 인덱스 블록을 지칭
    • 포인터가 가리키는 블록을 스캔하여 원하는 레코드보다 작거나 같은 검색키 값 중에 가장 큰 값을 가지는 레코드를 찾음
  • 내부 인덱스는 1,000,000 개의 블록을 갖고, 외부 인덱스는 100개의 블록만 사용하여 40MB의 외부 인덱스는 메모리에 적재가능

    

9.3 B+_트리 인덱스

• B+_트리 인덱스
  • 루트 노드로부터 모든 단말 노드에 이르는 경로의 길이가 같은 높이 균형 트리
    • 순서 인덱스는 파일이 커질수록 데이터 탐색에 있어서 접근 비용이 커지는 문제점을 해결하기 위해 제안
    • 현재까지도 널리 사용되는 대표적인 순서 인덱스

         

  • B+_트리의 노드 구조

    

     

• B+_트리 구성
  • 인덱스 세트: 단말이 아닌 노드로 구성
    • 단말 노드에 있는 검색키 값을 신속하게 찾아갈 수 있도록 경로를 제공하는 목적으로 사용
    • [n/2], n 사이의 자식을 가짐
  • 순차 세트: 단말 노드로 구성
    • 모든 노드가 순차적으로 서로 연결
  • 단말 노드의 예

    

       

• 

     

• B+_트리의 특징
  • 루트는 2, 혹은 𝑛/2~𝑛개 사이의 포인터를 가짐
  • 루트와 단말 노드를 제외한 모든 노드는 최소 𝑛/2 에서 𝑛개 사이의 포인터를 가짐
  • 모든 단말 노드는 루트로부터 같은 거리
  • 단말 노드가 아닌 노드에 있는 검색키 값의 수는 그 노드의 포인터 수보다 하나 적음
  • 단말 노드는 데이터 파일의 순차 세트를 나타내며 모두 리스트로 연결
  • 단말 노드는 적어도 (𝑛−1)/2 개의 검색키 값을 포함

       

• B+_트리 상에서의 검색
  • V=검색키, 현재 방문한 노드 = N
    • 𝑁을 조사하여 𝑉값과 같거나 𝑉보다 큰 검색키 중 가장 작은 𝐾𝑖를 찾음
    • 𝐾𝑖=𝑉이면 𝑃𝑖+1이 가리키는 노드를 방문함 (𝑁=𝑃𝑖+1)
    • 𝐾𝑖>𝑉 이면 𝑃𝑖 이 가리키는 노드를 방문함 (𝑁=𝑃𝑖)
    • 𝑉>𝐾𝑚−1 이면, 마지막 포인터 𝑃𝑚이 가리키는 노드를 방문함 (𝑁=𝑃𝑚)
    • 변경된 𝑁이 단말 노드가 아니라면, 단말 노드가 될 때까지 이전 과정을 반복
    • 𝑁이 단말 노드라면

      𝐾𝑖=𝑉이면 𝑃𝑖이 가리키는 레코드를 읽음

      𝐾𝑖와 같은 𝑉 가 없다면 𝑉를 가지는 레코드는 존재하지 않음

     

• B+_트리 상에서의 검색 예

  => '장보고' 검색

  

     

• B+_트리 상에서의 삽입과 삭제
  • 삽입: 검색과 같은 방법을 사용하여 삽입되는 레코드의 검색키 값이 속할 단말 노드를 찾음
    • 해당 단말 노드에 <검색키 값, 포인터> 쌍을 삽입
    • 삽입 시 검색키가 순서를 유지
  • 삭제: 삭제될 레코드의 검색키를 통해 삭제될 검색키와 포인터를 포함한 단말 노드를 찾음
    • 같은 검색 키 값을 가지는 다중 엔트리가 존재할 경우, 삭제될 레코드를 가리키는 엔트리를 찾을 때까지 탐색 후 단말 노드에서 제거
    • 단말 노드에서 제거된 엔트리의 오른쪽에 있는 엔트리들은 빈 공간이 없도록 왼쪽으로 이동

         

• 노드가 분할되는 삽입

  =>'강감찬' 삽입

  

     

     

  

  • 강감찬을 삽입하고자 하는 노드에 더 이상 저장할 공간이 없으므로 노드를 위 그림과 같이 분할
    • 강감찬과 김영희를 하나의 단말 노드로 구성
    • 나태양과 도철수가 하나의 단말 노드로 구성

         

    

    • 새로 만들어진 단말 노드의 가장 작은 검색키 값을 가진 '나태양'은 부모 노드에 공간이 존재하기 때문에

      추가적인 노드 분할 없이 새로운 노드를 가리키는 포인터를 삽입

• B+_트리 상에서 노드가 병합되는 삭제
  • 강감찬이 추가된 B+트리에서 피천득 삭제
    • 피천득이 있는 단말 노드를 검색

      해당 단말 노드는 삭제 후 홍길동만 남게 됨

      (𝑛−1)/2 개 보다 적은 검색키 값이 적으므로 다른 노드와의 병합이 필요

         

    • 홍길동이 저장된 노드의 왼쪽의 형제 노드와 병합

      홍길동을 포함한 엔트리를 형제 노드로 이동

      비워진 노드를 삭제

      비워진 노드를 가리키는 포인터도 삭제

      기존의 포인터를 대체할 '정도전＇을 부모 노드에 삽입

         

  • '피천득' 삭제 결과

    

• 데이터 저장과 파일

  8.1 물리적 저장장치

  • 물리적 저장장치
    • 물리적 저장장치들은 데이터 접근 속도를 기준으로 다양한 장치로 분류

         

      

       

  • 기억 지속성 관점에서 분류
    • 휘발성
      • 주기억장치: 레지스터, 캐시, 메인 메모리로 주로 CPU가 이용
    • 비휘발성
      • 보조기억장치: 디스크와 같이 주기억장치보다 하위에 위치하여 주기억장치를 보조
      • 3차 기억장치: 광학 디스크 드라이브, 자기 테이프
    • 캐시
      • 고비용 저장장치로 빠른 데이터 접근 속도를 보장
      • 레지스터를 제외하면 프로세서가 가장 빠르게 접근
    • 메인 메모리
      • 프로그램과 데이터가 적재되는 공간
    • 플래쉬 메모리
      • 메인 메모리와 유사하나 비휘발성 저장장치로 전원이 꺼져도 데이터를 유지
      • 디스크보다 빠른 접근 가능
    • 자기 디스크
      • 주로 데이터베이스 전체가 저장되는 공간으로 데이터를 안정적으로 저장
    • 광학 디스크 드라이브
      • 대표적인 광학 기억장치는 CD
      • DVD의 경우 4.7GB 정도
    • 테이프 저장장치
      • 기록 데이터를 저장하는데 사용
      • 자기 디스크보다 용량이 크고 저렴
      • 데이터를 순차적으로 읽어야 하기 때문에 데이터 접근이 매우 느림

         

  8.2 RAID

  복수의 디스크를 사용

• 표준 RAID 수준
  • RAID 0 수준: 스트라이핑
    • 스트라이핑: 빠른 데이터 입출력을 위해 데이터를 여러 디스크에 나누어 저장
    • 데이터를 중복 저장하지는 않기 때문에, 디스크 장애 발생시 데이터 손실 발생
  • RAID 1 수준: 미러링
    • 데이터를 중복 저장하기 때문에, 디스크 장애 발생시 데잍어 복구가 가능
    • 용량이 큰 데이터에 대한 병렬적으로 빠른 읽기가 가능
    • 쓰기의 경우 성능이 저하
  • RAID 0+1 수준: 스트라이핑과 미러링
  • RAID 2 수준: 스트라이핑과 에러 검출 및 정정
  • RAID 3 수준: 패리티비트 기반 스트라이핑
  • RAID 4 수준: 패리티비트 기반 개량 스트라이핑
  • RAID 5 수준: 삽입 패리티 기반 개량 스트라이핑

     

• 신뢰성 향상
  • 데이터를 중복시켜 여러 디스크에 저장하면, 저장한 데이터가 디스크의 장애에 의해서 손실되어도 복구가능
  • 미러링된 디스크들은 각 디스크의 평균 고장시간과 평균 수리시간에 영향
    • 평균 고장시간: 디스크가 고장 나기까지 걸리는 시간
    • 평균 수리 시간: 고장 난 디스크를 교체하고 데이터를 복구하는데 걸리는 시간
    • 평균 데이터 손실 시간: 미러링된 디스크가 데이터를 손실하는데 까지 걸리는 시간

     

• 성능 향상
  • 미러링: 복수의 디스크에 병렬적인 접근하여 처리함으로써 읽기 속도 향상
  • 스트라이핑: 데이터를 다수의 디스크에 나누어 저장하기 때문에 성능이 향상

       

    

       

       

  8.3 파일 구성

  

  • 파일 구성
    • 파일: 데이터를 영구적으로 저장하기 위해 사용되는 가장 기초적인 구조
    • 블록: 파일을 고정적인 길이로 분할하여 생기는 균등한 크기의 데이터 묶음

      =>블록 단위로 분할되어 디스크에 기록

    • 레코드: 블록을 구성하는 요소로, 더 이상 분리 되어 저장되지 않는 최소 데이터 저장단위
  • 고정 길이 레코드
    • 각 레코드에 고정적인 바이트 수를 할당하는 기법

      

  • 고정 길이 레코드의 문제점
    • 블록의 길이가 레코드 길이로 정확히 나뉘어 떨어지지 않는 경우

      => 블록 내의 남은 공간으로 저장 공간이 낭비됨

      

    • 레코드 삭제 시
      • 특정 레코드가 삭제되면, 해당 레코드가 저장된 공간이 비기 때문에 낭비가 발생
    • 대처 방법
      • 마지막 레코드로 공백 대체
      • 삭제 레코드 이후에 레코드를 이동
      • 가용 리스트 관리
  • 가변 길이 레코드
    • 블록에 저장되는 레코드의 길이가 서로 다르게 레코드에 가변적인 길이를 할당하는 방법
    • 가변길이 레코드가 쓰이는 경우
      • 한 블록 내에 저장되는 레코드의 유형이 둘 이상
      • 길이가 고정되지 않은 컬럼의 개수가 하나 이상
      • 레코드가 멀티셋을 허용한 컬럼을 가질 때

        *멀티셋: 컬럼값이 여러 개인 컬럼

           

  • 파일 구조화 방법
    • 힙 파일 구조
      • 모든 레코드는 파일 내 임의의 위치에 위치
      • 저장 순서를 고려하지 않음
    • 순차 파일 구조
      • 레코드들이 특정 컬럼에 대한 값을 기준으로 정렬되어 저장
      • 정렬키로 검색키를 사용
    • 해시 파일 구조
      • 레코드를 입력 받아 레코드가 저장될 블록주소를 반환하는 해시 함수를 사용
  • 순차 파일 구조
    • 레코드가 검색키 순서대로 정렬
    • 레코드가 파일에 삽입되는 시점에서 키 값이 부여
    • 장점
      • 검색 키에 대한 정렬 연산이 불필요, 키 값들의 순서로 레코드를 판독하는 연산에 효율적
      • 현재 레코드에서 정렬된 키 순서로 다음 레코드를 찾을 때 부가적인 블록 접근이 불필요
      • 이진 탐색을 사용하면 더 빠르게 레코드를 검색
    • 단점
      • 레코드 삽입, 삭제에 많은 비용 소요됨
  • 다중 테이블 클러스터링 파일 구조
    • 빈번히 조인되는 테이블을 하나의 파일에 저장하기 위한 구조
    • 필요한 테이블이 미리 조인되어 저장

         

         

  8.4 저장장치 접근

  • 저장장치 접근
    • 파일은 논리적 관점에서의 저장이며, 실제 저장될 때에는 여러 개의 물리적 단위인 블록으로 저장

      일반적으로 2KB, 4KB, 8KB, 16KB, 32KB 사용

      • 블록은 데이터의 전송 단위로 블록 전송을 최소화할수록 입출력 소요 시간이 단축
      • 블록전송 최소화
        • 사용 중인 블록을 지속적으로 메모리에 적재
        • 한정적 공간으로 인하여 필요에 따라 특정 블록할당을 해지
        • 메모리 내부에 버퍼라는 공간에 블록을 저장하고, 이를 관리하기 위한 버퍼 관리자를 사용

             

  • 버퍼 관리자
    • DBMS상의 프로그램들은 필요한 블록이 있을 때 버퍼 관리자들에게 해당 블록을 요청
      • 요청된 블록이 버퍼에 있다면, 버퍼 관리자는 블록이 위치한 메모리 주소를 프로그램에게 전달
      • 요청된 블록이 없는 경우, 버퍼 관리자는 버퍼내의 새로운 공간을 할당하고 해당 블록을 적재
      • 더 이상 적재할 공간이 없다면, 버퍼에 있는 기존 블록을 선택하여 할당을 해지하고 해당 블록을 적재
  • 버퍼 관리자의 기능
    • 버퍼 교체 전략
      • 가용 공간을 확보하기 위해 기존에 적재된 블록의 할당을 특정 기준에 의하여 해지
      • 미래에 가장 적게 사용될 블록을 선택하여 디스크로 내보내는 것이 이상적인 버퍼 교체 전략
        • LRU(Least Recently Used)

          최근에 참조된 블록은 다시 참조될 가능성이 높다고 판단하여 가장 최근에 적게 참조된 블록을 교체

        • MRU(Most Recently Used)

          최근에 가장 많이 사용된 블록을 선택하여 블록을 교체

    • 고정 블록
      • 장애로 인하여 메모리의 데이터가 손실되어 작업이 중단될 경우, 중단된 작업의 결과물이 디스크에 기록되는 것을 방지
      • 디스크 블록이 교체되는 것을 제한
    • 블록 강제 출력
      • 시스템 로그와 같이 중요한 데이터는 디스크에 영구적으로 기록되어야 함
      • 버퍼 공간이 필요 없어도 강제로 디스크에 기록

1. 정규화

   7.1 기본 정규형

      

• 제1정규형
  • 릴레이션의 모든 속성이 단일 값으로 구성되어야 하는 조건
  • 정의

    어떤 릴레이션 스키마에서 정의된 모든 속성의 도메인이 원자값을 갖는 상태

       

• 함수적 종속성 판별

  

     

• 함수적 종속성 다이어그램
  • 릴레이션 내의 속성간의 종속 관계를 직관적으로 이해하기 쉽게 도식화 한 표현방식
    • 직사각형: 속성 또는 속성 집합
    • 화살표: 함수적 종속성

  

• 제2정규형
  • 릴레이션이 제1정규형을 만족하고 기본키의 부분집합이 특정 속성을 종속하고 있지 않을 때 제 2정규형이라고 함
  • 정의

    주어진 릴레이션의 인스턴스가 제1정규형을 만족하고 기본키가 아닌 속성들이 기본키에 완전히 종속되어 있는 상태

  • 예

    

       

    

• 릴레이션의 무손실 분해
  • 임의분해 시 발행하는 문제점
    • 불필요한 조인이 발생
    • 분해된 릴레이션을 사용하여 원래 릴레이션을 재구성 하지 못하는 경우
  • 무손실 분해
    • 어떤 릴레이션 스키마 𝑅에 함수적 종속성 𝑋→𝑌가 존재하고 𝑋∩𝑌=∅ 이면, 𝑅을 𝑅−𝑌와 𝑋𝑌로 분해하는 것을 무손실 분해라고 함
  • 도크관리 릴레이션 무손실 분해
    • {도크번호}→{도크관리자}
    • {도크번호}∩{도크관리자}=∅

    => 도크관리 - {도크관리자}, {도크번호, 도크관리자}로 분해

       

• 제3정규형
  • 정의

    릴레이션이 제2 정규형을 만족시키고, 기본키가 아닌 속성들이 어떤 키에도 이행적으로 종속되지 않은 상태

    이행적 종속성 - 𝑋→𝑌이고 𝑌→Z이면 𝑋→Z이다

       

  • 예

    

       

    • {도크번호, 입항시간} → {목적}
    • {목적}→{담당도선사}

      => {도크번호, 입항시간} → {담당도선사}

         

    

       

    

       

    

     

     

• BC정규형
  • 정의

    릴레이션이 제3정규형을 만족하고 릴레이션에서 성립하는 x→Y형태의 모든 함수적 종속성에 대하여 x가 슈퍼키인 상태

  • 입출항관리 릴레이션의 함수적 종속성
    • {도크번호, 입항시간} → {목적}
    • {도크번호, 입항시간} → {출항시간}
    • {목적} → {도크번호}
  • 예

    

7.2 추가적인 정규형

• 다중치 종속성
  • 다중치 종속성의 원인은 릴레이션 속성값이 원자값만을 가져야 하는 제1정규화 제약조건
  • 다중값 속성을 허용하지 않으면 한 번만 삽입될 레코드가 다른 속성들의 값과 같이 매번 중복되어 저장하는 문제가 발생 함
  • 릴레이션 R1, R2, R3 사이에 일대다 관계가 존재하면, R1, R2, R3가 한 릴레이션으로 합쳐지면

    다중치 종속성이 발생 함

       

• 제4정규형
  • 정의

    릴레이션의 스키마 R의 종속성 집합 F에 대한 F+의 모든 자명하지 않은 다중치 종속성 X→→Y에 대하여 X가 P의 슈퍼키인 상태

       

  • 도선사 릴레이션의 다중치 종속성
    • 도선사명 →→ 선박종류
    • 도선사명 →→ 자격증

         

    

     

• 조인종속성
  • 릴레이션을 분해하여 생성된 릴레이션과 원래 릴레이션의 관계를 검사하여 얻음
  • 정의

    릴레이션 스키마 R을 R1, R2,…, Rn으로 분해 시 R1 ∪ R2 ∪ … ∪ Rn = R을 만족하면

    R1, R2,…, Rn은 R에 대해 조인종속성을 가짐

  • 표기
    • *({도선사명, 선박종류}, {도선사명, 자격증})

      =>분해되기 전의 도선사 릴레이션에 대하여 조인종속성을 가짐

         

• 제5정규형