본문 바로가기
CS 스터디/Index

Index

Gyurim 2023. 6. 5. 11:13

Index

주제 선정 이유

  • DB를 사용하면서 데이터의 양(row)에 따라 실행 결과의 속도가 차이가 나는 것을 인지하고 있음
  • 데이터의 양이 증가할수록 실행 속도가 느려지고, JOIN이나 서브 쿼리 사용 시 곱 연산이 일어나 데이터의 양이 증가하기 때문에 WHERE 조건에서 필요한 데이터만 추출 후, 사용하는 것이 좋다고 알고 있음
  • 보다 쿼리의 성능을 높이는데 중요한 것은 인덱스를 적재적소 사용한 것
  • 인덱스의 개념과 구조, 사용 이유, 장단점 확인하기 위해 선정

인덱스란?

  • 추가적인 쓰기 작업과 저장 공간을 활용하여 데이터베이스 테이블의 검색 속도를 향상 시키기 위한 자료구조
  • 데이터베이스에서 테이블의 모든 데이터를 검색하면 시간이 오래 걸리기 때문에 데이터와 데이터의 위치를 포함한 자료구조를 생성하여 빠르게 조회할 수 있도록 도움
  • 특정 컬럼의 인덱스를 생성하면, 해당 컬럼의 데이터들을 정렬하여 별도의 메모리 공간에 데이터의 물리적 주소와 함께 저장됨
  • 만약 아래 그리과 같이 인덱스를 타게 되고 먼저 인덱스에 저장되어 있는 데이터의 물리적 주소로 가서 데이터를 가져오는 식으로 동작하여 검색 속도 향상 가능
  • 인덱스 생성 시, 데이터를 오름차순으로 정렬하기 때문에 정렬된 주소 체계라고 표현할 수 있음

  • ex)
    • 우리가 책에서 원하는 내용을 찾을 때, 책의 모든 페이지를 찾아 보는 것은 오래 걸림
    • 책의 저자들은 책의 맨 앞 혹은 맨 뒤에 색인 추가, 데이터베이스의 인덱스는 색인과 같음
    • 색인 : 본문 중의 중요한 것을 뽑아 한 곳에 모아 이들의 본문 소재의 페이지를 기재한 것
  • 인덱스를 활용하면, 데이터를 조회하는 SELECT 외에도 UPDATE나 DELETE의 성능이 향상됨
  • UPDATE나 DELETE 연산을 수행하려면 해당 대상을 조회해야 하기 때문
// KIM이라는 이름을 수정하기 위해 KIM을 조회
UPDATE USER SET NAME = 'CHOI' WHERE NAME = 'KIM';

인덱스의 장점과 단점

  • 장점
    • 테이블을 조회하는 속도와 그에 따른 성능 향상
    • 전반적인 시스템의 부하 줄일 수 있음
    • 가장 큰 특징은 데이터들이 정렬되어 있음, 조건 검색이라는 영역에서 굉장한 이점이 됨
    • 조건 검색 WHERE 절의 효율성
      • 테이블을 만들고 데이터가 쌓이게 되면 테이블의 레코드(row)는 내부적으로 순서없이 뒤죽박죽 저장됨
      • WHERE절에 특정 조건에 맞는 데이터를 찾기 위해, 레코드의 처음부터 끝까지 다 읽어서 검색 조건과 맞는지 확인 → Full Table Scan(Full Scan)
      • 인덱스 테이블 스캔(Index Tble Scan)시 인덱스 테이블은 데이터들이 정렬되어 저장되어 있기 때문에 해당 조건(WHERE)에 맞는 데이터를 빠르게 찾을 수 있음
    • 정렬 ORDER BY의 효율성
      • 인덱스를 사용하면 ORDER BY에 의한 정렬(Sort) 과정을 피할 수 있음
      • ORDER BY는 굉장히 부하가 많이 걸리는 작업
      • 정렬과 동시에 1차적으로 메모리에서 정렬이 이뤄지고 메모리보다 큰 작업이 필요하다면, 디스크 I/O도 추가적으로 발생
      • 인덱스를 사용하면 전반적인 자원 소모를 하지 않아도 됨, 이미 정렬되어 있기 때문
    • MIN, MAX의 효율적인 처리 가능
      • 데이터가 정렬되어 있기 때문에 가능
      • MIN값과 MAX값을 레코드의 시작 값과 끝 값 한건 씩 가져와야 하기 때문에, Full Table Scan으로 테이블을 모두 뒤져서 작업하는 것보다 훨씬 효율적으로 찾을 수 있음
  • 단점
    • 인덱스 DML에 취약
      • INSERT, UPDATE, DELETE를 통해 데이터가 추가되거나 값이 바뀐다면, 인덱스 테이블 내에 있는 값을 다시 정렬해줘야 함
      • 위 사진처럼 인덱스 테이블, 원본 테이블 이렇게 2군데의 데이터 수정 작업 필요
      • 만약 CREATE, DELETE, UPDATE가 빈번히 발생하는 속성에 인덱스를 적용시킨다면, 인덱스의 크기가 비대해져서 오히려 성능 저하 → DELETE, UPDATE 연산 때문
      • UPDATE와 DELETE는 기존의 인덱스를 삭제하지 않고, ‘사용하지 않음’ 처리
      • 어떤 테이블에서 UPDATE와 DELETE가 빈번히 발생하면, 실제 데이터는 10만건이지만, 인덱스는 훨씬 많이 존재하기 때문에 SQL문 처리 시 비대한 인덱스에 의해 오히려 성능 저하 발생
      • DML이 빈번한 테이블보다 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋음
    • 인덱스 스캔이 무조건 좋은 것은 아님
      • 검색을 위주로 하는 테이블에 인덱스를 생성하는 것이 좋지만, 무조건 검색 시에도 인덱스가 좋은 것은 아님
      • 인덱스는 테이블의 전체 데이터 중에서 10~15% 이하의 데이터를 처리하는 경우에만 효율적이고, 그 이상의 데이터를 처리할 땐 인덱스를 사용하지 않는 것이 더 좋음
      • ex) 1개의 데이터가 있는 테이블과 100만개의 데이터가 들어있는 테이블이 있다고 가정
      • 100만개의 데이터가 들어있는 테이블이라면, 풀 스캔보다는 인덱스 스캔이 유리하겠지만, 1개의 데이터가 들어있는 테이블(100%)은 굳이 인덱스 스캔 없이 풀 스캔이 빠를 것
    • 속도 향상을 위해 인덱스를 많이 만드는 것은 좋지 않음
      • 인덱스를 관리하기 위해서는 데이터베이스의 약 10%에 해당하는 저장 공간이 추가로 필요
      • 즉, 속도 향상에 비해 단저들의 COST를 비교해서 인덱스를 만들지 말지를 결정

인덱스를 남발하지 말아야 하는 이유

  • 데이터베이스 서버에 성능 문제가 발생하면 가장 빨리 생각하는 해결책이 인덱스 추가 생성
  • 문제가 발생할 때마다 인덱스를 생성하면서 인덱스가 쌓여가는 것은 하나의 쿼리문을 빠르게는 만들 수 있지만
  • 전체적인 데이터베이스의 성능 부하를 초래
  • 조회 성능을 극대화하려 만든 객체인데, 많은 인덱스가 쌓여서 INSERT, UPDATE, DELETE시에 부하가 발생해 전체적인 데이터베이스 성능 저하
  • 그렇기에 인덱스를 생성하는 것보다는 SQL문을 좀 더 효율적으로 짜는 방향이 좋음
  • 인덱스 생성은 마지막 수단으로 강구해야 할 문제

인덱스 관리

  • 인덱스는 항상 최신의 데이터를 정렬된 상태로 유지해야 원하는 값을 빠르게 찾을 수 있음
  • 인덱스가 적용된 컬럼에 INSERT, UPDATE, DELETE가 수행된다면 계속 정렬을 해주어야 하고 그에 따른 부하 발생
  • 이러한 부하를 최소화하기 위해, 인덱스는 ‘데이터 삭제’라는 개념에서 ‘인덱스를 사용하지 않는다’라는 작업을 대신함
    • INSERT: 새로운 데이터에 대한 인덱스를 추가
    • DELETE: 삭제하는 데이터의 인덱스를 사용하지 않는다는 작업을 진행
    • UPDATE: 기존의 인덱스를 사용하지 않음 처리하고, 갱신된 데이터에 대해 인덱스를 추가

인덱스 생성 전략

  • 생성된 인덱스를 가장 효율적으로 사용하려면, 데이터의 분포도는 최대한으로 그리고 조건절에 호출 빈도는 자주 사용되는 컬럼을 인덱스로 생성하는 것이 좋음
  • 인덱스는 특정 컬럼을 기준으로 생성하고 기준이 된 컬럼으로 정렬된 인덱스 테이블이 생성됨
  • 이 기준 컬럼은 최대한 중복이 되지 않는 값이 좋음
  • 가장 최선은 PK로 인덱스를 거는 것
  • 중복된 값이 없는 인덱스 테이블이 최적의 효율을 발생 시키고, 반대로 모든 값이 같은 컬럼의 인덱스 컬럼이 된다면 인덱스로써의 가치가 없다고 봐야 함
  1. 조건절이 자주 등장하는 컬럼
  2. 항상 =으로 비교되는 컬럼
  3. 중복되는 데이터가 최소한인 컬럼(분포도가 좋은 컬럼)
  4. ORDER BY 절에서 자주 사용되는 컬럼
  5. JOIN 조건으로 자주 사용되는 컬럼

인덱스의 자료구조

  • 인덱스를 구현하기 위해서는 다양한 자료구조를 사용
  • 대표적인 자료구조는 해시 테이블과 B+Tree

해시 테이블

  • (Key, Value)로 데이터를 저장하는 자료구조
  • 빠른 데이터 검색이 필요할 때 유용
  • Key 값을 이용해 고유한 index를 생성하여 그 index에 저장된 값을 꺼내오는 구조

  • 해시 테이블 기반의 index는 (컬럼값, 데이터의 위치) == (key, value) 로 사용하여 컬럼의 값으로 생성된 해시를 통해 인덱스를 구현
  • 해시 테이블의 시간 복잡도는 O(1)로 매우 빠른 검색 지원
  • 하지만 index에서 해시 테이블이 사용되는 경우는 제한적
  • 해시가 “=” 등호 연산에만 특화되었기 때문
  • 해시 함수는 값이 1이라도 달라지면 완전히 다른 해시 값 생성
  • 부등호 연산(<, >)이 자주 사용되는 데이터베이스 검색을 위해서는 해시 테이블 부적합
  • ex) ‘choi’로 시작하는 모든 데이터를 검색하기 위한 쿼리문은 인덱스의 혜택을 받지 못함
  • 이러한 이유로 데이터베이스의 인덱스는 B+Tree가 일반적으로 사용됨

B+Tree

  • DB의 인덱스를 위해 자식 노드가 2개 이상인 B-Tree를 개선시킨 자료구조
  • B+Tree는 모든 노드에 데이터(Value)를 저장했던 B-Tree와 다른 특성을 갖고 있음
    • 리프 노드(데이터 노드)만 인덱스와 함께 데이터(value)를 갖고 있고, 나머지 노드(인덱스 노드)들은 데이터를 위한 인덱스(key)만 갖고 있음
    • 리프 노드들은 LinkedList로 연결되어 있음
    • 데이터 노드 크기는 인덱스 노드의 크기와 같지 않아도 됨

데이터베이스의 인덱스 컬럼은 부등호를 이용한 순차 검색 연산이 자주 발생될 수 있음

이러한 이유로 BTree의 리프노드들은 LinkedList로 연결하여 순차검색을 용이하게 하는 등 BTree를 인덱스에 맞게 최적화 함

비록 B+Tree는 O(log2n)의 시간 복잡도를 갖고 있지

만, 해시 테이블보다 인덱싱에 더욱 적합한 자료구

티스토리툴바