인덱스·파일 조직

학습 목표

인덱스와 파일 조직의 검색 특성만 비교한다.

본문

핵심 이론

B+트리 인덱스는 키 순서를 유지하여 등치와 범위 검색에 활용한다. 해시는 함수로 버킷을 선택하므로 등치 검색에 적합하고 충돌 처리가 필요하다.

밀집 인덱스는 모든 검색키 값에 엔트리를 두고 희소 인덱스는 일부 키에만 둔다. 희소 인덱스의 추가 탐색에는 파일 정렬 등 조건이 필요하다.

순차 파일은 키 순서의 순차 처리·병합에, 해시 파일은 키 기반 직접 접근에 초점을 둔다. 인덱스는 조회를 돕지만 저장 공간과 데이터 변경 시 유지 비용을 추가한다.

페이지 분할의 내부 구현이나 고급 실행계획 튜닝은 제외하고, 제시된 검색 조건에 알맞은 구조를 설명하는 수준으로 학습한다.

개념 도식

전체 맞춤원본 크기새 창 보기

검색 조건이 구조 선택의 이유가 된다

해시는 키에 함수를 적용해 버킷을 찾으므로 특정 키 한 개를 찾는 등치 검색에 적합하다. 다만 다른 키가 같은 버킷에 모일 수 있어 충돌 처리가 필요하다. 값이 가까워도 해시 버킷이 가까운 것은 아니므로 범위 검색에 그대로 활용하기 어렵다.

B+트리는 키의 순서를 유지한다. 100~200 범위에서는 시작 위치를 찾은 뒤 정렬된 리프 구간을 이어 읽을 수 있다. 트리라는 이름보다 ‘정렬된 범위를 연속 접근할 수 있다’는 이유를 답과 연결한다.

밀집 인덱스는 모든 검색키 값에 엔트리를 두고 희소 인덱스는 일부 키에만 둔다. 정렬된 파일의 블록 시작 키만 색인한 경우, 목표값 이하의 가장 가까운 시작 키를 찾아 해당 블록 안을 탐색한다. 희소 인덱스는 엔트리를 줄이는 대신 파일 정렬 등 전제가 필요하다.

인덱스는 조회 비용을 줄일 수 있지만 INSERT·UPDATE·DELETE 때 유지 작업이 생기고 저장 공간도 사용한다. 따라서 ‘항상 많을수록 빠르다’는 결론은 틀리다. 순차 파일·인덱스 파일·해시 파일은 정렬 순서, 직접 접근 방식, 변경 부담을 비교하는 정도로 정리한다.

풀이 예시

레코드의 고객번호에 계산식을 적용해 저장 버킷 주소를 얻는다. 별도의 정렬된 색인을 따라가지 않으며 서로 다른 고객번호가 같은 버킷으로 매핑될 때의 충돌 처리가 필요하다. 이러한 파일 조직 방식을 쓰시오.

해시 파일 조직