[정처기 필기] 정렬, 검색, 해싱, 파일 편성 방법

정렬의 종류

• 내부 정렬 : 주기억장치에서 정렬이 이루어짐
• 외부 정렬 : 보조기억장치에서 정렬이 이루어짐

 

내부 정렬 종류

• 삽입 정렬
  정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법이다.
  
  
• 버블 정렬
  인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법이다.
  
  
• 선택 정렬
  n개의 레코드 중에서 최소값(또는 최대값)을 찾아 1st 레코드 위치에 놓고, 나머지(n-1) 개의 레코드 중에서 최소값(또는 최대값)을 찾아 2nd 레코드 위치에 놓는 방법을 반복하여 정렬하는 방법이다.
  
  
• 퀵 정렬
  레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법이다.

 

검색

기억 공간 내 기억된 자료 중에서 주어진 조건을 만족하는 자료를 찾는 것이다.

 

검색 방식의 종류

이분 검색(=이진 검색,Binary Search)

• 이분 검색을 실행하기 위한 전제 조건은 자료가 순차적으로 정렬되어 있어야 한다.
• 탐색 효율이 좋고 탐색 시간이 적게 소요된다.
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어든다.

 

선형 검색(Linear Search)

• 주어진 자료에 원소를 첫 번째 레코드부터 순차적으로 비교하면서 해당키 값을 가진 레코드를 찾아내는 가장 간단한 검색 방법이다.
• 데이터를 특별히 조직화할 필요가 없고 다양한 상황에서도 사용될 수 있는 장점이 있지만 n개의 입력 자료에 대해서 평균적으로 (n+1)/2번의 비교를 해야 하므로 비효율적이다.

 

피보나치 검색(Fibonacci Search)

• 이진 검색과 비슷한 원리로, 비교 대상 기준을 피보나치 수열로 결정한다.
• 피보나치 수열 : 1, 2, 3, 5, 8, 13, … 로 앞의 두수이 합이 다음법 값이 된다.

 

블록 검색(Block Search)

• 전체 레코드를 일정한 블록으로 분리한 뒤 각 블록 내의 키값을 순서대로 비교하여 원하는 값을 근노드로 지정하고 근노드보다 작으면 왼쪽, 크면 오른족에 연결하여 구성한다.

 

해싱(Hashing)

• 해싱 함수를 이용하여 레코드키에 대한 해시 테이블 내의 홈주소를 계산하여 주어진 레코드에 접근하는 방식이다.
• 직접 접근 파일을 구성할 때 사용된다.
• 속도는 가장 빠르지만 충돌 현상 시 오버플로 해결의 부담이 가중되며, 많은 기억 공간을 요구한다.

 

해싱 함수의 종류

제산 방법(Division Method)

• 해싱 함수 기법에서 키값을 양의 정수인 소수로 나누어 나머지를 홈주로 취하는 방법

 

중간 제곱 방법(Mid-Square Method)

• 레코드 키값을 제곱하고 나서 그 중간 부분의 값을 주소로 계산하는 방법이다.
• 해시 테이블의 크기에 따라서 중간 부분의 적당한 자릿수를 선택할 수 있다.
• 비트 단위로 n자릿수를 중간 위치 자릿수로 가정하면 해시 테이블의 크기는 2의 n제곱 이다.

 

중첩 방법(Folding Method)

• 해싱 함수 중 주어진 키를 여러 부분으로 나누고, 각 부분의 값을 더하거나 배타적 논리합(XOR: Exclusive OR) 연산을 통하여 나온 결과로 주소를 취하는 방법이다.

 

기수 변환 방법(Radix Conversion Method)

• 해싱 함수 기법 중 어떤 진법으로 표현된 주어진 레코드 키값을 다른 진법으로 간주하고 키값을 변환하여 홈주소로 취하는 방식이다.

 

계수 분석 방법(Digit Analysis Method)

• 주어진 모든 키값들에서 그 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택하는 방법을 취하는 해싱 함수기법이다.

 

해싱 관련 용어

동의어(Synonym)

해싱에서 동일한 홈주소로 인하여 충돌이 일어난 레코드들의 집합을 의미한다.

 

슬롯(Slot)

한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.

 

충돌(Collision)

• 레코드를 삽입할 때 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것을 의미한다.
• 버킷(Bucket)이 려거 개의 슬롯(Slot)으로 구성될 때 충돌(Collision)이 발생하여도 오버플로우가 발생하지 않을 수 있다.

 

인덱스

• 인덱스를 통하여 레코드를 빠르게 접근할 수 있다.
• DB의 물리적 구조와 밀접한 관계가 있다.
• 레코드의 삽입/삭제가 자주 발생 시 인덱스의 개수를 최소화하는 것이 효율적이다.

 

파일 편성 방법

순차 파일(Sequential File)

• 입력되는 데이터의 논리적 순서에 따라 물리적으로 연속된 위치에 순차적으로 기록하는 방식이다.
• 처리속도가 빠르고, 연속적인 레코드의 저장에 의해 헤코드 사이에 빈 공간이 존재하지 않으므로 기억 장치의 효율적인 이용이 가능하다.

 

색인 순차 파일(ISAM, Indexed Sequential Access-Method)

• 키값에 따라 순차적으로 정렬된 데이터를 저장하는 데이터 지역과 이 지역에 대한 포인터를 가진 색인 지역으로 구성된 파일이다.
• 순차 및 직접 접근 형태 모두 가능하도록 레코드들을 키값 순으로 정렬시켜 기록하고, 레코드의 키 항목만으로 모든 색인을 구성하는 방식이다.

 

VSAM 파일(Virtual Storage Access Method File)

• 동적 인덱스 방법을 이용한 색인 순차 파일이다.
• 기본 영역과 오버플로 영역을 구분하지 않는다.
• 레코드를 삭제하며 그 공간을 재사용할 수 있다.

 

직접파일(Direct File)

• 해싱 함수를 계산하여 물리적 주소에 직접 접근하는 방식으로 레코드를 임의 물리적 기억 공간에 기록한다.
• 특정 레코드에 접근하기 위해서 디스크의 물리적 주소로 변환할 수 있는 해싱 함수를 사용하는 방식이다.
• 속도가 빠르고, 랜덤 처리에 적합하나 기억 공간 효율이 떨어진다.

 

역파일(Inverted File)

• 특정 파일을 여러 개인 색인으로 만들고 항목별 특성에 맞게 작업하도록 구성한 구조이다.
• 파일 또는 DB에서 레코드를 빨리 검색하기 위해 별도 인덱스 파일을 만들어 두면 인덱스 파일에는 키 필드의 값과 그 키값을 가지는 레코드에 대한 포인터들이 저장된다.
• 검색 속도가 빠르다.