Blog
스터디
CS Study with SON
4주차
인덱스

인덱스(Index)

추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상시키기 위한 자료구조


개념

  • 데이터베이스에서 컬럼(속성)을 기반으로 빠른 검색을 지원하기 위한 자료구조
  • 특정 컬럼 값 기반으로 테이블 행에 대한 물리적인 위치를 찾아 매핑
  • 테이블에 대한 보조 구조로써 생성되며, 원본 데이터와 별도로 관리
  • 특정 컬럼에 인덱스 생성 시, 해당 컬럼의 데이터를 정렬 후 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장
  • 컬럼 값, 물리적 주소를 (Key, value) 한 쌍으로 저장

장점

  • 테이블의 검색 속도와 성능 향상

    • 전반적인 시스템 부하를 줄임
  • 데이터들이 정렬된 형태를 가짐

    • Full Table Scan(특정 데이터 검색을 위해 테이블 전체 조건과 비교) 작업 불필요
    • ORDER BY, MIN/MAX 작업의 빠른 수행

단점

  • 인덱스 관리를 위한 오버헤드가 발생

    • 원하는 값을 빠르게 탐색하기 위해 항상 정렬된 상태로 유지해야 한다.
      • 삽입(INSERT) : 새로운 데이터에 대한 인덱스 추가
      • 삭제(DELET) : 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업 수행
      • 수정(UPDATE) : 기존의 인덱스 사용않음 처리 및 갱신된 데이터의 인덱스 추가
  • 데이터 잦은 수정 작업시 성능 저하

    • 인덱스 제거가 아닌 '사용하지 않음'처리 남겨둬 수정 작업이 많은 경우 데이터에 비해 과도하게 인덱스 커짐
  • 인덱스를 관리하기 위해 DB의 약10%의 추가적인 저장공간이 필요

  • 데이터의 수에 따라 풀스캔이 효율적일수 있다.

    • 1개의 데이터가 들어있는 테이블의 경우 인덱스를 이용하는 것보다 풀스캔이 효율적이다.


인덱스의 자료구조

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


해시 테이블(Hash Table)

Key와 Value를 한 쌍으로 데이터를 저장하는 자료구조

  • (key, value) 쌍 표현
  • key값을 이용해 대응되는 value값을 구함
  • 평균적으로 O(1)의 빠른 시간에 데이터 탐색 (해시 충돌의 변수 존재)

인덱스와 해시 테이블

  • (Key, value) = (컬럼의 값, 데이터의 위치)로 인덱스 구현
  • 실제로 인덱스에서 잘 사용X
    • 해시 테이블은 등호(=)연산에 최적화
    • 데이터베이스에선 부등호(<,>) 연산이 자주 사용 됨
    • 해시 테이블 내 데이터들은 정렬되어있지 않으므로 특정 기준보다 크거나 작은 값을 빠른 시간 내 찾을 수 없음

B+Tree


기존의 B-Tree의 단점을 개선시킨 자료구조


  • leaf node에만 데이터 저장
    • 중간 node에서 key를 올바르게 찾아가기 위해 key가 중복될 수 있음
    • leaf node끼리 LinkdedList로 연결
  • leaf node가 아닌 node에는 자식 포인터만 저장

leaf node끼리 LinkdedList로 연결하여 부등호를 이용한 순차 검색 연산이 자주 발생하는 경우 root로 돌아가 leaf node를 재탐색하는 것이 아닌 다음 node를 탐색한다.



인덱스의 존재여부와 ORDER BY/GROUP BY 연산의 동작 과정

ORDER BY

  • 결과 집합을 특정 열 기준으로 정렬 시 사용
  • 정렬 작업은 정렬을 수행할 열의 값을 비교하고 필요에 따라 데이터를 재배열하는 것을 의미

  • 인덱스 미존재 ( ORDER BY의 기준이 되는 열에 인덱스 없을 경우 ) - 데이터베이스는 전체 테이블을 스캔하여 정렬 수행 - 대량의 데이터에 대해 매우 비효율적

  • 인덱스 존재

    • 데이터베이스는 인덱스를 사용하여 정렬 작업 수행
    • 인덱스는 정렬된 순서로 데이터에 액세스할 수 있도록 도와주어 정렬 작업 성능 향상

GROUP BY

  • 특정 열을 기준으로 데이터를 그룹화 시 사용
  • 그룹화된 결과는 주로 집계 함수와 함께 사용되어 그룹별로 데이터 요약, 분석시 유용

  • 인덱스 미존재 ( GROUP BY의 기준이 되는 열에 인덱스 없는 경우 )
    • 데이터베이스는 전체 테이블을 스캔하여 그룹화 수행
    • 대량의 데이터에 대해서는 성능 문제 일으킬 가능성 존재


* 인덱스 존재 - 데이터베이스는 인덱스를 사용하여 그룹화 작업 수행 - 인덱스는 동일한 그룹 값들이 연속적으로 저장되어 있으므로, 그룹화 작업의 성능을 향상



기본키와 인덱스

기본 키
: 데이터베이스 테이블에서 각 행을 고유하게 식별하기 위해 사용되는 열 또는 열의 집합


외래 키
: 관계형 데이터베이스에서 한 테이블의 열이 다른 테이블의 기본키를 참조하는 경우 사용되는 열

  • 참조 무결성을 유지하고 테이블 간의 관계 설정 시 사용

인덱스
: 데이터베이스에서 데이터에 대한 검색 및 정렬을 향상시키기 위해 생성되는 데이터 구조


<기본키와 인덱스>

기본키는 인덱스가 될 수 있지만, 기본키가 반드시 인덱스인 것은 아니다. 하지만 일반적으로 기본키 열에는 인덱스가 자동으로 생성되어 기본키의 고유성과 검색성능을 보장하는데 사용된다.


<외래키와 인덱스>

외래키 관계를 사용해 테이블 간의 JOIN작업을 수행하거나 외래키 열을 검색하는 경우 인덱스를 활용해 검색성능을 향상시킬 수 있다. 따라서 외래키 열에는 인덱스를 생성하는 것이 좋으며, 일반적인 관례로 외래키 열에 인덱스를 생성한다.