File

<비정렬 파일>

• Heap or a pile file 이라고 불린다.
• 새로운 레코드들이 파일의 가장 마지막으로 삽입된다.
• 파일 레코드들을 통한 Linear Search 레코드들을 검색하기 위해 필수적이다.
  이것은 평균적으로 파일 블록의 절반을 읽거나 검색하기 때문에, 매우 expensive하다.
• 레코드(~=튜플) 삽입은 매우 효율적이다.
• 특정 필드의 순서로 레코드를 읽으려면 파일 레코드를 정렬해야 한다.

<정렬 파일>

• Sequential file이라고 불린다.
• 파일 레코드들은 정렬된 필드들의 값에 의해 정렬상태로 유지된다.
• 삽입이 expensive하다 . 레코드들은 맞는 순서에 의해 삽입되어야 한다.
  일반적으로, 새로운 레코드의 삽입의 효율을 높이기 위해 별도의 비정렬 overflow(또는 트랜잭션)파일을 보관하는 것이 일반적이다.
  이것은 주기적으로 메인 정렬 파일과 합병된다.
• Binary Search가 정렬 필드에서 사용될 수 있다. (log시간안에 작동 가능)
  
• 정렬된 필드의 순소로 레코드를 읽는것은 매우 효율적이다.

 file의 구성, 저장방법에 따라 실행시간이 다르다.

<Hashed files : 자료를 O(1)에 찾을 수 있다. (최상의 경우)>

• 디스크 파일을 위한 해싱은 External Hashing이라고 불린다. ( 하드에 해싱을 구현 )
• 파일 블록은 같은 buckets 사이즈 M개로 나누어진다. 각각 bucket0 , bucket1, ..... bucketM-1( 각각 Home address를 갖는다)
  
• 파일 필드들 중 하나를 파일의 hash key로 지정한다.
• hash key value (K)를 갖는 레코드는 버켓 i 에 저장되며, i=h(k) , 그리고 h는 hash function 이다.
  
• hash key를 이용한 검색은 매우 효율적이다.
• 새로운 레코드가 이미 꽉차 있는 버켓으로 해쉬될 때 충돌이 일어난다.
  이러한 레코드들을 저장하기 위해 overflow 버켓이 사용되며,각 버켓에 해쉬된 overflow record들은 서로 연결될 수 있다.

M개의 Home address.

Overflow record를 줄이기 위해 , 해쉬 파일은 일반적으로 70-80%만 사용한다. (적재율 70~80% ,O(C) //적재율 50% O(1) )

이러한 것은 충돌발생률을 낮춰준다 

해쉬 함수 h^[각주:1]는 레코드들을 버켓에 균일하게 분배해야 한다. 그렇지 않으면 overflow 레코드들이 존재하므로 검색시간이 증가한다.

Static external hashing의 주 단점 : 

 - M을 정하는 것이 어렵다 . 들어오는 데이터의 M의 개수가 더 많거나 너무 적으면 reorganize해야한다.

 - Specific key로 검색을 할 수 없다. 직접 접근은 가능 하지만 Ordered access는 sorting cost가 많이 들어간다.

<Dynamic and Extendible hashed files : M정하기를 보완하기 위해 나온 hashing 기법, Extendible이 더 많이 쓰임>

• 파일 레코드의 길이가 크고 작음에 대해서 동적을 수용하는 것을 허용하는 기술이다.
• Dynamic and extendible hashing 는 디렉토리의 접근하기 위해서 hash value h(K)의 이진법 표현을 사용한다.
  다이나믹 해쉬는 이진트리 사용. extendible 해쉬는 2^d^[각주:2] 사이즈의 정렬이다.
• 디렉토리들은 디스크에 저장될 수 있으며, 동적으로 늘어나거나 줄어들수 있다.
  디렉토리 앤트리들은 저장된 레코드들을 포함하고 있는 디스크 블록을 가리킨다.
• 꽉차 있는 하나의 디스크 블록에 삽입을 하는 것은 블록을 두개의 블록으로 쪼개고 레코드들은 다시 두 개의 블록중에서 재분배된다.
  디렉토리는 적절하게 업데이트 된다.
• Dynamic and extendible hashing은 overflow area를 허용하지 않는다.

모든 Bucket에 Pointer 갯수가 2개이면 dir size는 1/2배 가능하다.

Overflow가 생긴 bucket만 rehashing 해준다.

<Parallelizing disk access using RAID(Redundant Arrays of Inexpensive Disks) technology >

• Data를 쪼개서 여러 개의 packet에 뿌린다. (bits striping , block striping)
• 동시에 data를 읽는다.
• Secondary Storage 기술은 성능과 신뢰도를 향상시키기 위한 단계이다.
• 주요한 장점은 RAID의 발전에 따라 생겨나게 되었다.
• 해결책은 하나의 단일 고성능 논리 디스크같은 역할을 하는 작은 독립적 디스크들의 커다란 집합이다.
• data striping이라고 불리는 개념이 사용되며, 디스크 성능을 향상시키기위해 병렬방법을 사용한다.
• Data striping은 데이터들을 multiple disks에 분배해준다. 데이터들이 하나의 커다랗고, 빠른 단일 디스크처럼 보이게 한다.

<RAID 기술>

• 서로 다른 RAID 조직들은 data striping의 세분성과 중복정보를 계산하기 위해 사용되는 패턴의 두 요소의 다른 조합을 기반으로 정의된다.
  6개의 level로 이루어져 있다.
  Raid level 0 ( Striping Only ) 은 중복이 없고 최고의 쓰기 성능을 갖고 있다. 하지만 데이터 손실의 위험도 있다.
  Raid level 1 ( mirroring Only) Mirrored disks를 사용한다.
  위 의 2level 이 성능과 신뢰도에 큰 기여를 한다.
  Raid level 5는 모든 디스크에 데이터와 Parity정보를 분배한다. (Block 단위 Striping)
• 서로 다른 RAID 조직들은 다른 상황아래서 사용된다.
  Raid level5( 블록 단위 데이터 스트라이핑 )은 커다란 양의 저장을 위해 선호된다.
• 가장 인기 있는 것들은 Level 0 ( with striping ), Level 1(with mirroring) , Level 5 (with an extra drive for parity) 이다
• RAID를 위한 디자인 결정은 Level of RAID, number of disks, choice of parity schemas 를 포함한다.

<Indexes as access paths : To searching Data file record >

• 단일수준 인덱스는 데이터 파일안에서 하나의 레코드를 검색하기 위해 더욱 효율적으로 만들기 위한 하나의 보조 파일이다.
• 인덱스는 주로 파일의 하나의 필드에서 구체화 된다. ( 여러개의 필드여도 구체화 된다 .)
• 인덱스의 하나의 형태는 파일 앤트리 ( <필드 값, 레코드 포인터> ) 이고 필드 값에 의해 정렬된다.
• 인덱스는 Access path라고도 불린다
• 단일 조합 attribute들에 대한 index를 만들 수 있음. 성능 개선을 위해 사용한다. <값 , 위치정보 >
• 인덱스 파일은 항목들이 적기 때문에 데이터파일보다 더욱 적은 디스크 블록을 차지한다.
• 인덱스를 통한 Binary Search는 파일 레코드를 가리키는 포인터를 만든다.
• 인덱스들은 dense or sparse로써 구체화된다.
  dense index는 모든 search key value를 위해 하나의 인덱스 항목을 갖는다.
  sparse index는 오직 몇개의 검색 값을 위해 인덱스 항목을 갖는다.

<예제 : data file, index 추가공간 access time 줄어듦 >

<단일 수준 인덱스의 유형>

• Primary Index
  - 정렬된 데이터 파일에 정의 된다.
  - key field위에 데이터 파일들이 정렬된다.
  
• Clustering Index
   - 정렬된 데이터 파일에 정의된다.
   - non-key field위에 데이터 파일이 정렬된다. 각 레코드들을 위한 별개의 값을 가지지 않는다.
• 두 개의 인덱스 유형은 서로 중복을 갖지 않는다.

<Clustering index>

1. 성능을 결정하는 중요한 열쇠역할 [본문으로]
2. 여기서 d는 global depth를 의미 한다. d의 갯수에 따라 디렉토리가 커진다. [본문으로]