[DB] 인덱스(Index)

인덱스란?

인덱스(Index)는 데이터베이스의 테이블 검색에 대한 속도를 향상해 주는 구조입니다.

테이블의 특정 컬럼에 인덱스를 생성하면 해당 컬럼의 데이터를 정렬한 후 별도의 메모리 공간에 컬럼의 값과 데이터의 물리적 주소를 key, value 형태로 저장합니다.

인덱스를 효율적으로 사용하기 위해서는 데이터의 양이 많고 중복이 적고 조회가 많거나 Insert, Update, Delete 작업의 빈도가 적은 컬럼에 사용하는 것이 좋습니다.

 

장점

인덱스를 적용하지 않은 상태라면 풀 테이블 스캔을 해야했지만 인덱스를 사용하면 데이터들이 정렬된 형태를 갖고 있어 빠르게 검색을 할 수 있습니다. 그로 인해  테이블을 검색하는 속도와 성능이 향상되어 시스템의 부하를 줄일 수 있습니다.

 

단점

인덱스를 항상 정렬된 상태로 유지하기 위해 추가적인 저장공간이 필요하고 Insert, Update, Delete 작업이 수행될 때 인덱스의 재정렬이 발생할 수 있습니다.

또한 잘못된 방식으로 인덱스를 사용할 경우 검색 성능이 저하될 수 있습니다.

 

자료구조

1. 해시 테이블 (Hash table)

해시 테이블은 키와 값을 한 쌍으로 데이터를 저장하는 자료구조입니다. 키를 이용해 대응되는 값을 구하는 방식으로 동작합니다.

해시 충돌이라는  변수가 존재하지만 평균적으로 O(1)의 매우 빠른 시간에 데이터를 검색할 수 있습니다.

해시 테이블은 = 연산에 최적화 되어있지만 범위 연산(<, >)이 자주 사용될 경우 정렬되어 있지 않은 구조상 검색 시간이 느립니다.

 

2. B+Tree

B-Tree의 확장 개념으로 leaf node에만 데이터를 저장하고 그 외의 node들은 데이터를 저장하지 않습니다. leaf node들은 linked list로 연결되어 있습니다.

leaf node에만 데이터가 저장되어 중간 node에서 키를 올바르게 찾아가기 위해 키가 중복될 수 있습니다.

leaf node를 제외한 node에는 데이터가 저장되지 않음으로 메모리를 더 확보할 수 있고 풀 스캔시 leaf node에 모든 데이터가 있기 때문에 한 번의 선형 탐색만 하면 되기 때문에 검색 시간이 빠릅니다.