[MySQL] 인덱스 개념 및 B-Tree 인덱스

#해당 내용들은 RealMySQL 책에 기반하고 있습니다

• 데이터베이스 성능 튜닝 ~ 디스크 I/O 줄이기
  -> DB 서버에서는 항상 디스크 장치가 병목 지점

  • SSD는 데이터 저장용 플래터를 제거하고 플래시 메모리를 장착 -> 원판의 기계적 회전이 사라져 HDD보다 빠름

  • 디스크의 헤더를 움직이지 않고 한번에 많은 데이터를 읽는 순차 I/O에서는 SSD ~ HDD

  • 하지만 랜덤 I/O에서는 SSD가 HDD보다 훨씬 빠름

  • 랜덤 IO vs. 순차 IO

  • 순차 IO는 연속된 페이지를 디스크에 기록하기 위해 1번 system call

    • 사실상 순차 IO도 작업시에 동기화 작업이 필요하기에 1번안에 처리하기 어려운데, 이에 따라 RAID 컨트롤러를 사용하여 효율적으로 순차 IO를 처리할 수 있도록 함

  • 랜덤 IO는 매번 새롭게 페이지 넣을 위치 찾느라 n번 system call

  • 즉 쿼리를 튜닝하는 것 = 랜덤 IO를 줄여주는 것

  • 인덱스 레인지 스캔: 데이터를 읽기 위해 랜덤 IO 사용

  • 풀 테이블 스캔: 순차 IO 사용
    -> 큰 테이블의 레코드 대부분을 읽을 경우에는 임의로 인덱스 레인지 스캔이 아닌, 풀 테이블을 스캔하도록 구성하기도 함

• 인덱스

  • 칼럼의 값을 주어진 순서로 미리 정렬해서 보관!

• 인덱스 : SortedList 같은 느낌

  • 항상 정렬된 상태로 유지
  • 저장시마다 항상 값의 정렬 과정이 있어 느리지만, 값을 찾을 경우에는 매우 빠르게!
  • I, U, D를 희생하고 Select의 성능을 높이는 느낌!
  • 따라서 인덱스가 너무 많아도.. 좋지 않다! (데이터 저장성능 저하)
  • 데이터 파일: ArrayList같은 느낌 (별도의 정렬 없이 그대로 저장)

• 인덱스 분류
  프라이머리키와, 프라이머리키를 제외한 모든 인덱스인 보조인덱스

  • 데이터 저장 알고리즘에 따른 분류
    • B-Tree
      칼럼의 값을 변형하지 않고, 원래의 값을 이용해 인덱싱
    • Hash
      칼럼의 값으로 해시값을 계산해서 인덱싱
      - 칼럼 자체의 값으로 인덱싱되는 것이 아니라, prefix 일치와 같은 일부 검색 불가능
      - 메모리 기반 DB에서 주로 사용
    • Fractal-Tree
      • B-Tree 단점 보완 (정확한 설명 X)

• B-Tree 인덱스

  • 보통 B+ Tree, B* Tree 이용 (여기서 B는 Balanced!)

  • B-Tree: 루트 노드(젤 부모), 리프 노드(젤 자식), 브랜치 노드(루트, 리프 노드 제외한 노드들)

  • 리프 노드에는 실제 데이터 레코드를 찾아가기 위한 주소값을 가지고 있음

  • 데이터 레코드는 insert된 순서대로 저장되는 것이 아님!

    • 하지만 InnoDB의 경우에는, 레코드가 PK 단위로 클러스터되어 디스크에 저장되어 순서대로 저장됨 (디폴트로 클러스터링 테이블 생성)

  • 레코드를 찾아가기 위한 주소값에 InnoDB의 경우에 는 PK가 담김 (PK에 의해 클러스터링 되어 디스크에 저장되기 때문)

  • 인덱스에 새로운 key가 추가될 때 B-Tree에서 적합한 위치를 찾아 추가됨

    • 비용이 꽤나 소모되어, InnoDB 스토리지 엔진의 경우 해당 작업을 지연시켜 나중에 처리할지 여부를 세팅 가능하다 (By Insert Buffer)

  • 삭제될 때에는 레코드를 찾아 삭제 마킹

  • 변경의 경우

    • 키 값에 따라 저장될 리프노드의 위치가 결정되는 방식이라, 단순한 변경은 불가능하고 키 값을 삭제한 후, 새로운 키 값을 추가하는 형태로 처리됨

  • 검색

    • B-Tree 인덱스를 이용한 검색은 100% 일치 or 값의 앞부분만 일치의 경우에 사용 가능
    • <> 또는 뒷부분 substring 검색, 인덱스의 키 값에 변형이 가해진 값을 기반으로 비교/정렬할 경우 등은 인덱스 활용이 불가능

  • 인덱스 키 값이 커지면 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 갯수가 작아져서, B-Tree의 깊이가 깊어지고, 디스크로부터 읽어야하는 인덱스 페이지도 많아진다. -> 느려짐

  • 인덱스 페이지를 읽는 것도, disk로 부터 읽는 것으로, 인덱스 페이지를 많이 읽어야하는 부분도 병목이 될 수 있음

    • 즉, B-Tree의 깊이 ~ 랜덤 IO 발생 횟수

  • 그래도 B-Tree의 깊이기 4~5 이상까지 깊어지지는 X

  • Cardinality

    • 인덱스 키값들 중 유니크한 값의 수 (key값의 종류 갯수)
    • Cardinality 값이 클수록, 특정 인덱스 키에 해당하는 데이터가 많이 없기 때문에, 검색 대상이 줄어들어 빠르게 처리됨
      (전체 레코드 건수를 cardinality로 나눠보면, 하나의 키 값에 해당하는 레코드 건수 예측 가능)

  • 인덱스를 통해 테이블의 레코드를 읽는 것은, 인덱스를 안거치고 레코드를 바로 읽는 것보다 높은 비용이 듦 (4~5배)

    • 옵티마이저에서 풀스캔과 인덱스 활용을 적절히 판단해서 쿼리를 수행

  • 인덱스를 통한 데이터 읽기

    • 인덱스 레인지 스캔
      • 검색해야할 인덱스의 범위가 결정됐을 때 사용
      • 시작해야할 위치를 찾으면, 그 후부터는 리프 노드의 레코드만 순서대로 스캔
      • 리프 노드의 끝에 달하면 리프 노드간의 링크를 통해 다음 리프 노드를 찾아 스캔 -> 완료시 레코드 사용자에게 반환
      • 리프 노드에서 검색조건에 일치하는 건들은 데이터 파일에서 레코드를 읽어와야하는데, 레코드 한건 한건 단위로 랜덤 io가 한번씩 실행됨
        -> 비용이 많이 드는 작업
    • 인덱스 풀 스캔
      • 인덱스의 처음부터 끝까지 모두 읽음
      • 쿼리의 조건절에 사용된 조건이 인덱스의 첫번째 칼럼이 아닌 경우
        ex) index: (a, b, c), 검색조건: (b, c)
      • 인덱스에 명시된 칼럼만으로 조건을 처리할 수 있으므로 인덱스만 읽어도 되어서, 테이블 풀 스캔보다는 효율적 but 당연히 레인지 스캔보다는 slow
    • 루스 인덱스 스캔
      • group by, max, min 등에 대해서 사용
      • min/max 조건의 경우에, 이미 인덱스에 따라 정렬이 되어 있으므로 가져온 인덱스 페이지에 대하여 모두 읽을 필요 없고, 제일 위/아래 row만 읽어도 결과값을 반환 가능한 경우가 있음
      • 이런 경우 가져온 인덱스 페이지를 순차적으로 스캔하는 방식이 아니므로, 루스 인덱스 스캔이라고 함

  • 다중 칼럼 인덱스

    • 인덱스의 n번째 칼럼은 n-1번째 칼럼에 의존해서 정렬되어 있음
    • 즉, n번째 칼럼의 정렬은, n-1번째 칼럼이 똑같은 레코드에서만 의미가 있음
    • 따라서 인덱스를 pair로 걸 때 거는 순서에 따라서 성능이 크게 차이가 남 (a,b)로 거느냐, (b,a)로 거느냐에 따라서.
      -> 둘다 작업 범위 결정 조건으로 쓰일수도 있고, 하나는 필터링 조건으로만 이용될 수 있다.
      -> (a,b)로 인덱스를 걸었는데 b에 대한 조건만 있을 경우, 인덱스 활용이 불가능함 (postfix도 마찬가지 원리로 인덱스 활용 불가능)