시험 직전 요약장

• 모든 고객의 청구서를 고객 번호순으로 매일 출력한다면 순차 파일이 단순하다.
• 고객 번호로 단건 조회하면서 번호순 전체 출력도 필요하면 색인 순차 파일이 균형을 제공한다.
• 주문 번호로 정확히 한 건을 매우 자주 찾고 범위 조회가 거의 없다면 직접 파일이 유리할 수 있다.
• 삽입·삭제가 매우 잦으면 색인 갱신, 오버플로 영역, 재구성 비용까지 비교해야 한다.

어느 구조도 모든 연산에서 항상 우월하지 않다. 동등 검색, 범위 검색, 전체 순차 처리, 삽입·삭제, 저장 공간 중 무엇이 중요한지 먼저 정한다.

이 이론은 서로 다른 네 질문을 한꺼번에 다룬다. 검색은 자료 안에서 목표 키를 찾는 절차, 해싱은 키로 저장 위치를 계산하는 방법, 복잡도는 입력 크기에 따른 비용 증가율, 파일 구조는 보조기억장치에서 레코드를 배치하고 접근하는 방식이다. 같은 키를 사용하더라도 분석 대상이 다르므로 용어를 섞지 않는다.

예를 들어 순차 검색의 최악 비용 함수는 Θ(n)이다. 이 함수는 O(n)이면서 Ω(n)이기도 하다. 또한 3n + 100은 O(n²)라고 해도 수학적으로 틀리지는 않지만, 실제 증가 차수를 가장 정확히 나타내는 밀접한 경계는 Θ(n)이다.