DB 인덱스

인덱스가 없는 경우

인덱스가 없으면 풀 스캔을 통해 모든 데이터를 읽는다.

인덱스가 있는 경우

DBMS 에서는 일반적으로 B 트리 인덱스를 사용한다.

인덱스가 있다면 찾는 부분으로 이동 후 찾을 수 있다.

하지만 데이터 추가 삭제 시에는 인덱스 갱신도 해서 오버헤드가 클 수 있다.

인덱스의 구조 - B 트리 인덱스

트리 구조로 루트 블록, 브랜치 블록, 리프 블록, 원하는 데이터에 접근 가능한 구조를 가지고 있다.

이렇게 4개의 블록만 거치면 데이터를 찾을 수 있어서 풀스캔 할때보다 빠르다.

하지만 인덱스 블록을 읽을때마다 테이블 블록을 하나씩 읽어서 디스크 I/O 횟수가 늘어나기도 한다.

B 트리 인덱스는 트리 계층 구조가 깊어지지 않아 디스크 I/O 를 줄일 수 있기 때문에 DBMS 에서 많이 사용된다.

반대로 인메모리 데이터 베이스에서는 T 트리라는 이진 데이터 형식을 사용하는데 인메모리에서는 디스크 조회를 할 필요가 없으므로 키값 비교가 적은 T트리가 효율적이기 때문이다.

해시 테이블

해시 테이블에는 등호 검색에 강점이 있는 데이터 구조이다.

키와 값 조합으로 표를 구성하며, 해시 함수를 통해 해시 값으로 변환 되기 때문에 조합 표의 데이터 구조가 간단해서 검색이 빠르다는 장점이 있다.

등호 검색에 있어서는 아무리 데이터가 늘어나도 동일한 성능을 낸다.

범위 검색에서는 약한 경향이 있어서 B 트리가 만능으로 사용할 수 있는 데이터 구조라면 해시 테이블은 좀더 등호 검색에 특화된 데이터 구조라고 할 수 있다.