인덱스

  • 인덱스는 원하는 데이터를 쉽고 빠르게 찾을 수 있게 해주는 역할을 합니다. 원하는 정보를 검색할 때, 인덱스를 통해 해당 데이터의 주소를 찾아낼 수 있습니다.
  • 인덱스는 key-value(인덱스 칼럼 - 데이터 주소값)로 이루어진 한 쌍으로 구성되어 있으며, 인덱스를 구성하는 컬럼순으로 항상 정렬되어 있습니다.
  • 항상 정렬되어 있기 때문에, 인덱스가 많을수록 조회(=SELECT) 성능이 개선되고 데이터를 변경하는 DML(INSERT, DELETE, UPDATE)은 정렬로 인해 성능이 저하됩니다.

인덱스의 종류

  • 인덱스는 크게 아래 두가지 종류로 나뉩니다.
    1. 기본 키 (Primary Key)
      • 해당 테이블에서 데이터를 식별할 수 있는 기준 값
      • Not Null (=Null을 허용하지 않음)
      • 데이터 중복을 허용하지 않음
    2. 보조 키 (Secondary Key)
      • PK를 제외한 모든 인덱스
      • 유니크 키(Unique Key)는 PK와 성격이 비슷하며 PK를 대체할 수 있어 대체 키로 불림
    3. 유니크 키 (Unique Key)
      • 데이터 중복을 허용하지 않음
      • Unique Key에 대해 동등 조건(“=”)이 있는 쿼리는 옵티마이저가 1건만 찾으면 된다고 알려주는 효과가 있음

B-Tree 인덱스

  • 인덱싱 알고리즘 중에 가장 일반적으로 사용되는 알고리즘
  • B-Tree 구조는 크게 아래 세가지 노드 타입으로 분류
    1. 루트 노드 (Root)
      • 트리 구조의 가장 최상위에 존재하는 노드로, 하위에 자식 노드들이 존재.
    2. 리프 노드 (Leaf)
      • 트리 구조 가장 최하위에 존재하는 노드.
      • 인덱스의 B-Tree 구조에서, 실제 데이터를 찾아가기 위한 주소값이 포함됨.
    3. 브랜치 노드 (Branch)
      • 루트, 리프 노드도 아닌 중간에 존재하는 모든 노드를 의미.
  • 실제 데이터 파일의 레코드는 임의의 순서로 정렬되어 있지만, InnoDB에서 Primary Key가 있는 경우에는 항상 PK순으로 저장된 클러스터 구조.

  • 데이터 조회 시, B-Tree 인덱스를 통해 리프 노드에서 데이터 주소값을 이용하여 실제 레코드를 추출.

  • MySQL의 경우, 리프 노드에 실제 물리 주소값 대신, PK 값을 논리적인 주소값으로 사용.

B-Tree 인덱스 키 추가

  1. 저장될 위치 결정 2-1. 레코드의 키 값과, 주소값을 B-Tree 리프노드에 저장 2-2. 리프 노드에 저장할 공간이 없을 경우, 리프 노드의 분리(Split)가 필요해 상위 브랜치 노드까지 영향을 받음 (작업 비용이 커짐)

B-Tree 인덱스 키 삭제

  1. 삭제될 데이터의 키 값이 저장된 리프 노드에 삭제 마크
  2. 인덱스 키 삭제에 대한 마킹 작업도 디스크 I/O가 필요한 작업이며, 5.5버전 이상부터는 비동기 처리가 가능해짐.

B-Tree 인덱스 키 변경

  1. 키 값에 따라 B-Tree 구조의 노드 위치가 결정되므로 단순 변경이 불가능.
  2. 기존 키 값을 삭제 후, 신규 키 값을 추가하는 형태로 처리 (InnoDB 상에서는 체인지 버퍼를 활용해 비동기 처리 진행)

B-Tree 인덱스 키 검색

  • 인덱스 생성을 하는 가장 주요한 이유는 검색 성능 향상을 위함.
  • 데이터 조회 시, B-Tree 루트 노드에서부터 리프 노드 순으로 비교 작업을 수행. (= 트리 탐색)
  • 인덱스를 이용한 검색은 다음과 같은 경우에 사용 가능.
    1. 일치 검색 (“=”)
    2. 키 값의 앞부분 Like 검색 (“LIKE ‘xxx%’”)
    3. 부등호 비교 조건 (“<, >, <=, >=”)
  • 인덱스 컬럼에 변형이 이뤄진 경우 사용 불가

B-Tree 인덱스 사용에 영향을 주는 요소

  1. 인덱스 키 값의 크기
  2. B-Tree 깊이
  3. 선택도 (Cardinality)
  4. 읽어야 하는 레코드의 건수

B-Tree 인덱스의 기본 개념에 대해 정리해봤습니다. 이후 실제 쿼리를 통해 인덱스 사용 방법과, 종류에 대해 알아보겠습니다.