[Database] 인덱스 (Index)

인덱스 (Index)

• 인덱스는 데이터베이스의 테이블에 대한 검색 속도를 향상시켜주는 자료구조이다.
• 테이블의 특정 컬럼에 인덱스를 생성하면, 해당 컬럼의 데이터를 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장하며, 컬럼의 값과 물리적 주소를 (key, value) 쌍으로 저장한다.
  
  • 테이블 생성 시 MYD, MYI, FRM 3개의 파일이 생성된다.
  • FRM : 테이블 구조가 저장되어 있는 파일
  • MYD : 실제 데이터가 있는 파일
  • MYI :  인덱스 정보가 들어있는 파일
  • 인덱스를 사용하지 않는 경우 MYI 파일은 비어져 있다. 인덱싱하는 경우 MYI 파일이 생성되며 이후에 사용자가 Select 쿼리로 인덱스를 사용하는 컬럼을 탐색할 때 MYI 파일의 내용을 검색한다.

인덱스의 장단점

장점

• Full Table Scan을 하지 않아도 되기 때문에 검색 속도가 빨라진다.
  • 인덱스를 사용하지 않으면 Where문을 이용하여 특 정 조건의 데이터를 찾기 위해 테이블의 전체를 조건과 비교해야하는 Full Table Scan을 해야 했다. 그러나 인덱스를 사용하면 데이터들이 이미 정렬되어 있기 때문에 조건에 맞는 데이터를 빠르게 찾을 수 있다. 또한, Order By 문이나 Min/Max 같은 경우도 이미 정렬되어 있어 빠르게 수행할 수 있다.

단점

• 인덱스를 관리하기 위한 추가 작업이 필요하다.
  • 삽입, 삭제, 수정 작업을 수행할 때 삽입의 경우 새로운 데이터에 대한 인덱스를 추가하고, 삭제의 경우 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 수행하고, 수정의 경우 기존의 인덱스를 사용하지 않는다고 처리하고 갱신된 데이터에 대한 인덱스를 추가해야하는 작업이 필요하다.
  • 따라서 데이터의 수정이 잦은 경우 성능이 낮아진다. 
    
    
• 값과 물리적 주소를 저장하기 위한 추가적인 저장 공간이 필요하다.
  • 데이터의 인덱스를 제거하는 것이 아니라 사용하지 않는 것으로 처리하기 때문에 수정이 잦은 경우 실제 사용하는 데이터에 비해 인덱스가 과도하게 많아지는 문제점이 발생할 수 있다.
  • 또한, 별도의 메모리 공간에 저장되기 때문에 추가 저장 공간이 많이 필요하다.
    
    
• 잘못 사용하는 경우에는 오히려 검색 성능이 저하될 수 있다.
  • 인덱스는 전체 데이터의 10 ~ 15% 이상의 데이터를 처리하거나, 데이터의 형식에 따라 오히려 성능이 저하될 수 있다. 예를 들어, 사용자의 성별 같은 경우 값의 range 가 고작 2이기 때문에 인덱스를 이용한다고 해도 그 안에 많은 데이터가 있어 비효율적이다.

인덱스를 사용하면 좋은 경우

• 테이블의 규모가 클 때
• 삽입, 수정, 삭제 작업이 자주 발생하지 않는 컬럼
• Where, Order By, Join 등이 자주 사용되는 컬럼
• 데이터의 중복도가 낮은 컬럼

인덱스 사용을 피해야 하는 경우

• range가 작은 컬럼 즉, 데이터 중복도가 높은 컬럼
• DML 이 자주 일어나는 컬럼

인덱스의 자료구조

인덱스를 구현하는 대표적인 자료구조로는 해시 테이블과 B+Tree가 있다.

해시 테이블 (Hash Table)

해시 테이블은 key-value 쌍을 저장하고 검색하는 자료구조이다. 해시 충돌이 발생할 수 있지만 평균적으로 O(1)의 시간으로 데이터를 탐색할 수 있다.

해시 테이블을 이용하면 key = 컬럼 값, value = 물리적 주소 로 구현한다. 그러나 데이터베이스에서는 부등호연산이 자주 사용되는데 해시 테이블은 등호 연산에 최적화 되어있기 때문에 인덱스를 구현할 때 잘 사용하지는 않는다. 또한, 해시 테이블의 데이터들은 정렬되어 있지 않기 때문에 기준 보다 크거나 작은 값을 빠른 시간에 찾을 수 없다.

B+Tree

B+Tree는 균형 이진트리의 일종으로 데이터를 정렬된 상태로 저장하고 검색하는 자료구조이다. B+Tree는 내부 노드와 리프 노드로 구성되며, 리프 노드만 실제 데이터를 가지고 있으며 일반 노드는 자식 포인터만 저장한다.

리프 노드는 연결 리스트로 연결되어 있어 범위 검색이나 정렬된 데이터 처리에 용이하다. 반드시 리프 노드에만 데이터가 저장되기 때문에 중간 노드에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있다. 또한, B+Tree는 삽입과 삭제가 발생해도 트리의 균형을 유지하면서 성능을 보장한다.

https://rebro.kr/167

장점

• 메모리 확보
  • 리프 노드를 제외하고 데이터를 저장하지 않기 때문에 메모리를 확보할 수 있다. 따라서 하나의 노드에 많은 포인터를 가질 수 있어 트리의 높이가 낮아지고 이로 인해 검색 속도가 빨라질 수 있다.
    
    
• Full Scan 시 더 적은 시간이 소요된다.
  • 리프 노드에만 데이터가 저장되어 있고 연결 리스트로 연결되어 있기 때문에 선형 시간이 소요된다. 반면, B-Tree는 모든 노드를 확인해야 한다.

단점

• 특정 key를 찾기 위해 리프 노드까지 접근해야 한다. B-Tree는 최상의 경우 루트 노드에서 찾을 수 있다.

B-Tree 대신 주로 B+Tree를 사용하는 이유

인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생하는데 B+Tree는 연결 리스트로 구현되어 있기 때문에 이것을 이용하면 순차 검색을 효율적으로 할 수 있다.

참고: https://rebro.kr/167