데이터 구조 및 파일 구조

• 데이터 구조
  • 데이터 구조는 데이터를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
  • 효과적으로 설계된 데이터 구조는 실행시간 또는 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 보장
  • 데이터 구조는 각자의 연산 및 목적에 적합하도록 설계됨
  • B^-트리는 데이터베이스에 효율적이며, 라우팅 테이블은 네트워크에 일반적으로 사용
  • 다양한 프로그램을 설계함에 있어 어떠한 데이터 구조를 선택할지 우선적으로 고려해야 함
  • 일단 데이터 구조가 선택되면 적용할 알고리즘은 상대적으로 명확해짐
  • 데이터 구조에 있어 가장 기초적인 단위로는 행령, 레코드, 트리, 그래프 등이 있음
       
• 파일 구조
  • 파일 구조는 데이터를 효율적으로 이용할 수 있도록 파일에 저장하는 방법
  • 릴레이션을 구성하는 레코드는 일반적으로 하나의 파일로 존재하며 디스크 블록에 저장됨
  • 블록은 디스크의 물리적인 속성으로 운영체제에 의해 결정되는 고정된 크기이지만, 레코드 크기는 가변적임
  • 레코드는 고정 길이 또는 가변 길이의 필드로 구성, 즉 연관된 필드들이 모여서 고정 길이 또는 가변 길이 의 레코드가 됨
  • 한 파일에 속하는 블록들이 반드시 물리적으로 인접해 있지는 않음
  • 인접한 블록들을 읽는 경우에는 탐색 시간과 회전 지연 시간이 필요하지 않기 때문에 입출력속도가 빠르고, 필요에 따라 블록들이 인접하도록 구성하는 것이 좋음
       
• 파일 구조의 종류
  • 힙 파일 구조(Heap File Organization)
    • 파일 안에 레코드를 위한 공간만 있으면 임의의 레코드는 어디든지 놓일 수 있는 구조
    • 가장 단순한 파일 조직으로 일반적으로 레코드들이 삽입된 순서대로 파일에 저장되는 비 순서 파일 구조
    • 새로 삽입되는 레코드는 파일의 가장 끝에 첨부되는데, 파일 중간에 빈 공간이 있으면 삽입 가능
    • 원하는 레코드를 찾기 위해서는 모든 레코드들을 순차적으로 접근해야 하며, 삭제는 원하는 레코드를 찾은 후에 그 레코드를 삭제함
    • 좋은 성능을 유지하기 위해 힙 파일을 주기적으로 재구성할 필요가 있음
    • 힙 파일은 질의에서 모든 레코드들을 참조하고 레코들을 접근하는 순서가 중요하지 않을 때 사용하는 것이 효율적
  • 순차 파일 구조(Sequential File Organization)
    • 입력된 레코드들을 논리적인 순서에 따라 물리적 연속 공간에 순차적으로 기록하는 방식
      • 레코드들의 물리적 순서가 그 레코드들의 논리적 순서와 같게 저장
      • 급여 관리 등과 같이 변동 사항이 크지 않고 기간별로 일괄 처리를 주로 하는 경우에 적합
      • 삽입 연산은 삽입하려는 레코드의 순서를 고려해야 하기 때문에 시간이 많이 걸릴 수 있음
      • 삭제 연산은 삭제된 레코드가 사용하던 공간을 빈 공간으로 남기기 때문에 힙 파일의 경우와 마찬가지로 주기적으로 순차 파일을 재구성해야 함
    • 순차 파일의 종류
      • 엔트리(Entry) 순차 파일 : 레코드가 시스템에 삽입되는 순서대로 만들어지는 파일
      • 키(Key) 순차 파일 : 레코드들의 키 값의 순서대로 만들어지는 파일
    • 장점
      • 기록 밀도가 높아 기억 공간을 효율적으로 사용할 수 있으며, 매체 변환이 쉬워 어떠한 매체에도 적용할 수 있음
      • 레코드를 기록할 때 사용한 키 순서대로 레코드를 처리하는 경우에는 매우 빠름
    • 단점
      • 파일에 새로운 레코드를 삽입 및 삭제하는 경우, 파일 전체를 복사해야 하므로 시간이 많이 소요
      • 데이터 검색 시 처음부터 순차적으로 검색하기 때문에 직접 접근이 어려움
  • 직접 파일 구조(Direct File Organization)
    • 저장하고자 하는 데이터의 키 값을 저장 공간의 물리적 주소로 변환할 수 있는 어떤 관계를 정의해 두었다가 이를 활용하는 파일 구조
    • 이러한 관계는 디렉토리나 해싱 함수를 사용하여 구현될 수 있으며, 직접파일은 오직 직접 접근 방법만을 지원
    • 해싱 함수를 통하여 레코드 키를 디스크의 물리적 주소로 변환하여 그 주소에 레코드를 저장하는 파일 구조를 해싱 파일 구조라 함
    • 해싱 파일 구조를 구축할 때 고려해야 할 필수적인 설계 요소 : 버킷 크기, 적재율, 해싱 함수, 오버플로우 해결 기법 등
  • 인덱스된 순차 파일 구조(Indexed Sequential File Organization)
    • 순차 접근 방법을 지원하는 순차 파일과 직접 접근 방법을 지원하는 직접 파일을 결합한 형태의 파일 구조
    • 키 값에 따라 정렬된 레코드를 순차적으로 접근하거나 주어진 키 값에 따라 직접 접근할 수 있는 파일 구조
    • 순차적으로 정렬된 순차 데이터 파일과 이 파일에 대한 포인터를 가지고 있는 인덱스로 구성
    • 인덱스와 순차 데이터 파일을 구성하는 방법에 따라 정적 인덱스 방법(ISAM 파일)과 동적 인덱스 방법(VSAM 파일)으로 구분되며, 다단계 인덱스를 사용하는 목적은 탐색 횟수를 줄이기 위해서임
    • ISAM(Index Sequential Access Method) 파일
      • 기본 구역(Prime Area) : 실제 레코드들을 기록하는 부분으로, 각 레코드는 키 값 순으로 저장
      • 인덱스 구역(Index Area) : 기본 구역에 있는 레코드들의 위치를 찾아가는 인덱스가 기록되는 부분으로, 트랙 인덱스 구역, 실린더 인덱스 구역, 마스터 인덱스 구역으로 구분
      • 오버플로우 구역(Overflow Area) : 기본 구역에 빈 공간이 없어서 새로운 레코드의 삽입이 불가능할 때를 대비하여 예비적으로 확보해 둔 구역
        • 실린더 오버플로우 구역 : 각 실린더마다 만들어지는 오버플로우 구역으로써, 해당 실린던의 기본 구역에서 오버플로우된 레코드를 기록
        • 독립 오버플로우 구역 : 실린더 오버플로우 구역에 더 이상 오버플로우된 데이터를 기록할 수 없을 때 사용할 수 있는 예비 공간
    • VSAM(Virtual Storage Access Method) 파일
      • 제어 구간(Control Interval) : 데이터 레코드가 저장되는 부분
      • 제어 구역(Control Area) : 몇 개의제어 구간을 모아 놓은 부분
      • 순차 세트(Sequence Set) : 제어 구역에 대한 인덱스를 저장한 곳
      • 인덱스 세트(Index Set) : 순차 세트의 상위 인덱스
  • 다중 키 파일 구조(Multi-key File Organization)
    • 하나의 데이터 파일에 대해 서로 다른 키 필드를 이용하여 여러 개의 접근 경로, 즉 여러 개의 인덱스를 제공하여 데이터를 탐색할 수 있도록 지원하는 파일 구조
    • 대표적인 것으로 역 파일과 다중 리스트가 있음
    • 역 파일(Inverted File) 구조
      • 어느 한 키에 대한 역 인덱스는 데이터 레코드 파일에 나타나 있는 그 키에 대한 값들을 인덱스 키로 모두 포함하고, 역 인덱스의 각 키 값 엔트리는 동일한 키 값을 가지고 있는 모든 데이터 레코드들에 대한 포인터를 전부 가짐
      • 역이란 인덱스 엔트리가 될 2개의 값들에 대해 데이터 레코드로 부터 추출해서 해당 인덱스에 전도시키는 것을 의미하여, 데이터 파일은 키 필드에 대해 전도되었다고 함
      • 보조키로 기본키를 찾는 것을 역 인덱스라 하는데, 이진 탐색 기법을 사용하면 연산 시간이 O(log₂N)이 되므로 매우 효율적으로 검색할 수 있음
    • 다중 리스트(Multi-List) 구조
      • 각 보조키(인덱스)마다 각각 연결(linked) 리스트로 구성하는 다중 리스트 파일을 유지하는 구조
      • 인덱스 엔트리가 < 키 값, 하나의 레코드에 대한 포인터 > 쌍으로 구성되며, 각 키 값에 대한 엔트리는 그 키 값을 가지고 있는 데이터 레코드 중 하나의 레코드에 대한 포인터만 가지고 있고, 나머지 레코들에 대한 정보는 리스트 구조로 실제 데이터 파일에서 유지되는 방법
  • 다중 링 파일 구조(Multi-ring File Organization)
    레코드들의 다중 관계를 표현한 파일로서, 같은 특성을 가진 레코드들의 집합을 체인(Chain), 즉 연결 리스트로 연결하여 레코드들을 신속하게 검색하기 위한 파일 구조
  • 클러스터링 파일 구조(Clustering File Organization)
    • 서너 개의 다른 릴레이션들의 레코드들을 같은 파일에 저장하거나 서로 다른 릴레이션들의 관련된 레코드들을 같은 블록에 저장하는 파일 구조
    • 하나의 입.출력 연산으로 모든 릴레이션들로부터 관련된 레코드들의 검색이 가능
    • 파일 내 클러스터링(Intra-file Clustering)
      한 파일 내에서 함께 검색될 가능성이 높은 레코드들을 디스크 상에서 물리적으로 가까운 곳에 모아 두는 것
    • 파일 간 클러스터링(Inter-file Clustering)
      논리적으로 연관되어 함께 검색될 가능성이 높은 2개 이상의 파일에 속한 레코드들을 디스크 상에서 물리적으로 가까운 곳에 저장하는 것
    •    
• 버퍼 관리
  • 버퍼는 디스크 블록들을 저장하는데 사용되는 주기억 장치 공간
  • 디스크 입.출력은 컴퓨터 시스템에서 가장 속도가 느린 작업이므로 입.출력 횟수를 줄이는 것이 DBMS의 성능을 향상하는데 매우 중요함
  • 가능한 한 많은 블록들을 주기억 장치에 유지하거나 자주 참조되는 블록들을 주기억 장치에 유지하면 블록 전송 횟수를 줄일 수 있음
  • 버퍼 관리자는 운영체제의 구성 요소로, 주기억 장치 내에서 버퍼 공간을 할당하고 관리하는 모듈
  • 버퍼 교체 전략(Buffer Replacement Strategy)
    • 버퍼에 남아 있는 블록 중에서 어느 블록을 새로운 블록으로 교체할 것인가를 결정하는 전략
    • 대부분의 운영체제는 가장 오랫동안 사용되지 않은 블록을 교체하는 LRU(Least Recently Used)기법을 사용
         
  • ISAM 파일 - 데이터 파일에 레코드가 삽입되거나 삭제될 때 인덱스의 내용은 변하지만 인덱스의 구조 자체는 변경되지 않는 방법으로,정적 인덱스 방법이라 함
  • VSAM 파일 - 인덱스나 데이터 파일을 블록으로 구성하고 각 블록에는 추가로 삽입될 레코드를 감안하여 빈 공간을 미리 예비해 두는 방법으로, 동적 인덱스 방법이라 함