#6-5 The Art of Computer Programming - 정렬과 검색

이번 절은 3권의 마지막 절인 2 차키에 의한 조회이다.

 

지금까지는 기본키에 대한 검색, 즉 한 파일에서 하나의 레코드를 유일하기 식별하는 키를 이용한 검색에 대해 알아보았다.

그런데 기본키 말고 레코드의 다른 필드에 기반해서 검색을 수행해야 하는 경우도 있다.

그런 필드를 2차키 혹은 특성(attribute)라고 한다.

일반화하면, 각 레코드가 여러 개의 특성들을 가진다고 할 때 특정한 특성들이 특정한 값들인 모든 레코드를 찾는 게 목표다.

원하는 레코드들의 명세를 가르켜 질의(query)라고 하며 아래의 3종류로 나눌 수 있다.

1. 단순 질의 : 특정한 하나의 특성에 특정한 하나의 값을 지정

2. 범위 질의 : 특정한 하나의 특성에 특정한 범위를 지정

3. 부을 질의 : 앞의 두 질의들을 AND, OR, NOT 연산으로 결합하여 질의

 

상기의 3가지는 실제 DB에서 쿼리를 요청할 때 자주 사용된다.

 

이런 세 종류의 질의에 효율적인 검색기법을 찾는 문제는 꽤 어려워서

이보다 더 복잡한 형태의 질의에 대해서는 고려하지 않는다.

 

파일이 아주 크고 질의에 대한 응답을 빨리 얻는게 중요할 경우 간단한 방식으로는 만족스럽게 처리가 어렵다.

그래서 이번절에서는 전형적인 컴퓨터 환경에서 2 차키 조회를 제대로 수행하는 방법에 대해 알아보기로 한다.

여러 가지 좋은 기법들이 이미 개발되었지만, 기본키 조회보다는 성능이 나쁠 수수 밖에 없다.

 

뒤집 한 파일 : 레코드와 특성의 역할 맞바뀜. 주어진 레코드의 특성들을 나열하는 대신 주어진 특성을 가진 레코드들을 나열

 

복합 특성, 이진 특성, 겹침 부호화, 조합적 해싱 등을 활용한 방법들을 소개하며

일반화된 트라이 및 균형 파일링 방안들에 대해서도 언급한다.